按图搜索

【⼈⼯智能】1.问题求解：状态空间图和盲⽬搜索

什么是问题求解？问题求解可以理解为利⽤知识，尽可能有效的找到问题的解，或者最优解的过程，主要包括：

1）问题描述⽅法：状态空间法，与或树表⽰法；

2）搜索⽅法（搜索策略）：盲⽬搜索，启发式搜索。

⼀、状态空间问题描述

1.问题表⽰

1）初始状态集合：当前所处的环境的集合。

2）操作符集合：把⼀个问题从⼀个状态变换为另⼀个状态的动作集合。

3）⽬标测试函数：确定⼀个状态是否是⽬标。

4）路径费⽤函数：从⼀个状态到另⼀个状态的代价等。

2.状态空间法

状态空间法是以状态和算符为基础来表⽰和求解问题的。

1）状态：状态⽤于描述问题求解过程中任⼀时刻状况的数据结构，⽤⼀组变量的有序组合表⽰：SK=(SK0，SK1，…)

2）操作符（算符）：把问题从⼀种状态变换为另⼀种状态的⼿段。⾛步、过程、规则、数学算⼦、运算符号或逻辑符号。

3）状态空间：（S，F，G）表⽰，其中S为初始状态的集合，F是操作符的集合；G是⽬标状态的集合。

4）状态空间图：⽤状态标识节点，⽤操作标识有向边，有向边的⽅向由操作的施加对象状态指向操作的结果状态。

3.⼆阶汉诺塔问题的表⽰

⼆阶汉诺塔问题：设有1、2、3三根钢针，在1号钢针上穿有A、B两个⾦⽚，A⼩于B，A位于B的上⾯。要求把这两个⾦⽚全部移到另⼀根

钢针上，⽽且规定每次只能移动⼀⽚，任何时刻都不能使B位于A的上⾯。

1）状态：SK=（SK0，SK1），SK0表⽰A所在的钢针号，SK1表⽰B所在的钢针号：

2）操作：A(i,j)表⽰把⾦⽚A从i号钢针移到j号钢针；B(i,j)表⽰把⾦⽚B从i号钢针移到j号钢针。

3）组成状态空间图：

⼆、盲⽬搜索

1.什么是搜索

⼈⼯智能所要解决的问题⼤部分是结构不良或⾮结构化的问题，对这样的问题⼀般不存在成熟的求解算法可供利⽤，⽽只能是利⽤已有的知

识⼀步步地摸索着前进。

搜索就是：根据实际问题，不断寻找可⽤知识，确定推理路线，从⽽构造⼀条代价尽可能的少的路线，⽽问题⼜能得到圆满的解决。

2.什么是盲⽬搜索

预先规定好控制策略进⾏搜索，在搜索过程中获取的中间信息不影响或改变控制策略，由于搜索总是按预先规定的路线进⾏，没有考虑到问

题本⾝的特性，所以这种搜索具有盲⽬性，效率不⾼，不便于复杂问题的求解。

尽管盲⽬搜索的性能不如启发式搜索，但由于启发式搜索需要抽取与问题本⾝有关的特征信息，⽽这种特征信息的抽取往往⼜⽐较困难，因

此盲⽬搜索仍不失为⼀种有⽤的搜索策略。

3.问题求解的性能

1）完备性：是否能找到解；

2）最优性：找到最优解；

3）时间复杂度：找到⼀个解花费时间；

4）空间复杂度：需多少存储空间。

4.⼀般的图搜索

1）基本思想：

先把问题的初始状态作为当前扩展节点对其进⾏扩展，⽣成⼀组⼦节点，然后检查问题的⽬标状态是否出现在这些⼦节点中。若出现，则搜

索成功，找到了该问题的解；若没出现，则再按照某种搜索策略从已⽣成的⼦节点中选择⼀个节点作为当前扩展节点。重复上述过程，直到

⽬标状态出现在⼦节点中或者没有可供扩展的节点为⽌。

2）数据结构：

Open表：

