状态空间搜索

第三章状态空间搜索人工智能（AI）的第一个大成就是发展了能够求解问题的下棋程序。通过研究下棋程序，人们发展了人工智能中的搜索及问题归约等基本技术。问题求解：问题表示、搜索过程（模拟人类求解某些问题的过程）§3.1问题与问题空间一、问题状态空间的构成1.状态：描述问题求解过程中不同时刻状况的数据结构。用一组变量的有序集合表示：

Q=（)

称为状态变量2.算符：引起状态中某些分量发生变化，从而使问题由一个状态变为另一个状态的操作称为算符。3.状态空间：表示一个问题的全部状态及一切可用算符构成的集合。表示如下：（S，F，G）S：所有可能的问题初始状态集合F：算符（操作符）集合G：目标状态集合4.问题的解：从问题的初始状态集合S出发，经过一系列算符运算，到达目标状态。二、利用状态空间表示问题的步骤定义状态的描述形式把问题的所有可能状态都表示出来，并确定出问题的初始状态集合描述和目标状态集合描述。3.定义一组算符。例：二阶Hanoi塔问题定义问题状态的描述形式：用所定义的状态描述形式把所有可能的状态都表示出来，并确定初始状态集合与目标状态集合

S0=（1，1）S1=（1，2）S2=（1，3）S3=（2，1）S4=（2，2）S5=（2，3）S6=（3，1）S7=（3，2）S8=（3，3）初始状态集合：S={S0}目标状态集合：G={S8}

定义一组算符F：A（i,j)B(i,j)共12个：A（1，2）A（1，3）A（2，1）A（2，3）A（3，1）A（3，2）三、求解过程将适用的算符作用于初始状态，以产生新的状态；然后把另一些使用的算符作用于新的状态；继续下去，直到产生目标状态为止。四、状态图示法图：节点、弧线例：1,13,13,22,22,13,32,31,31,2A(1,2)B(1,3)A(2,3)§3.2搜索的概念及种类一、搜索的概念根据问题的实际情况，按照一定的策略或规则，从知识库中寻找可利用的知识，从而构造出一条使问题获得解决的推理路线的过程，称为搜索。找到一条推理路线时间和空间复杂度最小二、搜索种类盲目搜索：无信息搜索。启发式搜索§3.3盲目搜索策略一、图搜索策略扩展：用合适的算符对某个节点操作生成一组后继节点。状态节点父节点编号状态节点父节点OPEN表结构（未扩节点）

