状态空间搜索

1、计算机与信息学院 刘勇 最优化理论与应用常用搜索策略常用搜索策略 基础知识 状态空间搜索法 与或树搜索法 博弈树搜索法 随机搜索遗传算法 分析与讨论计算机与信息学院 刘勇 最优化理论与应用一. 基础知识1、为何要搜索？、为何要搜索？ 人工智能所要解决的问题大部分是人工智能所要解决的问题大部分是结构不良或非结构不良或非结构化结构化的问题，对这样的问题一般的问题，对这样的问题一般不存在成熟的算法不存在成熟的算法可供利用，而只能是利用已有的知识一步丛地可供利用，而只能是利用已有的知识一步丛地摸索摸索着着前进。如何确定前进。如何确定推理路线推理路线，使其付出的，使其付出的代价尽可能的代价尽可能的少少，

2、而问题又能得到较好的解决，而问题又能得到较好的解决? ? 在人工智能中，即使对结构性能较好，理论上有在人工智能中，即使对结构性能较好，理论上有算法可依的问题，由于问题本身的复杂性以及计算机算法可依的问题，由于问题本身的复杂性以及计算机在在时间、空间上的局限性时间、空间上的局限性，也需要通过搜索来求解。，也需要通过搜索来求解。计算机与信息学院 刘勇 最优化理论与应用2、搜索的定义和分类？、搜索的定义和分类？定义定义：根据问题的实际情况不断：根据问题的实际情况不断寻找可利用的知识寻找可利用的知识，从而从而构造一条代价较少的推理路线构造一条代价较少的推理路线，使问题得到圆满，使问题得到圆满解决的过程

3、称为搜索。解决的过程称为搜索。 分类分类：盲目搜索和启发式搜索。：盲目搜索和启发式搜索。 盲目搜索是按预定的控制策略进行搜索，在搜索过程中获盲目搜索是按预定的控制策略进行搜索，在搜索过程中获得的中间信息不用来改进控制策略。效率不高，不便于复杂问得的中间信息不用来改进控制策略。效率不高，不便于复杂问题的求解。题的求解。 启发式搜索是在搜索中加入了与问题有关的启发性信息，启发式搜索是在搜索中加入了与问题有关的启发性信息，用以指导搜索朝着最有希望的方向前进，加速问题的求解过程用以指导搜索朝着最有希望的方向前进，加速问题的求解过程并找到最优解。并找到最优解。计算机与信息学院 刘勇 最优化理论与应用3、

4、基于搜索的问题求解模式、基于搜索的问题求解模式v问题的形式化：将环境状态简化为适于问题求解的状态，用状态空间图描述问题。给出初始状态设计算子：对动作建模目标函数：目标的形式化给出路径代价函数v求解过程：在状态空间图中一条从初始结点到达目标的路径。这条路径上的所有边对应算子组成的序列，就是解决问题的一个方案v关键技术：计算机与信息学院 刘勇 最优化理论与应用问题实例八数码问题v状态：8个棋子在33的棋盘上的任意一个摆放v初始状态：右上图v算子（后继函数）：left、right、up、downv目标函数：右下图v路径代价：1计算机与信息学院 刘勇 最优化理论与应用计算机与信息学院 刘勇 最优化理论

5、与应用二. 状态搜索法1、状态（、状态（State）的基本概念）的基本概念 可把状态空间记为三元状态可把状态空间记为三元状态(S，F，G)。计算机与信息学院 刘勇 最优化理论与应用2、状态空间的搜索策略、状态空间的搜索策略计算机与信息学院 刘勇 最优化理论与应用3.3. 状态空间的一般搜索过程状态空间的一般搜索过程 对一个确定的具体问题来说，与解题有关的对一个确定的具体问题来说，与解题有关的状态空状态空间往往只是整个状态空间的一部分间往往只是整个状态空间的一部分，因此只要能生成并，因此只要能生成并存储这部分状态空间就可求得问题的解。存储这部分状态空间就可求得问题的解。 人工智能采用的人工智能采

