人工智能第五章.ppt

人工智能第五章
何确定推理路线，才能使在付出尽量少的代价的前提下把问题圆满解决。
如果存在多条路线可实现对问题求解，那就又存在这样的问题 ，即如何从这多条求解路线中，选出求解代价最小的一条，以提高求解程序的运行效率。
改通向它们后继节点的指针。
Step8：按某一任意方式或按某种策略重排OPEN表中节点的顺序。
Step9：转Step3。
搜索过程的流程图如图1所示。
*
Y
N
N
Y
开 始
初始化：把S0放入OPEN中，CLOSED表置空
把OPEN表中的第一个节点(n)移至CLOSED表中
若n的后继节点未曾在搜索图G中出现，则将其放入OPEN表的末端，并提供返回节点n的指针中。
根据后继节点在搜索图G中的出现情况修改指针方向
重排OPEN表
失败，退出
成功，退出
OPEN为空表？
n为目标节点吗？
图1 状态空间的搜索过程框图
*
这一搜索算法具有通用性。以后讨论的各种搜索策略都可以看作是它的一个特例。各种策略的主要区别就在于Step8对OPEN表中的节点排序的算法不同。在Step8中，对OPEN表中的节点排序时，主要希望从未扩展节点中选出一个最有希望的节点作为Step4扩展来用。
若这时的排序是任意的或者是盲目的，则搜索即为盲目搜索；如果是按某种启发信息或准则进行排序，则其就是启发式搜索。
搜索图：在搜索过程中，生成了一个图G，它是问题状态空间图的一部分，称为搜索图。
搜索树：由搜索图G中的所有节点及Step7设置的指向父节点的反向指针，所构成的集合T称为搜索树。
*
搜索图G中，除初始节点S0外的每个节点，都有一个指向G中一个父辈节点的指针，该父辈节点就定为搜索树中对应节点的唯一父辈节点。
搜索解：在搜索过程中，当某个被选作扩展的节点，是目标节点时（在Step5），则就找到了问题的一个解。所找到的解就是从初始节点S0到目标节点路径上的算符所构成的序列。
而路径则是通过目标节点按Step7设置的指针指向初始节点回溯而得到的。如果在搜索中一直找不到目标节点，而且OPEN表中又不再具有可供扩展的节点，则搜索失败，在Step3退出结束。
这样的搜索过程实际上就是问题的求解过程。在利用状态空间搜索法求解问题时，并不是将整个问题的状态空间图全部输入计算机，而是只存入与问题解有关的
*
部分状态空间图。这种部分状态空间图是在搜索过程中生成的，并且每前进一部，都要检查是否到达目标节点，这样就可以尽量地少生成与问题无关地状态，从而提高了解题效率，节省了存储空间。
二．宽度优先搜索策略
宽度优先搜索又称为广度优先搜索，是一种盲目搜索。其基本思想如下：
从初始节点开始，逐层对节点进行依次扩展，并考察它是否为目标节点，在对下层节点进行扩展（或搜索）之前，必须完成对当前层的所有节点的扩展（或搜索）。
在搜索过程中，未扩展节点表OPEN中的节点排序准则是：
*
先进入的节点排在前面，后进入的节点排在后面。其搜索过程如图2所示。
图2 宽度优先搜索过程
起始节点
*
Step6：对节点n进行扩展，将它的所有后继节点放入OPEN表的末端，并为这些后继节点设置一个指向父节点n的指针，然后转Step2。
算法2：状态空间图的宽度优先搜索算法
Step1：把初始节点S0放入OPEN表中。
Step2：如果OPEN表是空表，则没有解，失败退出。否则继续。
Step3：把OPEN表中的第一个节点（记为节点n）移出，并放入CLOSED表中。
Step4：判断节点n是否为目标节点。若是，则求解结束，并用回溯法找出解的路径，退出；否则继续执行Step5。
Step5：若节点n不可扩展，转Step2；否则继续执行Step6。
*
宽度优先算法的流程图如图3所示。
Y
Y
N
N
Y
开 始
把S0放入OPEN
把OPEN表中的第一个节点(n)移出放入CLOSED表
扩展节点n，将其后继节点放入OPEN表的末端
为每个后继节点配置指向n的指针
失败，退出
回溯求解路径
OPEN空表？
n为目标节点吗？
节点n可扩展吗？
N
成功，退出
图3 宽度优先算法框图
*
例1 八数码难题：设在3*3的一个方格棋盘上，摆放着8个数码1、2、3、4、5、6、7、8，有一个方格是空格，其初始状态如图4(a)所示，要求对空格执行下列的操作（或算符）：
空格左移，空格上移，空格右移，空格下移
使八个数据最终按图4(b)的格式摆放，如图4(b)称为目标状态Sg。要求寻找从初始状态到目标状态的路径。
2 8 3
1 4
7