⽤于存放刚⽣成的节点，由于这些节点还没有进⾏扩

展，因此也称为未扩展节点表；

Clod表：

⽤于存放已经扩展的节点，因此Clod表也称为已扩展节

点表。

3）搜索过程：

①把初始节点S0放⼊OPEN表，并建⽴⽬前只包含S0的图，记为G。

②检查OPEN表是否为空，若为空则问题⽆解，退出。

③把OPEN表的第⼀个节点取出放⼊CLOSED表，并记该节点为节点n。

④考察节点n是否为⽬标节点。若是，则求得了问题的解，退出。

⑤扩展节点n，⽣成⼀组⼦节点。把其中不是节点n先辈的那些⼦节点记作集合M，并把这些⼦节点作为节点n的⼦节点加⼊G中。

⑥针对M中⼦节点的不同情况，分别进⾏如下处理：

A、对于那些未曾在G中出现过的M成员设置⼀个指向⽗节点（即节点n）的指针，并把它们放⼊OPEN表。

B、对于那些先前已在G中出现过的M成员，确定是否需要修改它指向⽗节点的指针。（计算是否需要修改，涉及到节点和路径的代价，每

次计算都要从S0算到⽬标节点）

C、对于那些先前已在G中出现并且已经扩展了的M成员，确定是否需要修改其后继节点指向⽗节点的指针。（对于C这种情况，针对的是已

扩展节点的后继节点不只⼀个⽗节点时，到后继节点的总代价可能因为B中修改⽽变化。即对于C这种情况，要先进⾏B的修改。）

⑦按某种搜索策略对OPEN表中的节点进⾏排序。

⑧转第（2）步。

5.关于⼀般图搜索的说明

1）状态空间搜索有通⽤性，之后的各种搜索策略都是特例，主要体现在Open表中节点排序不同，另外对于⼴搜这种⼀层⼀层的搜索，代

价相同的情况下，也不涉及指针的修改。

2）⼀个节点经过⼀个算符只⽣产⼀个⼦节点，但是因为对于这个节点来说有很多个算符，此时就会有⼀组⼦节点，其中就有可能有⽗节

点，祖⽗节点等，此时不能将这些先辈节点作为当前扩展节点的⼦节点。除此之外的节点记为集合M，加⼊图G中。

3）依据代价修改指针（表中的⽗节点）。

4）注意：搜索得到的图G和状态空间图时不⼀样的，由搜索图中所有节点以及反向指针构成的集合是搜索树。

5）到⽬标节点的反向指针构成路径。

6）盲⽬搜索仅适⽤于状态空间是树状结构的问题，因此对于盲⽬搜索⽽⾔，不会出现修改指针的情况，每个⼦节点都是第⼀次出现的。

三、⼴度优先搜索

1.基本思想

从初始节点S0开始，逐层地对节点进⾏扩展并考察它是否为⽬标节点，在第n层的节点没有全部扩展并考察之前，不对第n+1层的节点进⾏

扩展。OPEN表中的节点总是按进⼊的先后顺序排列，先进⼊的节点排在前⾯，后进⼊的排在后⾯。

2.搜索过程

①把初始节点S0放⼊OPEN表。

②如果OPEN表为空，则问题⽆解，退出。

③把OPEN表的第⼀个节点（记为节点n）取出放⼊CLOSED表。

④考察节点n是否为⽬标节点。若是，则求得了问题的解，退出。

⑤若节点n不可扩展，则转第②步。

⑥扩展节点n，将其⼦节点(不含先辈节点)放⼊OPEN表的尾部，并为每⼀个⼦节点都配置指向⽗节点的指针，然后转第②步。

3.优劣

①缺点：盲⽬性较⼤，当⽬标节点距离初始节点较远时将会产⽣许多⽆⽤节点，搜索效率低。⽽且写出Open表可以发现，若⽬标节点已经

被扩展出来，但是没有判断（判断和扩展时在将节点放⼊Clo表时进⾏的），在执⾏到判断⽬标节点的时候，多余已经执⾏了很多扩展的