6、用的基本思想基本思想：首先首先把问题的初始状态把问题的初始状态( (即初始节点即初始节点) )作为作为当前状态当前状态，选择适用的算符对其进行，选择适用的算符对其进行操作，生成一组操作，生成一组子状态子状态( (或称后继状态、后继节点、于或称后继状态、后继节点、于节点节点) )，然后然后检查目标状态是否在其中出现。若出现，检查目标状态是否在其中出现。若出现，则搜索成功，找到了问题的解；若不出现，则按某种搜则搜索成功，找到了问题的解；若不出现，则按某种搜索策略从已生成的状态中再选一个状态作为当前状态。索策略从已生成的状态中再选一个状态作为当前状态。重复上述过程重复上述过程，直到目标状态出现或者不

7、再有可供操作，直到目标状态出现或者不再有可供操作的状态及算符时为止。的状态及算符时为止。计算机与信息学院 刘勇 最优化理论与应用4.4. 状态空间搜索数据结构表示状态空间搜索数据结构表示计算机与信息学院 刘勇 最优化理论与应用5.5. 状态空间搜索一般过程状态空间搜索一般过程计算机与信息学院 刘勇 最优化理论与应用计算机与信息学院 刘勇 最优化理论与应用6.6. 常用搜索方法常用搜索方法（盲目（盲目BlindfoldBlindfold启发式启发式HeuristicHeuristic）计算机与信息学院 刘勇 最优化理论与应用B1 B1 广度优先搜索vbreadth-first search，BF

8、SvA B F C D E G I先扩展出的节点先被考察 计算机与信息学院 刘勇 最优化理论与应用广度优先搜索算法初始化open表、close表为空，定义S为初始状态结点将S放入到open表中如果open表为空，则搜索失败，否则从open表中取出第一个结点N,将N放入到close表中。如果N是目标结点，搜索成功，返回N对N的每一个子结点 i，如果open表和close表中都没有结点i，那么将结点i其追加到open表的最后一个元素之后goto 3计算机与信息学院 刘勇 最优化理论与应用广度优先搜索openclose1A2B,FA3F,C,D,EA,B4C,D,E,G,IA,B,F5D,E,G,I

9、A,B,F,C6E,G,IA,B,F,C,D7G,IA,B,F,C,D,E8I,HA,B,F,C,D,E,G9HA,B,F,C,D,E,G,I计算机与信息学院 刘勇 最优化理论与应用B2 B2 深度优先搜索（depth-first search）vA B C D E F G H I新扩展出的节点先被考察 计算机与信息学院 刘勇 最优化理论与应用深度优先搜索算法初始化open表、close表为空，定义S为初始状态结点将S 放入open表中如果open表为空，则搜索失败，否则从open表中取出第一个结点N，将N放入close表中如果N是目标结点，搜索成功，返回N对N的每一个子结点 i，如果open

10、表和close表中都没有结点i，那么将结点i其插入到open表的第一个元素之前goto 3计算机与信息学院 刘勇 最优化理论与应用深度优先搜索openclose1A2B,FA3C,D,E,FA,B4D,E,FA,B,C5E,FA,B,C,D6FA,B,C,D,E7G,IA,B,C,D,E,F8H,IA,B,C,D,E,F,G9IA,B,C,D,E,F,G,H10A,B,C,D,E,F,G,H,I计算机与信息学院 刘勇 最优化理论与应用B3 B3 迭代加深结合广度优先和深度优先的优点算法：v 令d = 1v 最大搜索深度 d 的深度优先搜索v 如果找到目标结点，那么结束搜索，否则d=d+1, g