CLOSED表结构（已扩节点）状态空间图的一般搜索算法建立一个只含有初始节点S0的搜索图G，把S0放入OPEN表中。建立CLOSED表，且置为空表。判断OPEN表是否为空，若为空，则问题无解，退出。选择OPEN表中的第一个节点，把它从OPEN表中移出并放入CLOSED表中，将此节点记为节点n。考察节点n是否为目标节点，若是，则问题有解，并成功退出。问题的解即可从图G中沿着指针从n到S0的这条路径得到。扩展节点n生成一组不是n的祖先的后继节点，并将它们记作集合M，将M中的这些节点作为n的后继节点加入到图G中。对那些未曾在G中出现过的（未在OPEN或CLOSED表中出现过）M中的节点，设置一个指向父节点（即n节点）的指针，并把这些节点加入到OPEN表中；对于已在G中出现过的M中的那些节点，确定是否需要修改指向父节点（n节点）的指针；对于那些先前已在G中出现并且已在CLOSED表中的那些M中的节点，确定是否需要修改指向它们后继节点的指针。按某一任意方式或按某种策略重排OPEN表中节点的顺序。转第3步开始初始化：把S0放入OPEN表，CLOSED表，置空。OPEN为空表？把OPEN表中第一个节点（n）移至CLOSED表中N为目标节点吗？若n的后继节点未曾在G中出现，则将其放入OPEN表末端，并提供返回节点n的指针。根据后继节点在G中的出现情况修改指针方向重排OPEN表失败，退出成功，退出YYNN二、宽度优先搜索策略1.宽度优先搜索算法把初始节点S0放入OPEN表中。如果OPEN表空表，则问题无解，退出；否则继续。把OPEN表中的第一个节点（记为节点n）移出，并放入CLOSED表中。判断节点n是否为目标节点，若是，则问题有解，并用回溯法找出解的路径，退出；否则继续若节点n不可扩展，转2）；否则继续。对节点n进行扩展，将它的所有后继节点放入OPEN表的末端，并为这些后继节点设置指向父节点n的指针，然后转2）。2.搜索过程示意图SLOFMNPQFH28314765283147652318476528316475283147658321476528371465231847652318476512384765234187651237846512384765例：八数码难题三、深度优先搜索1.深度优先搜索算法把初始节点S0放入OPEN表中。如果OPEN表空表，则问题无解，退出；否则继续。把OPEN表中的第一个节点（记为节点n）移出，并放入CLOSED表中。判断节点n是否为目标节点，若是，则问题有解，并用回溯法找出解的路径，退出；否则继续若节点n不可扩展，转2）；否则继续。对节点n进行扩展，将其后继节点放入OPEN表的前端，并为这些后继节点设置指向父节点n的指针，然后转2）。SLOFMNPQFHF2.搜索过程示意图四、有界深度优先搜索把初始节点S0放入OPEN表中。如果OPEN表空表，则问题无解，退出；否则继续。把OPEN表中的第一个节点（记为节点n）移出，并放入CLOSED表中。判断节点n是否为目标节点，若是，则问题有解，并用回溯法找出解的路径，退出；否则继续如果节点n的深度等于最大深度，转2）若节点n不可扩展，转2）；否则继续。对节点n进行扩展，将其后继节点放入OPEN表的前端，并为这些后继节点设置指向父节点n的指针，然后转2）。五、代价树的宽度优先搜索1.代价树：有向边上标有代价的搜索树。C（i,j)：节点i到其后继节点j的连线代价g(x)：初始节点S0到节点x的路径代价则

g（j）=g（i）+C（i,j)2.代价树的宽度优先搜索算法把初始节点S0放入OPEN表中，令g（S0）=0。如果OPEN表空表，则问题无解，退出；否则继续。把OPEN表中代价最小的节点，即排在前端的第一个节点（记为节点n）移出，并放入CLOSED表中。如果节点n是目标节点，则问题有解，退出；否则继续。若节点n不可扩展，转2）；否则继续。对节点n进行扩展，将它的所有后继节点放入OPEN表中，并对每个后继节点计算其代价，并为这些后继节点设置指向父节点n的指针，然后，根据节点的代价大小对OPEN表中的所有节点进行从大到小的排序。转2）。例：推销员旅行问题ABDCE6105678AB1C1D1D2E1C2E2B2E3E465786107856§5.4启发式搜索策略一、启发信息与估价函数启发信息：用于指导搜索过程且与具体问题求解有关的控制性信息。分类：用于决定要扩展的下一个节点用于要生成哪一个或哪几个后继节点用于确定某些应该从搜索树中抛弃的节点估价函数：用来估价节点希望程度的度量。其一般形式为：

f(x)=g(x)+h(x)g(x)：S0到节点x已实际付出的代价h(x)：从节点x到目标节点Sg的最优估计代价，又称启发函数。二、最佳优先搜索1.局部最佳优先搜索开始把S0放入OPEN表，计算f（S0）OPEN为空表？把OPEN表中第一个节点（n）移至CLOSED表中N为目标节点吗？对节点n进行扩展，并计算其后继节点的估价函数值，依从大到小的顺序放入OPEN表的前端为每个后继节点设置指向n的指针失败，退出成功，退出YYNNN为可扩展吗？NY2.全局最佳优先搜索开始把S0放入OPEN表，计算f（S0）OPEN为空表？把OPEN表中第一个节点（n）移至CLOSED表中N为目标节点吗？对节点n进行扩展，并计算其后继节点的估价函数值，为每个后继节点设置指向n的指针把后继节点送入OPEN表，对其中所有节点依估价函数从小到大排序失败，退出成功，退出YYNNN为可扩展吗？NY例：用全局最佳优先算法求解八数码难题2318476512384765S0Sg定义估价函数：f(x)=d(x)+h(x)d(x)：节点x的深度h(x)：节点x与目标节点不同数码位置的个数42831476523184765423184765231