操作。

②优点：只要问题有解，⽤⼴度优先搜索总可以得到解，⽽且得到的是路径最短的解。

四、深度优先搜索

1.基本思想

从初始节点S0开始扩展，若没有得到⽬标节点，则选择最后产⽣的⼦节点进⾏扩展，若还是不能到达⽬标节点，则再对刚才最后产⽣的⼦

节点进⾏扩展，⼀直如此向下搜索。当到达某个⼦节点，且该⼦节点既不是⽬标节点⼜不能继续扩展时，才选择其兄弟节点进⾏考察。

2.搜索过程

①把初始节点S0放⼊OPEN表。

②如果OPEN表为空，则问题⽆解，退出。

③把OPEN表的第⼀个节点（记为节点n）取出放⼊CLOSED表。

④考察节点n是否为⽬标节点。若是，则求得了问题的解，退出。

⑤若节点n不可扩展，则转第②步。

⑥扩展节点n，将其⼦节点放⼊到OPEN表的⾸部，并为其配置指向⽗节点的指针，然后转第②步。

3.深度优先局限性

深度优先相当于对优先某⼀个分⽀进⾏搜索，如果这个分⽀上没有解，或者时⽆限分⽀，那么就很难得到解或者根本得不到解，解得到了解

有可能不是最优解。并不是⼀种完备的搜索算法。

4.有界深度优先搜索

1）对深度优先搜索引⼊搜索深度的界限（设为dm)，当搜索深度达到了深度界限，⽽尚未出现⽬标节点时，就换⼀个分⽀进⾏搜索。搜索

过程如下：

①把初始节点S0放⼊OPEN表中，置S0的深度d（S0)=0。

②如果OPEN表为空，则问题⽆解，退出。

③把OPEN表中的第⼀个节点（记为节点n）取出放⼊CLOSED表。

④考察节点n是否为⽬标节点。若是，则求得了问题的解，退出。

⑤如果节点n的深度d(n)=dm，则转第②步。

⑥若节点n不可扩展，则转第②步。

⑦扩展节点n，将其⼦节点放⼊OPEN表的⾸部，并为其配置指向⽗节点的指针,并指定每⼀个⼦节点的深度为d(n)+1然后转第②步。

2）优化：

dm的选择：

先任意给定⼀个较⼩的数作为dm，然后进⾏上述的有界深度优先搜索，当搜索达到了指定的深度界限dm仍未发现⽬标节点，并且

CLOSED表中仍有待扩展节点时，就将这些节点送回OPEN表。

最优解：

为找到最优解，可增设⼀个表（R)，每找到⼀个⽬标节点后，就把它放⼊到R的前⾯，并令dm等于该⽬标节点所对应的路径长度，然后继

续搜索。由于后求得的解的路径长度不会超过先求得的解的路径长度，所以最后求得的解⼀定是最优解。

例如如果S3和S5是⽬标节点，找到S3后，取Dm=3，R表中增加S3，继续搜索；找到S5，取Dm=2，R表中增加S5，解为S5。

五、代价树搜索

1.代价计算

1）代价树：边上标有代价（或费⽤）的树称为代价树。

2）代价树中，⽤c（x1，x2）表⽰从⽗节点x1到⼦节点x2的代价。

3）⽤g（x）表⽰从初始节点S0到节点x的代价。

4）代价计算公式：g（x2)=g（x1)+c（x1，x2)

2.代价树的⼴搜和深搜

代价树的搜索也只是Open表内的排序不⼀样，要先计算代价，然后根据⼀定规则进⾏排序。

1）⼴度搜索：OPEN表中的节点在任⼀时刻都是按其代价从⼩⾄⼤排序的，代价⼩的节点排在前⾯，代价⼤的节点排在后⾯，⽽不管节点

在代价树中处于什么位置上。

2）深度搜索：刚扩展出的⼦节点中选⼀个代价最⼩的节点送⼊CLOSED表进⾏考察