11、oto 2计算机与信息学院 刘勇 最优化理论与应用迭代加深搜索过程计算机与信息学院 刘勇 最优化理论与应用启发式信息加速搜索v 盲目搜索的缺陷v 根据与问题相关的知识问题，引入启发式信息。v 定义：经过结点n的且从起点到目标的最短路径函数。 f(n)的值越小，表示路径越短v 策略：从初始结点S出发，选择最小的子结点计算机与信息学院 刘勇 最优化理论与应用引入的搜索过程f(n)计算机与信息学院 刘勇 最优化理论与应用引入的搜索过程)()()(nhngnf计算机与信息学院 刘勇 最优化理论与应用=g + g表示起始结点到n的最小代价路径的代价表示n到目标结点的最小代价路径的代价)(ng)(nh计算

12、机与信息学院 刘勇 最优化理论与应用)(* ng)(* nh)()(* )(*)(*)(* )(*)(*)(*nfnfnhngnfnnfnnhnng估计的最小代价路径的代价是经过结点估计到目标最小代价的代价是结点估计的最小代价路径的代价是初始结点到结点计算机与信息学院 刘勇 最优化理论与应用启发式搜索启发式搜索 H1 H1 局部择优搜索 局部择优搜索是一种启发式搜索方法，是对深度优先搜索方法的一种改进。其基本思想是：当一个节点被扩展以后，按f(x)对每一个子节点计算估价值，并选择最小者作为下一个要考察的节点，由于它每次都只是在子节点的范围内选择下一下要考察的节点，范围比较狭窄，所以称为局部择优

13、搜索，下面给出它的搜索过程。计算机与信息学院 刘勇 最优化理论与应用H2 H2 全局择优搜索 每当要选择一个节点进行考察时，局部择优搜索只是从刚生成的子点节中进行选择，选择的范围比较狭窄，因而又提出了全局择优搜索方法。这种方法搜索时，每次总是从0PEN表的全体节点中选择一个估价值最小的节点。 f(x)g(x)则它就成为代价树的广度优先搜索 f(x)d(x) 它就成为广度优先搜索 计算机与信息学院 刘勇 最优化理论与应用八数码问题数为位置不正确的数字个令的深度为初始结点到结点令)(*)(*nhnng1)(*nh计算机与信息学院 刘勇 最优化理论与应用计算机与信息学院 刘勇 最优化理论与应用A*算

14、法v定义g*（n）为已发现已发现的初始结点到结点n所有路径中的最小代价路径的代价。v定义h*(n)为结点n到目标结点的最小代价估计，也称启发式函数。vf*(n) =g*(n)+ h*(n)v利用f*加速搜索的算法v使用Open表、Close表计算机与信息学院 刘勇 最优化理论与应用A*算法初始化open表、close表为空，定义s为初始状态结点。计算f*(s) := g*(s) + h*(s)。将s加入到open表中。如果open表为空，则搜索失败退出，否则从open表中取出第一个结点n，将n插入到close表中如果n是目标结点，搜索成功，返回问题的解应用每一个可用的算子Opi ，扩展n生成子

15、结点 mi，计算g*(mi)=g*(n)+ C*(n, mi); f*=g*(mi)+h*(mi);如果m已经存在于open表中或者在close表中，且先前计算的g*(mi)小于等于当前的g*(mi)，那么goto 5。否则从open表或close表中取出与mi相同的子结点mi令mi ：= mi ，将mi的父指针指向n将结点mi插入到open表，然后将open表按f值排序。goto 3计算机与信息学院 刘勇 最优化理论与应用如何设计可采纳的启发式函数?v根据问题特征设计h，例如八数码问题 h1位置不一致的棋子数目 h1 (n)=1+1+0+1+1+0+0+0=4 h2所有棋子到其目标位置的距离

16、和 h2 (n)=1+2+0+1+1+0+0+0=5目标结点n计算机与信息学院 刘勇 最优化理论与应用如何设计可采纳的启发式函数?v组合启发式函数：如果已有h1, h2 , hm等可采纳启发式函数，那么： h = max(h1, h2 , hm)v从经验中学习：已知某些特征x1与x2和h有关，但不知道具体的关系，那么可以定义h=c1x1 +c2x2 通过学习调整c1与c2。vABSOLVER程序能自动生成启发式。魔方的第一个有用的启发式就是它找到的计算机与信息学院 刘勇 最优化理论与应用三. 与或树搜索法 由可解子节点来确定父节点、祖父节点等为可解节点的过程称为可解标示过程；由不可解子节点来确

17、定其父节点、祖父节点等为不可解节点的过程称为不可解标示过程。 在与或树的搜索过程中将反复使用这两个过程，直到初始节点(即原始问题)被标示为可解或不可解节点为止。计算机与信息学院 刘勇 最优化理论与应用计算机与信息学院 刘勇 最优化理论与应用与或树的一般搜索过程： (1) 把原始问题作为初始节点S0，并把它作为当前节点。 (2) 应用分解或等价变换算符对当前节点进行扩展。 (3) 为每个子节点设置指向父节点的指针。 (4) 选择合适的子节点作为当前节点，反复执行第(2)步和第(3)步，在此期间要多次调用可解标示过程和不可解标示过程，直到初始节点被标示为可解节点或不可解节点为止。 由这个搜索过程所

18、形成的节点和指针结构称为搜索树。计算机与信息学院 刘勇 最优化理论与应用 与或树的广度优先搜索 与或树的广度优先搜索与状态空间的广度优先搜索类似，也是按照“先产生的节点先扩展”的原则进行搜索.只是在搜索过程中要多次调用可解标示过程和不可解标示过程。 与或树的深度优先搜索 与或树的深度优先搜索过程和状态空间的深度优先搜索过程基本相同，也是按照“新产生的节点先扩展”的原则进行搜索.只是在搜索过程中要多次调用可解标示过程和不可解标示过程。计算机与信息学院 刘勇 最优化理论与应用四. 博弈树搜索法（敌对搜索法） 诸如下棋、打牌、战争等一类竞争性智能活动称为博弈。其中最简单的一种称为“二人零和、全信息、

19、非偶然”博弈。 所谓“二人零和、全信息、非偶然”博弈是指： (1) 双垒的AB双方轮流采取行功，博弈的结果只有A方胜，B方败； B方胜，A方败；双方战成平局. (2)在对垒过程中，任何“方都了解当前的格局及过去的历史。 (3)任何一方在采取行动前都要根据当前的实际情况，进行得失分析，选取对自己最为有利而对对方最为不利的对策，不存在“碰运气”的偶然因素。 即双方都是很理智地决定自己的行功。计算机与信息学院 刘勇 最优化理论与应用博弈的形式化v 状态：（局面，棋手）v 初始状态：（初始局面，棋手）例如：（象棋的初始布局，执红的棋手)v 动作算子：每一种合乎规则的移动v 目标测试：获胜的局面v 状态

