人工智能第1章盲目搜索

1、第1章 搜索问题 一种在图中寻找路径的方法。 2831476581324765八数码魔魔方1.1搜索问题题知识的的表示方方法初始节点点S0目标节点点Sg状态空间间表示状态（State）的基本本概念状态(state)是为描述述某类不不同事物物间的差差别而引引入的一一组最少少变量q0，q1，qn的有序集集合，其其矢量形形式如下下：Q =q0,q1,qnT(1)式中每个个元素qi(i=0,1，n)为集合的的分量，称为状状态变量量。给定定每个分分量的一一组值就就得到一一个具体体的状态态，如Qk= q0k,q1k,，qnkT(2)例如，八八数码魔魔方中，所有初初始节点点S0构成初始始节点状状态集合合Q；

2、所有目目标节点点Sg构成目标标节点状状态集合合Q。当Q中每个分分量取定定一个值值时，就就得到一一个具体体的状态态集合，如例子子中的就就是是Q0， 而就就是是Qk。2831476581324765问题求解解技术主主要是两两个方面面：问题的表表示求解的方方法问题的状状态空间间(statespace)是一个表表示该问问题全部部可能状状态及其其关系的的图，它它包含三三种说明明的集合合，即所所有可能能的问题题初始状状态集合合S、算符集集合F以及目标标状态集集合G。因此，可把状状态空间间记为三三元状态态(S，F，G)。算符：使问题题从一种种状态变变化为另另一种状状态的手手段称为为操作符符或算符符。操作作符

3、可为为走步、过程、规则、数学算算子、运运算符号号或逻辑辑符号等等。例如，例例子中的的八数码码魔方问问题就可可以用三三元状态态空间表表示为（S0，F，Sg）其中，S0代表初始始状态，Sg代表目标标状态，而F就是所有有能将初初始状态态变化为为目标状状态的算算符集合合。举例：012x012y迷宫问题题整个迷宫宫问题的的知识表表示是如如书上第第10页的图2.3，这是一一种状态态图知识识表示法法。问题是：机器人人位于迷迷宫入口口(0，0)处，如何何到达迷迷宫的出出口(2，2)。解：问题题空间的的初始状状态是节节点(0,0),而目标状状态是节节点(2,2)。从图2.3可见，从从(0,0)到(2,2)需经过

4、(U，R，R，U)算符集合合的操作作，因此此本问题题的解用用三元状状态集合合表示为为：(0,0),(U,R,R,U),(2,2)与图有关关的术语语状态空间间图由节点(不一定是是有限的的节点)及连接节节点的分分枝的集集合构成成。有限节点点图节点数目目有限的的图称为为有限节节点图。有向图一对节点点用分枝枝线连接接起来，从一个个节点指指向另一一个节点点。这种种图叫做做有向图图。始节节点叫父父节点或或双亲节节点，终终节点叫叫子节点点。扩展求解父父节点的的所有子子节点，叫做扩扩展。路径在一系系列节点点n1,n2,nm中，从n1开始，ni总有分枝枝连接ni+1，称从n1到nm之间的分分枝集合合是路径径。路

5、径径中不包包含两个个及以上上相同的的分枝，如果n1和nm是同一个个节点，则称这这种路径径为闭路路。不构构成闭路路的称为为树。在用状态态空间图图来表示示问题时时，对问问题的求求解就是是求出从从初始节节点到目目标节点点的路径径。1.2图搜索策策略1.图搜索的的定义一种计算算机在状状态图中中寻找路路径的方方法。2.CLOSED表的引入入编号节点号父节点号CLOSED表(记录扩展展过的节节点)OPEN表的引入入节点号父节点号OPEN表(记录待扩扩展的节节点)举例：八八数码魔魔方例子子中OPEN表变化过过程节点号父节点号S0空AS0BS0CS0DS0EAFACLOSED表变化过过程编号节点号父节点号0S

6、0空1AS02BS0图搜索的的一般过过程(1)建立一个个只含有有起始节节点S的搜索图图G，把S放到一个个叫做OPEN表的未扩扩展节点点表中。(2)建立一个个叫做CLOSED的已扩展展节点表表，其初初始为空空表。(3)LOOP：若OPEN表是空表表，则失失败退出出。(4)选择OPEN表上的第第一个节节点，把把它从OPEN表移出并并放进CLOSED表中。称称此节点点为节点点n。(5)若n为一目标标节点，则有解解并成功功退出，此解是是追踪图图G中沿着指指针从n到S这条路径径而得到到的(指针将在在第7步中设置置)。图搜索的的一般过过程(6)扩展节点点n，同时生成成不是n的祖先的的那些后后继节点点的集合

7、合M。把M的这些成成员作为为n的后继节节点添入入图G中。(7)对那些未未曾在G中出现过过的(既未曾在在OPEN表上或CLOSED表上出现现过的)M成员设置置一个通通向n的指针。把M的这些成成员加进进OPEN表。对已已经在OPEN或CLOSED表上的每每一个M成员，确确定是否否需要更更改通到到n的指针方方向。对对已在CLOSED表上的每每个M成员，确确定是否否需要更更改图G中通向它它的每个个后裔节节点的指指针方向向。(8)按某一任任意方式式或按某某个探试试值，重重排OPEN表。(9)GOLOOP。开始把S放入OPEN表OPEN表为空表表？把第一个节节点(n)从OPEN表移至CLOSED表n为目标

