基于搜索的问题求解之盲目搜索.ppt

第二章 基于搜索的问题求解,一种在图中寻找路径的方法。,八数码魔方,2.1 搜索与人工智能的关系,初始节点S0,目标节点Sg,状态空间表示,状态（State）的基本概念 状态(state)是为描述某类不同事物间的差别而引入的一组最少变量q0，q1，qn的有序集合，其矢量形式如下：Q=q0,q1,qnT(1)式中每个元素qi(i=0,1，n)为集合的分量，称为状态变量。给定每个分量的一组值就得到一个具体的状态，如 Qk=q0k,q1k,，qnkT(2),例如，八数码魔方中，一个具体的状态集合Q中，Q0是 而Qk是,问题求解技术主要是两个方面：问题的表示求解的方法,问题的状态空间(state space)是一个表示该问题全部可能状态及其关系的图，它包含三种说明的集合，即所有可能的问题初始状态集合S、算符集合F以及目标状态集合G。因此，可把状态空间记为三元状态(S，F，G)。,算符：使问题从一种状态变化为另一种状态的手段称为操作符或算符。操作符可为走步、过程、规则、数学算子、运算符号或逻辑符号等。,例如，例子中的八数码魔方问题就可以用三元状态空间表示为（S0，F，Sg）其中，S0代表初始状态，Sg代表目标状态，而F就是所有能将初始状态变化为目标状态的算符集合。,举例：,0,1,2,x,0,1,2,y,迷宫问题,整个迷宫问题的知识表示是如书上第10页的图2.3，这是一种状态图知识表示法。问题是：机器人位于迷宫入口(0，0)处，如何到达迷宫的出口(2，2)。解：问题空间的初始状态是节点(0,0),而目标状态是节点(2,2)。从图2.3可见，从(0,0)到(2,2)需经过(U，R，R，U)算符集合的操作，因此本问题的解用三元状态集合表示为：(0,0),(U,R,R,U),(2,2),与图有关的术语,状态空间图由节点(不一定是有限的节点)及连接节点的分枝的集合构成。有限节点图节点数目有限的图称为有限节点图。有向图一对节点用分枝线连接起来，从一个节点指向另一个节点。这种图叫做有向图。始节点叫父节点或双亲节点，终节点叫子节点。,扩展求解父节点的所有子节点，叫做扩展。路径在一系列节点n1,n2,nm中，从n1开始，ni总有分枝连接ni+1，称从n1到nm之间的分枝集合是路径。路径中不包含两个及以上相同的分枝，如果n1和nm是同一个节点，则称这种路径为闭路。不构成闭路的称为树。在用状态空间图来表示问题时，对问题的求解就是求出从初始节点到目标节点的路径。,2.2 逐个搜索,图搜索的定义一种计算机在状态图中寻找路径的方法。,随机搜索,也叫做盲目搜索，是最单纯的路径搜索算法，步骤如书上第12页中算法1所示。在这种算法中，由于没有特别的信息去指导下一步怎么走，因此不一定能找到问题的解，或可能得出的解不是最优的。,CLOSED表的引入,CLOSED表(记录扩展过的节点),OPEN表的引入,OPEN表(记录待扩展的节点),举例：八数码魔方例子中,OPEN表变化过程,CLOSED表变化过程,随机搜索的一般过程,(1)建立一个只含有起始节点S的搜索图G，把S放到一个叫做OPEN表的未扩展节点表中。(2)建立一个叫做CLOSED的已扩展节点表，其初始为空表。(3)LOOP：若OPEN表是空表，则失败退出。(4)选择OPEN表上的第一个节点，称此节点为节点n。若n为一目标节点，则有解并成功退出，其解是追踪图G中沿着指针从n到S这条路径而得到的(指针将在第7步中设置)(5)若n不是目标节点，则把它从OPEN表移出并放进CLOSED表中。,随机搜索的一般过程,(6)扩展节点n，同时生成不是n的祖先的那些后继节点的集合M。把M的这些成员作为n的后继节点添入图G中。(7)对那些未曾在G中出现过的(既未曾在OPEN表上或CLOSED表上出现过的)M成员设置一个通向n的指针。把M的这些成员加进OPEN表。对已经在OPEN表上的每一个M成员，确定是否需要更改通到n的指针方向。(8)不排或按某方式重排OPEN表。(9)GO LOOP。,开始,把S放入OPEN表,OPEN表为空表？,把第一个节点(n)从OPEN表移至CLOSED表,n为目标节点吗？,把n的后继节点放入OPEN表的末端，提供返回节点n的指针,修改指针方向,重排OPEN表,失败,成功,图搜索一般过程的框图,是,是,否,否,4.纵向搜索,定义 首先扩展最新产生的(即最深的)节点。深度相等的节点可以任意排列。这种盲目(无信息)搜索叫做纵向搜索。特点 扩展最深的节点的结果使得搜索沿着状态空间某条单一的路径从起始节点向下进行下去；只有当搜索到达一个没有后裔的状态时，它才考虑另一条替代的路径。,为了防止搜索过程沿着无益的路径扩展下去，往往给出一个节点扩展的最大深度深度界限。纵向搜索算法是一种“后进先出”的算法。,八数码魔方的纵向搜索树,举例：迷宫问题,0,1,2,x,0,1,2,y,小机器人的初始位置是(0,0)区域，即初始点为(0,0)。将其放入OPEN表，后取出，判断其是否为目标，当答案为否时，将其放入CLOSED表，并对其进行子节点扩展，得下列的OPEN和CLOSED表。,OPEN表,CLOSED表,接着，判断此时的OPEN表是否为空，若不是，则将OPEN表末端的第一个节点(0,1)提出来，判断其是否为目标，若不是，则将其放入CLOSED表中，并对其进行扩展，得下表,OPEN表,CLOSED表,取OPEN表最末端的节点(1,1)，判断其是否为目标，若不是，则将其放入CLOSED表，并对其进行扩展，得到的子节点放入OPEN表的末端，得如下,OPEN表,CLOSED表,再取OPEN表最末端的节点(1,0)，判断其是否为目标，若不是，则将其放入CLOSED表，并对其进行扩展，得到的子节点也放入OPEN表的末端，得如下,OPEN表,CLOSED表,又一次取OPEN表最末端的节点(2,0)，判断其是否为目标，若不是，则将其放入CLOSED表，并对其进行扩展，由于该节点没有子节点，所以没有新的节点加入OPEN表，如下示：,OPEN表,CLOSED表,对OPEN表最末端的节点(2,1)，判断其是否为目标，若不是，则将其放入CLOSED表，并对其进行扩展，其子节点放入OPEN表的末端，如下示：,OPEN表,CLOSED表,取OPEN表最末端的节点(2,2)，判断其是否为目标，是，则搜索成功，并退出。如下示：,OPEN表,CLOSED表,(0,0),(0,1),(0,2),(1,1),(2,1),(1,2),(1,0),(2,2),1,2,3,4,5,搜索到的路径如粗线所示,整个搜索过程如下图所示,5.横向搜索,定义 以接近起始节点的程度逐层扩展节点的搜索方法(breadth-first search)。特点 一种高代价搜索，但若有解存在，则必能找到它。,算法 这种搜索是逐层进行的；在对下一层的任一节点进行搜索之前，必须搜索完本层的所有节点。横向搜索算法是一种“先进先出”的算法。,举例：迷宫问题,0,1,2,x,0,1,2,y,将初始点(0,0)放入OPEN表，然后取出，判断其是否为目标，若为否时，将其放入CLOSED表，并对其进行子节点扩展，得OPEN和CLOSED表。,OPEN表,CLOSED表,接着，判断此时的OPEN表是否为空，若不是，则将OPEN表上的第一个节点(0,1)提出来，判断其是否为目标，若不是，则将其放入CLOSED表中，并对其进行扩展，得到的子节点加入OPEN表，如下,OPEN表,CLOSED表,取OPEN表上的第一个节点(0,2)，判断其是否为目标，若不是，则将其放入CLOSED表，并对其进行扩展，由于其没有子节点，因此没有新的子节点加入OPEN表，如下,OPEN表,CLOSED表,再取OPEN表最上端的节点(1,1)，判断其是否为目标，若不是，则将其放入CLOSED表，并对其进行扩展，得到的子节点放入OPEN表的末端，如下,OPEN表,CLOSED表,取OPEN表最上端的节点(1,2)，判断其是否为目标，若不是，则将其放入CLOSED表，并对其进行扩展，由于该节点没有子节点，所以没有新的节点加入OPEN表，如下示：,OPEN表,CLOSED表,对OPEN表最上端的节点(2,0)，判断其是否为目标，若不是，则将其放入CLOSED表，并对其进行扩展，其子节点放入OPEN表的末端，如下示：,OPEN表,CLOSED表,取OPEN表最上端的节点(1,0)，判断其是否为目标，若不是，则将其放入CLOSED表，并对其进行扩展，将得到的子节点放入OPEN表的末端，如下示：,OPEN表,CLOSED表,取OPEN表最上端的节点(2,2)，判断其是否为目标，是，则搜索成功，退出。,OPEN表,CLOSED表,(0,0),(0,1),(0,2),(1,1),(2,1),(1,2),(1,0),(2,2),1,2,3,4,5,(2,0),6,7,8,搜索到的路径为粗线所示,整个搜索过程如下图所示,举例：,假设A、B、C、D、E各个城市之间旅费如下图所示。某人想从城市A出发游览各城市一遍，而所用费用最少。试编程序输出结果。,从A点开始依次展开得到AB、AC、AD、AE四个新结点（第二层结点），当然每个新结点要记录下其距离；2、再次以AB展开得到ABC、ABD、ABE三个新结点（第三层结点），而由AC结点可展开得到ACB、ACD、ACE三个新结点，自然AD可以展开得到ADB、ADC、ADE，AE可以展开得到AEB、AEC、AED等新结点，对于每个结点也须记录下其距离；3、再把第三层结点全部展开，得到所有的第四层结点：ABCD、ABCE、ABDC、ABDE、ABEC、ABEDAEDB、AEDC，每个结点也需记录下其距离；4、再把第四层结点全部展开，得到所有的第五层结点：ABCDE、ABCED、AEDBC、AEDCB，每个结点也需记录下其距离；5、到此，所有可能的结点均已展开，而第五层结点中最小的那个就是题目的解了。由上可见，这种算法也是把所有的可能路径都列出来再找最短的那条，显而易见这也是一种很费时的算法。,举例：,八数码魔方,（目标状态）,（初始状态）,1,2,3,8,4,4,1,2,3,8,4,6,7,8,9,10,11,12,13,1,2,3,8,4,5,6,7,5,6,7,5,6,7,1,2,3,4,5,八数码魔方的横向搜索树,1,3,4,5,6,1,2,3,8,4,5,6,7,23,24,25,26,27,2,6,7,8,22,14,15,16,17,18,19,20,21,4,28,29,30,31,1,2,3,8,4,5,6,7,1,2,3,8,4,5,6,7,1,2,3,8,4,5,6,7,1,2,3,8,4,5,6,7,32,1,3,4,5,6,2,6,7,8,38,1,2,3,8,4,5,6,7,39,扩展26个节点，共生成46个节点之后，才得到目标,均一代价搜索,是横向搜索的一种推广，不是沿着等长度路径断层进行扩展，而是沿着均一代价路径断层进行扩展。搜索树中每条连接弧线上的有关代价,表示时间、距离等花费。若所有连接弧线具有相等代价，则简化为横向搜索算法。,迷宫问题如下，F是入口，B是出口，试采用均一代价搜索算法进行求解。,举例：迷宫问题,0,1,2,3,x,1,2,3,y,F,G,H,E,C,A,D,B,2,2,2,4,1,1,1,1,将初始点F及其代价0放入OPEN表，然后取出，判断其是否为目标，若为否时，将其放入CLOSED表，对其进行子节点扩展，并计算相应的代价，得OPEN和CLOSED表。,OPEN表,CLOSED表,接着，判断此时的OPEN表是否为空，若不是，则将OPEN表上的第一个节点G提出来，判断其是否为目标，若不是，则将其放入CLOSED表中，并对其进行扩展，得到的子节点及其代价，按递增的顺序加入OPEN表，如下,OPEN表,CLOSED表,取OPEN表上的第一个节点E，判断其是否为目标，若不是，则将其放入CLOSED表，并对其进行扩展，将子节点加入OPEN表，并按代价的递增顺序对OPEN表重新排序，如下,OPEN表,CLOSED表,再取OPEN表最上端的节点H，判断其是否为目标，若不是，则将其放入CLOSED表，并对其进行扩展，由于该节点没有子节点，因此没有新的子节点加入到OPEN表，如下,OPEN表,CLOSED表,取OPEN表最上端的节点C，判断其是否为目标，若不是，则将其放入CLOSED表，并对其进行扩展。其子节点中有个A已经出现在OPEN表，通过比较新旧代价，修改了A的指针。OPEN表经过重新排序后,OPEN表,CLOSED表,对OPEN表最上端的节点A，判断其是否为目标，若不是，则将其放入CLOSED表，并对其进行扩展，其子节点经过重新排序后放入OPEN表，如下示：,OPEN表,CLOSED表,取OPEN表最上端的节点D，判断其是否为目标，若不是，则将其放入CLOSED表，并对其进行扩展，由于其没有子节点，因此OPEN表如下：,OPEN表,CLOSED表,取OPEN表最上端的节点B，判断其是否为目标，是，则搜索成功，退出。,OPEN表,CLOSED表,注：每个节点小括号内的数值表示走到该节点所需付出的代价。,F(0),G(1),H(3),E(2),C(3),A(64),D(5),B(6),1,2,3,4,5,6,7,8,搜索到的路径为粗线所示,举例：推销员旅行问题,假设A、B、C、D、E各个城市之间旅费如下图所示。某人想从城市A出发游览各城市一遍，而所用费用最少。试编程序输出结果。,均一代价搜索法思路：,1、从A点开始依次展开得到AB（7）、AC（3）、AD（10）、AE（15）四个新结点，把第一层结点A标记为已展开，并且每个新结点要记录下其距离（括号中的数字）；2、把未展开过的AB、AC、AD、AE四个结点中距离最小的一个展开，即展开AC（3）结点，得到ACB（8）、ACD（16）、ACE（13）三个结点，并把结点AC标记为已展开；3、再从未展开的所有结点中找出距离最小的一个展开，即展开AB（7）结点，得到ABC（12）、ABD（20）、ABE（19）三个结点，并把结点AB标记为已展开；4、再次从未展开的所有结点中找出距离最小的一个展开，即展开ACB（8）结点；5、每次展开所有未展开的结点中距离最小的那个结点，直到展开的新结点中出现目标情况（结点含有5个字母）时，即得到了结果。,算法分析：,由上可见，均一代价搜索法并没有象横向搜索一样展开所有结点，只是根据代价最小的原则，每次展开距离A点最近的那个结点，反复下去即可最终得到答案。虽然中途有时也展开了一些并不是答案的结点，但这种展开并不是大规模的，不是全部展开，因而耗时要比横向搜索小得多。,