20、空间图博弈树v 博弈树：描述所有可能的对弈计算机与信息学院 刘勇 最优化理论与应用博弈树 (双人、确定的、回合制)我的移动对手的移动移动结果效用值：效用值：用来度量收益的数值 获胜为1，失败为 1，和为0 获胜为，失败为 ，和为0 结束时以你的收益为效用值 ，例如“拱猪”计算机与信息学院 刘勇 最优化理论与应用解决方法v搜索？深度优先？广度优先？A*算法？v最优最优决策：极小极大搜索v时间有限的对策：- 剪枝、评估函数的实时决策计算机与信息学院 刘勇 最优化理论与应用极小极大搜索v 确定性博弈的完美方法v 想法: 移动到具有最大的“最小最大值” 的局面= 同最优秀的对手对弈时能够得到的最大收益

21、 双人博弈:计算机与信息学院 刘勇 最优化理论与应用倒推值计算计算机与信息学院 刘勇 最优化理论与应用基于极小极大搜索策略的博弈程序设计实例-“一字棋” 设有九个空格，由MAX，MIN二人对弈，轮到谁走棋谁就往空格上放一只自己的棋子，谁先使自己的棋子构成“三子成一线三子成一线”(同一行或列或对角线全是某人的棋子)，谁就取得了胜利。 用叉号表示MAX，用圆圈代表MIN。 比如右图中就是MIN取胜的棋局。计算机与信息学院 刘勇 最优化理论与应用设棋局为P，估价函数为e(P)。 (1) 若P对任何一方来说都不是获胜的位置，则e(P)=e(那些仍为MAX空着的完全的行、列或对角线的总数)-e(那些仍为

22、MIN空着的完全的行、列或对角线的总数)(2) 若P是MAX必胜的棋局，则e(P)+。(3) 若P是B必胜的棋局，则e(P)-。比如P如右图示,则e(P)=6-4=2估价函数的设计计算机与信息学院 刘勇 最优化理论与应用要注意利用棋盘位置的对称性,在生成后继节点的位置时，下列博弈结局都是相同的棋局(在博弈中，一字棋的分枝系数比较小起初是由于对称性，而后是由于棋盘上未布子的空格减少所致)。图3.15画出了经过两层搜索生成的博弈树，静态估值记在端节点下面，倒推值记在圆圈内。 计算机与信息学院 刘勇 最优化理论与应用第一步应该走哪里呢？计算机与信息学院 刘勇 最优化理论与应用 假设MAX走了这一步，