8、节节点吗？把n的后继节节点放入入OPEN表的末端端，提供供返回节节点n的指针修改指针针方向重排OPEN表失败成功图搜索一一般过程程的框图图是是否否1.3无信息图图搜索过过程深度优先先搜索（纵向搜搜索）宽度优先先搜索（横向搜搜索）均一代价价搜索1.深度优先先搜索定义首先扩展展最新产产生的(即最深的的)节点。深度相等等的节点点可以任任意排列列。这种种盲目(无信息)搜索叫做做深度优先先搜索或纵向搜索索。 特点扩展最深深的节点点的结果果使得搜搜索沿着着状态空空间某条条单一的的路径从从起始节节点向下下进行下下去；只只有当搜搜索到达达一个没没有后裔裔的状态态时，它它才考虑虑另一条条替代的的路径。为了防止止

9、搜索过过程沿着着无益的的路径扩扩展下去去，往往往给出一一个节点点扩展的的最大深深度深度界限限。深度优先先搜索算法法是一种种“后进进先出”的算法法。开始把S放入OPEN表OPEN表为空表表？把第一个个节点(n)从OPEN表移至CLOSED表扩展n，把其后裔放入入OPEN表的前头头失败成功深度优先先搜索算法法框图是否是否是否有后后继节点点为目标节节点？S是否为目目标节点点？成功是否八数码魔魔方的深度优先先搜索树2.宽度优先先搜索定义以接近起起始节点点的程度度逐层扩扩展节点点的搜索索方法(breadth-firstsearch)，这种盲盲目(无信息)搜索叫做做宽度优优先搜索索或横向向搜索。 特点一种

10、高代代价搜索索，但若若有解存存在，则则必能找找到它。算法这种搜索索是逐层层进行的的；在对对下一层层的任一一节点进进行搜索索之前，必须搜搜索完本本层的所所有节点点。宽度优先先搜索算法法是一种种“先进进先出”的算法法。开始把S放入OPEN表OPEN表为空表表？把第一个个节点(n)从OPEN表移至CLOSED表扩展n，把n的后继节节点放入入OPEN表的末端端，提供供返回节节点n的指针失败宽度优先先搜索算法框图图是否把第一个节节点(n)从OPEN表移至CLOSED表n为目标节节点吗？成功是否举例：八数码魔魔方1238456712384567（目标状状态）（初始状状态）12384567123841238

11、45674123856712384123845671238456712384567678910111213123845675675671123845671238456712384567123845672345八数码魔魔方的宽度优先先搜索树1345612384567123845671238456712384567123845672324252627123678221238456712384567123845671238456712384567123845671238456714151617181920211238456742829303112384567123845671238456712384

12、5673213456123678381238456739扩展26个节点，共生成46个节点之之后，才才得到目目标3.均一代价价搜索是横向搜搜索的一一种推广广，不是是沿着等等长度路路径断层层进行扩扩展，而而是沿着着均一代代价路径径断层进进行扩展展。搜索树中中每条连连接弧线线上的有有关代价价,表示时间间、距离离等花费费。若所有连连接弧线线具有相相等代价价，则简简化为横横向搜索索算法。均一代价价搜索中中的几个个记号：起始节点点记为S；从节点i到它的后后继节点点j的连接弧弧线代价价记为c(i，j)；从起始节节点S到任一节节点i的路径代代价记为为g(i)。开始把S放入OPEN表OPEN表为空表表？把第一个

13、个节点(n)从OPEN表移至CLOSED表扩展n，把n的后继节节点放入入OPEN表的末端端，提供供返回节节点n的指针失败均一代价价搜索算算法框图图是否把第一个节节点(n)从OPEN表移至CLOSED表n为目标节节点吗？成功是否按g(i)值由小到到大的顺顺序重排排OPEN表均一代价价搜索法法思路：1、 从A点开始依依次展开开得到AB（7）、AC（3）、AD（10）、AE（15）四个新结结点，把把第一层层结点A标记为已已展开，并且每每个新结结点要记记录下其其距离（括号中中的数字字）；2、 把未未展开过过的AB、AC、AD、AE四个结点点中距离离最小的的一个展展开，即即展开AC（3）结点，得得到AC

14、B（8）、ACD（16）、ACE（13）三个结点点，并把把结点AC标记为已已展开；3、 再从从未展开开的所有有结点中中找出距距离最小小的一个个展开，即展开开AB（7）结点，得得到ABC（12）、ABD（20）、ABE（19）三个结点点，并把把结点AB标记为已已展开；4、 再次次从未展展开的所所有结点点中找出出距离最最小的一一个展开开，即展展开ACB（8）结点；5、 每次次展开所所有未展展开的结结点中距距离最小小的那个个结点，直到展展开的新新结点中中出现目目标情况况（结点点含有5个字母）时，即即得到了了结果。算法分析析：由上可见见，均一一代价搜搜索法并并没有象象横向搜搜索一样样展开所所有结点点，只是是根据代代价最小小的原则则，每次次展开距距离A点最近的的那个结结点，反反复下去去即可最最终得到到答案。虽然中中途有时时也展开开