第5章搜索求解策略

ArtificialIntelligencePrinciplesandApplications第5章搜索求解策略教材：王万良《人工智能及其应用》（第2版）高等教育出版社，2008.62第5章搜索求解策略5.1搜索的概念5.2状态空间的搜索策略5.3盲目的图搜索策略5.4启发式图搜索策略5.5与/或图搜索策略3第5章搜索求解策略5.1搜索的概念5.2状态空间知识表示方法5.3盲目的图搜索策略5.4启发式图搜索策略5.5与/或图搜索策略45.1搜索的概念问题求解：问题的表示。选择一种相对合适的求解方法。问题求解的基本方法：搜索法、归约法、归结法、推理法及产生式等。55.1搜索的概念5.1.1搜索的基本问题与主要过程5.1.2搜索策略65.1.1搜索的基本问题与主要过程搜索中需要解决的基本问题：（1）是否一定能找到一个解。（2）是否终止运行或是否会陷入一个死循环。（3）找到的解是否是最佳解。（4）时间与空间复杂性如何。75.1.1搜索的基本问题与主要过程搜索的主要过程：(1)从初始或目的状态出发，并将它作为当前状态。(2)扫描操作算子集，将适用当前状态的一些操作算子作用于当前状态而得到新的状态，并建立指向其父结点的指针。(3)检查所生成的新状态是否满足结束状态，如果满足，则得到问题的一个解，并可沿着有关指针从结束状态反向到达开始状态，给出一解答路径；否则，将新状态作为当前状态，返回第(2)步再进行搜索。85.1.2搜索策略1.搜索方向：(1)数据驱动：从初始状态出发的正向搜索。正向搜索——从问题给出的条件（一个用于状态转换的操作算子集合）出发。逆向搜索：先从想达到的目的入手，看哪些操作算子能产生该目的以及应用这些操作算子产生目的时需要哪些条件。(2)目的驱动：从目的状态出发的逆向搜索。95.1.2搜索策略1.搜索方向：(3)双向搜索双向搜索：从开始状态出发作正向搜索，同时又从目的状态出发作逆向搜索，直到两条路径在中间的某处汇合为止。105.1.2搜索策略2.盲目搜索与启发式搜索:（1）盲目搜索：在不具有对特定问题的任何有关信息的条件下，按固定的步骤（依次或随机调用操作算子）进行的搜索。（2）启发式搜索：考虑特定问题领域可应用的知识，动态地确定调用操作算子的步骤，优先选择较适合的操作算子，尽量减少不必要的搜索，以求尽快地到达结束状态。11第5章搜索求解策略5.1搜索的概念5.2状态空间知识表示方法5.3盲目的图搜索策略5.4启发式图搜索策略5.5与/或图搜索策略125.2状态空间知识表示方法5.2.1状态空间表示法5.2.2状态空间的图描述135.2.1状态空间表示法状态：表示系统状态、事实等叙述型知识的一组变量或数组：],,,[21nqqqQ},,,{21mfffF操作：表示引起状态变化的过程型知识的一组关系或函数：T145.2.1状态空间表示法状态空间：利用状态变量和操作符号，表示系统或问题的有关知识的符号体系，状态空间是一个四元组：),,,(0GSOS：状态集合。：操作算子的集合。：包含问题的初始状态是的非空子集。：若干具体状态或满足某些性质的路径信息描述。O0SGSS155.2.1状态空间表示法求解路径：从结点到结点的路径。0SGGSSSkOOOO321210kOO,,1：状态空间的一个解。状态空间的一个解：一个有限的操作算子序列。16例1八数码问题的状态空间。5.2.1状态空间表示法状态集：所有摆法S操作算子：将空格向上移Up将空格向左移Left将空格向下移Down将空格向右移Right175.2.2状态空间的图描述（状态）（操作算子）状态空间的有向图描述185.2.2状态空间的图描述八数码状态空间图19例2旅行商问题（travelingsalesmanproblem,TSP）或邮递员路径问题。5.2.2状态空间的图描述（家）（单位：km）可能路径：费用为375的路径（A，B，C，D，E，A）205.2.2状态空间的图描述旅行推销员状态空间图（部分）ABCDEA375AAAABBCCCCDDDDAEEEEEEED路径:路径:路径:路径:ABCEDAABDCEABDECA费用:费用:费用:费用:42552547552547537532540040030027527525022515010075125175225250100175225425.......21第5章搜索求解策略5.1搜索的概念5.2状态空间知识表示方法5.3盲目的图搜索策略5.4启发式图搜索策略5.5与/或图搜索策略225.3盲目的图搜索策略5.3.1回溯策略5.3.2宽度优先搜索策略5.3.3深度优先搜索策略235.3.1回溯策略带回溯策略的搜索：从初始状态出发，不停地、试探性地寻找路径，直到它到达目的或“不可解结点”，即“死胡同”为止。若它遇到不可解结点就回溯到路径中最近的父结点上，查看该结点是否还有其他的子结点未被扩展。若有，则沿这些子结点继续搜索；如果找到目标，就成功退出搜索，返回解题路径。24递归过程：5.3.1回溯策略StepTrack(DataList)：Data：=First(DataList);ifMember(Data,Tail(DataList))thenreturnFAIL;*回老路退回ifGoal(Data)thenreturnNIL;*达到目的地成功返回ifDeadEnd(Data)thenreturnFAIL;*达到不合理状态，退出ifLength(DataList)BoundthenreturnFAIL;*已到深度限制，退回Rules：=AppRules(Data);*得出可应用的规则集Loop：ifNull(Rules)thenreturnFAIL;*进入死胡同，退回R：=First(Rules);*取出第一条可用规则Rules：=Tail(Rules);Newdata：=Gen(R,Data);*运用规则，生成新状态NewDataList：=Cons(Newdata,DataList);Path：=BackTrack(NewDataList);*递归IfPath：=FAILthengoloopelsereturnCons(R,Path);255.3.1回溯策略1AB2E3J57K9G6F10H11D8C回溯搜索示意图265.3.1回溯策略回溯搜索的算法(1)PS（pathstates）表：保存当前搜索路径上的状态。如果找到了目的，PS就是解路径上的状态有序集。(2)NPS（newpathstates）表：新的路径状态表。它包含了等待搜索的状态，其后裔状态还未被搜索到，即未被生成扩展。(3)NSS（nosolvablestates）表：不可解状态集，列出了找不到解题路径的状态。如果在搜索中扩展出的状态是它的元素，则可立即将之排除，不必沿该状态继续搜索。275.3.1回溯策略Functionbacktrack：beginPS：=[Start];NPS：=[Start];NSS：=[];CS：=Start;*初始化whileNPS[]dobeginifCS=目的状态thenreturn(PS);*成功，返回解题路径ifCS没有子状态（不包括PS，NPS和NSS中已有的状态）thenbeginwhile（(PS非空)and(CS=PS中的第一个元素)）dobegin将CS加入NSS*标明此状态不可解从PS中删除第一个元素CS*回溯从NPS中删除第一个元素CS；CS：=NPS中的第一个元素；285.3.1回溯策略end;将CS加入PS；endelsebegin将CS子状态（不包括PS、NPS和NSS中已有的）加入NPS；CS：=NPS中第一个元素；将CS加入到PS；endend；returnFAIL;end.29回溯搜索示意图的回溯轨迹：初值：PS=[A]；NPS=[A]；NSS=[]；CS=A。5.3.1回溯策略305.3.1回溯策略图搜索算法（深度优先、宽度优先、最好优先搜索等）的回溯思想：（1）用未处理状态表（NPS）使算法能返回（回溯）到其中任一状态。（2）用一张“死胡同”状态表（NSS）来避免算法重新搜索无解的路径。（3）在PS表中记录当前搜索路径的状态，当满足目的时可以将它作为结果返回。（4）为避免陷入死循环必须对新生成的子状态进行检查，看它是否在该三张表中。315.3.2宽度优先搜索策略open表（NPS表）：已经生成出来但其子状态未被搜索的状态。closed表（PS表和NSS表的合并）：记录了已被生成扩展过的状态。0S12345678910宽度优先搜索法中状态的搜索次序325.3.2宽度优先搜索策略Procedurebreadth_first_searchbeginopen：=[start];closed：=[]*初始化whileopen[]dobegin从open表中删除第一个状态，称之为n；将n放入closed表中；ifn=目的状态thenreturn(success);生成n的所有子状态；从n的子状态中删除已在open或closed表中出现的状态；将n的其余子状态，按生成的次序加入到open表的后段。end;end;open表：队列结构，即先进先出（FIFO）的数据结构33例3通过搬动积木块，希望从初始状态达到一个目的状态，即三块积木堆叠在一起。5.3.2宽度优先搜索策略BCAABC(a)初始状态(b)目的状态积木问题34操作算子为MOVE（X，Y）：把积木X搬到Y（积木或桌面）上面。5.3.2宽度优先搜索策略MOVE（A，Table）：“搬动积木A到桌面上”。操作算子可运用的先决条件：（1）被搬动积木的顶部必须为空。（2）如果Y是积木，则积木Y的顶部也必须为空。（3）同一状态下，运用操作算子的次数不得多于一次。35ABABACCBACCCBABCABACBAABCBCBCCABAMOVE(A,TABLE)MOVE(C,A)MOVE(A,C)MOVE(B,A)MOVE(B,C)MOVE(C,A)MOVE(C,B)MOVE(C,B)MOVE(A,B)0S1S2S3S4S5S6S7S8S9S10S没有后裔，失败退出积木问题的宽度优先搜索树5.3.2宽度优先搜索策略365.3.3深度优先搜索策略0S12345678910111213KK深度优先搜索法中状态的搜索次序0S12345678910111213KK深度优先搜索法中状态的搜索次序37在深度优先搜索中，当搜索到某一个状态时，它所有的子状态以及子状态的后裔状态都必须先于该状态的兄弟状态被搜索。为了保证找到解，应选择合适的深度限制值，或采取不断加大深度限制值的办法，反复搜索，直到找到解。5.3.3深度优先搜索策略38深度优先搜索过程：5.3.3深度优先搜索策略Proceduredepth_first_searchbeginopen:=[start];closed:=[];d:=深度限制值whileopen[]dobegin从open表中删除第一个状态，称之为n;将n放入closed表中；ifn=目的状态thenreturn(success);ifn的深度dthencontinue;生成n的所有子状态；从n的子状态中删除已在open或closed表中出现的状态；将n的其余子状态，按生成的次序加入到open表的前端。endend。open表：堆栈结构，即先进后出（FILO）的数据结构。open表：所有已生成但未作扩展的状态closed表记录了已扩展过的状态39深度优先搜索并不能保证第一次搜索到的某个状态时的路径是到这个状态的最短路径。对任何状态而言，以后的搜索有可能找到另一条通向它的路径。如果路径的长度对解题很关键的话，当算法多次搜索到同一个状态时，它应该保留最短路径。5.3.3深度优先搜索策略40例4卒子穿阵问题，要求一卒子从顶部通过下图所示的阵列到达底部。卒子行进中不可进入到代表敌兵驻守的区域（标注1），并不准后退。假定深度限制值为5。5.3.3深度优先搜索策略00010010010000012134213