23、而MIN的回步是直接在X上方的空格里放上一个圆圈(对MIN来说这是一步坏棋，他一定没有采用好的搜索策略)。下一步，MAX又在新的格局下搜索两层。 计算机与信息学院 刘勇 最优化理论与应用计算机与信息学院 刘勇 最优化理论与应用 可看到MAX的最好的也是唯一能使他避免立即失败的一个走步。现在，MIN可以看出MAX必然在他的下一走步中获胜，因此，MIN只好认输。计算机与信息学院 刘勇 最优化理论与应用思考题（课后小作业）v MIN有没有更好的走法，其第一步的最优搜索策略是什么呢？试画出对应搜索树！v是不是先走就一定能获胜？计算机与信息学院 刘勇 最优化理论与应用- 剪枝技术 在极大极小分析法中，总

24、是先生成一定深度的博弈树，然后对端节点进行估值，再计算出上层节点的倒推值，这样做效率较低。 鉴于博弈树具有“与”节点和“或”节点逐层交替出现的特点，如能边生成节点边计算估值及倒推值，就有可能删去一些不必要的节点，从而减少搜索及计算的工作量。计算机与信息学院 刘勇 最优化理论与应用 对于一个“与”节点来说，它取当前子节点中的最小倒推值作为它倒推值的上界，称此值为值。 对于一个“或”节点来说，它取当前子节点中的最大倒推值作为它倒推值的下界，称此值为值值-值的定义计算机与信息学院 刘勇 最优化理论与应用(1) 任何“或”节点x的 值如果不能降低其父节点的值，则对节点x以下的分枝可停止搜索，并使x的倒

25、推值为 。这种剪枝称为剪枝。-剪枝技术计算机与信息学院 刘勇 最优化理论与应用 (2)任何“与”节点x的值如果不能升高其父节点的值，则对节点x以下的分枝可停止搜索，并使x的倒推值为这种剪枝称为 剪枝。-剪枝技术计算机与信息学院 刘勇 最优化理论与应用- 剪枝计算机与信息学院 刘勇 最优化理论与应用练习: 给出用-搜索法搜索下面的博奕树所得到的搜索树, 并在搜索到的节点上注明, 值和最终倒推值.0 1 2 -1 0 -1 1 2 3 0 -3与结点计算机与信息学院 刘勇 最优化理论与应用 (3) 在-剪枝技术中，一个节点的第一个子节点的倒推值是很重要的。对于一个“或”节点.如果估值最高的子节点最

26、先生成，或者对于一个“与”节点，估值最低的子节点最先生成，则被剪除的节点数最多，搜索的效率最高。这称为最优“-剪枝法”。-剪枝技术计算机与信息学院 刘勇 最优化理论与应用 若规定首先生成最左面的节点，图中给出了端节点的静态估值。采用-剪枝技术来引导深度优先搜索。生成的子树在图中用粗树枝表示，发生修剪的那些节点用“”表示。原来41个端节点只有18个必须估值，可见说明-方法能够有效地提高效率。计算机与信息学院 刘勇 最优化理论与应用遗传算法：神奇的方法(随机搜索启发式搜索) 不需要知道问题的知识 不用设计者明白通常的问题求解过程 越是复杂的，难以找到求解算法的问题，GA就越有效 模拟生物进化过程五

27、. 遗传算法（Genetic Algorithm, GA）计算机与信息学院 刘勇 最优化理论与应用仿生原理v进化理论拉马克的进化论用进废退达尔文的进化论自然选择适者生存基因进化学说进化的本质是基因的进化v进化过程适应能力差的生物被环境淘汰适应能力强的生物有更多的繁殖机会基因在生物体的繁殖过程中发生重组或者突变计算机与信息学院 刘勇 最优化理论与应用遗传算法流程图计算机与信息学院 刘勇 最优化理论与应用遗传算法的基本原理v给出问题的一组候选解，将这些解看作进化中的生物个体v这些个体中适应度高的个体通过繁殖生成下一代个体，也就是新的一组候选解v个体适应环境的过程就是候选解的质量不断提高的过程v问题

28、的解是在不断进化中得到的 计算机与信息学院 刘勇 最优化理论与应用遗传算法的要素v基本概念环境 适应度函数个体 问题的解种群 个体组成的集合v遗传操作生物的适应能力 适应度计算生物体的竞争 选择有性繁殖，基因的重组 交叉无性繁殖，基因的突变 变异计算机与信息学院 刘勇 最优化理论与应用生物世界VS遗传算法计算机与信息学院 刘勇 最优化理论与应用遗传算法的基本操作v 编码染色体在一定意义上包含了它所代表的问题的解。最常用的编码方式是二进制串每一个染色体用一个二进制串表示，这个二进制串的每一位表示解的某些特征。或者，整个二进制串表示一个数。例如 整数编码、实数编码、字符串编码、树状编码选用什么方法

29、编码主要取决于所要解决的问题本身。有的问题直接用整数或者实数来编码可能更好！ 计算机与信息学院 刘勇 最优化理论与应用遗传算法的基本操作v复制 直接将上一个的个体放入下一代种群，相当于染色体的自我复制 个体 新个体 v变异 个体 变异点 新个体 计算机与信息学院 刘勇 最优化理论与应用v交叉单点交叉 个体1 个体2 交叉点 新个体1 新个体2两点交叉 个体1 个体2 交叉点 交叉点 新个体1 新个体2计算机与信息学院 刘勇 最优化理论与应用应用遗传算法的步骤v针对要解决的问题，确定目标函数v对于问题的候选解，确定由候选解到染色体编码方法，以及由染色体到问题候选解的解码方法v根据目标函数设计适应度函数v选择（或针对问题设计）交叉、变异算子以及选择方法v设定种群规模、交叉概率、变异概率等参数计算机与信息学院 刘勇 最优化理论与应用遗传算法应用实例v待优化的函数2cos)(2|2 . 0 |xexfxv优化目标寻找区间-6.4,6.3内的f (x)函数的最大值计算机与信息学院 刘勇 最优化理论与应用算法设计v 编码 长度为7bit的位序列 表示-6.4 表示6.3 y = 2 令x表示 gene对应的数值x = -6.4+y(6.3-(-6.4)/(27-1) x = 0.1y 6.4v 种群规