(1.4)--第4章 搜索求解策略人工智能导论.ppt

《(1.4)--第4章 搜索求解策略人工智能导论.ppt》由会员分享，可在线阅读，更多相关《(1.4)--第4章 搜索求解策略人工智能导论.ppt（51页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第四章第四章 搜索求解策略搜索求解策略Searching Solving StrategySearching Solving StrategyPPT模板下载： 目录CONTENTS状态空间的搜索策略一二盲目的图搜索策略三搜索的概念启发式图搜素策略四问题的表示求解方法p问题求解p问题求解的基本方法：搜索法、归约法、归结法、推理法及产生式等。一、搜索的概念例1 八数码问题的状态空间。状态集 s：所有摆法操作算子：将空格向上移Up将空格向左移Left将空格向下移Down将空格向右移Right一、搜索的概念搜索中需要解决的基本问题：（1）是否一定能找到一个解。（2）找到的解是否是最佳解。（3）时间与空

2、间复杂性如何。（4）是否终止运行或是否会陷入一个死循环。一、搜索的概念1.1搜索的基本问题与主要过程搜索的主要过程：（1）从初始或目的状态出发，并将它作为当前状态。（2）扫描操作算子集，将适用当前状态的一些操作算子作用于当前状态而得到新的状态，并建立指向其父结点的指针。（3）检查所生成的新状态是否满足结束状态，如果满足，则得到问题的一个解，并可沿着有关指针从结束状态反向到达开始状态，给出一解答路径；否则，将新状态作为当前状态，返回第(2)步再进行搜索。一、搜索的概念1.1搜索的基本问题与主要过程1.搜索方向：（1）数据驱动：从初始状态出发的正向搜索。（2）目的驱动：从目的状态出发的逆向搜索。（

3、3）双向搜索正向搜索从问题给出的条件出发。逆向搜索：从想达到的目的入手，看哪些操作算子能产生该目的以及应用这些操作算子产生目的时需要哪些条件。双向搜索：从开始状态出发作正向搜索，同时又从目的状态出发作逆向搜索，直到两条路径在中间的某处汇合为止。一、搜索的概念1.2搜索策略2.盲目搜索与启发式搜索:（1）盲目搜索：在不具有对特定问题的任何有关信息的条件下，按固定的步骤（依次或随机调用操作算子）进行的搜索。（2）启发式搜索：考虑特定问题领域可应用的知识，动态地确定调用操作算子的步骤，优先选择较适合的操作算子，尽量减少不必要的搜索，以求尽快地到达结束状态。一、搜索的概念1.2搜索策略PPT模板下载：

4、 目录CONTENTS状态空间的搜索策略一二盲目的图搜索策略三搜索的概念启发式图搜索策略四二、状态空间的搜索策略状态空间表示法状态空间的图描述o状态：表示系统状态、事实等叙述型知识的一组变量或数组：o操作：表示引起状态变化的过程型知识的一组关系或函数：T二、状态空间的搜索策略2.1状态空间表示法u状态空间：利用状态变量和操作符号，表示系统或问题的有关知识的符号体系，状态空间是一个四元组：状态集合。：操作算子的集合。：包含问题的初始状态,是 的非空子集。：包含问题的目标状态，的非空子集。可以是若干具体状态或满足某些性质的路径信息描述。二、状态空间的搜索策略2.1状态空间表示法例1 八数码问题的状

5、态空间。状态集 s：所有摆法操作算子：将空格向上移Up将空格向左移Left将空格向下移Down将空格向右移Right二、状态空间的搜索策略2.2状态空间的图表示八数码状态空间图 二、状态空间的搜索策略（状态）（操作算子）状态空间的有向图描述二、状态空间的搜索策略2.2状态空间的图表示 例2 旅行商问题（traveling salesman problem,TSP）或邮递员路径问题。（家）（单位：km）可能路径：费用为375的路径（A，B，C，D，E，A）二、状态空间的搜索策略2.2状态空间的图表示 旅行推销员状态空间图（部分）ABCDEA 375 A A A A B B C C C C D D

6、 D D A E E E E E E E D 路径:路径:路径:路径:ABCEDA ABDCE ABDECA 费用:费用:费用:费用:425 525 475 525 475 375 325 400 400 300 275 275 250 225 150 100 75 125 175 225 250 100 175 225 425.二、状态空间的搜索策略PPT模板下载： 目录目录CONTENTS状态空间的搜索策略一二盲目的图搜索策略三搜索的概念启发式图搜索策略四三、盲目的图搜索策略回溯策略宽度优先搜索策略深度优先搜索策略带回溯策略的搜索从初始状态出发，不停地、试探性地寻找路径，直到它到达目的或“

7、不可解结点”，即“死胡同”为止。若它遇到不可解结点就回溯到路径中最近的父结点上，查看该结点是否还有其他的子结点未被扩展。若有，则沿这些子结点继续搜索；如果找到目标，就成功退出搜索，返回解题路径。三、盲目的图搜索策略3.1回溯策略回溯搜索示意图三、盲目的图搜索策略3.1回溯策略回溯搜索的算法PS（path states）表：保存当前搜索路径上的状态。如果找到了目的，PS就是解路径上的状态有序集。NPS（new path states）表：新的路径状态表。它包含了等待搜索的状态，其后裔状态还未被搜索到，即未被生成扩展。NSS（no solvable states）表：不可解状态集，列出了找不到解题

8、路径的状态。如果在搜索中扩展出的状态是它的元素，则可立即将之排除，不必沿该状态继续搜索。三、盲目的图搜索策略3.1回溯策略图搜索算法（深度优先、宽度优先、最好优先搜索等）的回溯思想：用未处理状态表（NPS）使算法能返回（回溯）到其中任一状态。用一张“死胡同”状态表（NSS）来避免算法重新搜索无解的路径。在PS 表中记录当前搜索路径的状态，当满足目的时可以将它作为结果返回。为避免陷入死循环必须对新生成的子状态进行检查，看它是否在该三张表中。三、盲目的图搜索策略3.1回溯策略open表（NPS表）：已经生成出来但其子状态未被搜索的状态。closed表（PS表和NSS表的合并）：记录了已被生成扩展过

9、的状态。0S12345678910宽度优先搜索法中状态的搜索次序三、盲目的图搜索策略3.2宽度优先搜索策略例1 通过搬动积木块，希望从初始状态达到一个目的状态，即三块积木堆叠在一起。BCAABC(a)初始状态(b)目的状态 积木问题三、盲目的图搜索策略3.2宽度优先搜索策略操作算子为MOVE（X，Y）：）：把积木X搬到Y（积木或桌面）上面。操作算子可运用的先决条件：被搬动积木的顶部必须为空。如果 Y 是积木，则积木 Y 的顶部也必须为空。同一状态下，运用操作算子的次数不得多于一次。MOVE（A，Table）：“搬动积木A 到桌面上”。三、盲目的图搜索策略3.2宽度优先搜索策略ABABACCBA

10、CCCBABCABACBAABCBCBCCABAMOVE(A,TABLE)MOVE(C,A)MOVE(A,C)MOVE(B,A)MOVE(B,C)MOVE(C,A)MOVE(C,B)MOVE(C,B)MOVE(A,B)0S1S2S3S4S5S6S7S8S9S10S没有后裔，没有后裔，失败退出失败退出积木问题的宽度优先搜索树三、盲目的图搜索策略S12345678910111213KK 深度优先搜索法中状态的搜索次序012345678910111213KK三、盲目的图搜索策略3.3深度优先搜索策略在深度优先搜索中，当搜索到某一个状态时，它所有的子状态以及子状态的后裔状态都必须先于该状态的兄弟状态被

11、搜索。为了保证找到解，应选择合适的深度限制值，或采取不断加大深度限制值的办法，反复搜索，直到找到解。三、盲目的图搜索策略3.3深度优先搜索策略深度优先搜索并不能保证第一次搜索到的某个状态时的路径是到这个状态的最短路径。对任何状态而言，以后的搜索有可能找到另一条通向它的路径。如果路径的长度对解题很关键的话，当算法多次搜索到同一个状态时，它应该保留最短路径。三、盲目的图搜索策略3.3深度优先搜索策略例2 卒子穿阵问题，要求一卒子从顶部通过下图所示的阵列到达底部。卒子行进中不可进入到代表敌兵驻守的区域（标注1），并不准后退。假定深度限制值为5。阵列图 三、盲目的图搜索策略3.3深度优先搜索策略ope

12、n表：S S1717、S S1818closed表：S S0 0S S1616 0SS)1,1(2S)2,1(3S)2,2(4S)1,2(5S)1,3(6S)2,3(7S)3,2(8S)3,1(9S)2,1(14S)4,1(10S)2,2(11S)1,2(12S)1,3(13S)3,2(15S)4,2(S)4,3(17S)4,4(18S)4,1(死死死死深度限制解 0SS)1,1(S)2,1(S),2(4S)1,2(5S)1,3(S)2,3(S)3,2(S)3,1(S)2,1(S)4,1(S)2,2(S)1,2(S)1,3(S)3,2(S)4,2(16S4,3(S)4,4(S)4,1(死死死死

13、深度限制解卒子穿阵的深度优先搜索树三、盲目的图搜索策略PPT模板下载： 目录目录CONTENTS状态空间的搜索策略一二盲目的图搜索策略三搜索的概念启发式图搜索策略四四、启发式图搜索策略启发式策略启发信息和估价函数A 搜索算法“启发”（heuristic）：关于发现和发明操作算子及搜索方法的研究。在状态空间搜索中，启发式被定义成一系列操作算子，并能从状态空间中选择最有希望到达问题解的路径。启发式策略：利用与问题有关的启发信息进行搜索。四、启发式图搜索策略4.1启发式策略运用启发式策略的两种基本情况：一个问题由于在问题陈述和数据获取方面固有的模糊性，可能会使它没有一个确定的解。虽然一个问题可能有确

14、定解，但是其状态空间特别大，搜索中生成扩展的状态数会随着搜索的深度呈指数级增长。四、启发式图搜索策略4.1启发式策略例1 一字棋。在九宫棋盘上，从空棋盘开始，双方轮流在棋盘上摆各自的棋子 或 （每次一枚），谁先取得三子一线（一行、一列或一条对角线）的结果就取胜。和 能够在棋盘中摆成的各种不同的棋局就是问题空间中的不同状态。9个位置上摆放空，有 39 种棋局。可能的走法：。四、启发式图搜索策略4.1启发式策略 启发式策略的运用四、启发式图搜索策略4.1启发式策略启发式搜索下缩减的状态空间四、启发式图搜索策略4.1启发式策略在具体求解中，能够利用与该问题有关的信息来简化搜索过程，称此类信息为启发信

15、息。启发式搜索：利用启发信息的搜索过程。四、启发式图搜索策略4.1启发式策略求解问题中能利用的大多是非完备的启发信息：求解问题系统不可能知道与实际问题有关的全部信息，因而无法知道该问题的全部状态空间，也不可能用一套算法来求解所有的问题。有些问题在理论上虽然存在着求解算法，但是在工程实践中，这些算法不是效率太低，就是根本无法实现。一字棋：9！，西洋跳棋：1078，国际象棋：10120，围棋：10761。假设每步可以搜索一个棋局，用极限并行速度（10-104年/步）来处理，搜索一遍国际象棋的全部棋局也得1016年即1亿亿年才可以算完！四、启发式图搜索策略4.2启发信息和估价函数 启发信息的分类：陈

16、述性启发信息过程性启发信息控制性启发信息利用控制性的启发信息的情况：没有任何控制性知识作为搜索的依据，因而搜索的每一步完全是随意的。有充分的控制知识作为依据，因而搜索的每一步选择都是正确的，但这是不现实的。四、启发式图搜索策略4.2启发信息和估价函数 估价函数的任务就是估计待搜索结点的“有希望”程度，并依次给它们排定次序（在open表中）。估价函数 ：从初始结点经过 结点到达目的结点的路径的最小代价估计值，其一般形式是一般地，在 中，的比重越大，越倾向于宽度优先搜索方式，而 的比重越大，表示启发性能越强。四、启发式图搜索策略4.2启发信息和估价函数 例2 八数码的估价函数设计方法有多种，并且不

17、同的估价函数对求解八数码问题有不同的影响。最简单的估价函数：取一格局与目的格局相比，其位置不符的数码数目。较好的估价函数：各数码移到目的位置所需移动的距离的总和。第三种估价函数：对每一对逆转数码乘以一个倍数。第四种估价函数：克服了仅计算数码逆转数目策略的局限，将位置不符数码数目的总和与3倍数码逆转数目相加。四、启发式图搜索策略4.2启发信息和估价函数 启发式图搜索法的基本特点：如何寻找并设计一个与问题有关的 及构出 ，然后以 的大小来排列待扩展状态的次序，每次选择 值最小者进行扩展。open表：保留所有已生成而未扩展的状态。closed表：记录已扩展过的状态。进入open表的状态是根据其估值的

18、大小插入到表中合适的位置，每次从表中优先取出启发估价函数值最小的状态加以扩展。四、启发式图搜索策略4.3 A 搜索算法八数码启发式搜索2 8 31 6 47 52 8 31 47 6 52 8 31 6 4 7 52 8 31 6 47 52 31 8 47 6 52 8 3 1 47 6 52 8 31 47 6 52 8 37 1 4 6 5 8 32 1 47 6 5 2 31 8 47 6 52 31 8 47 6 51 2 3 8 47 6 51 2 38 47 6 51 2 37 8 4 6 5s(4)A(6)B(4)C(6)D(5)E(5)F(6)G(6)H(7)I(5)J(7)

19、K(5)L(5)M(7)目标四、启发式图搜索策略o搜索过程如下：(1)把初始节点S0 放入OPEN表,计算f(S0)(2)如果OPEN表为空,则问题无解,退出(3)把OPEN表的第一个节点(记为节点n)取出,放入CLOSED表(4)考查节点n是否为目标节点.若是,则求得了问题的解,退出(5)若节点n不可扩展,则转第(2)步(6)扩展节点n,用估价函数f(x)计算每个子节点的估价值,并按估价值从小到大的顺序依次放入OPEN表的首部,并为每一个子节点都配置指向父节点的指针,转第(2)步局部择优搜索(爬山法)四、启发式图搜索策略全局择优搜索(有序搜索/最好优先)o搜索过程如下：(1)把初始节点S0

20、放入OPEN表,计算f(S0)(2)如果OPEN表为空,则问题无解,退出(3)把OPEN表的第一个节点(记为节点n)取出,放入CLOSED表(4)考查节点n是否为目标节点.若是,则求得了问题的解,退出(5)若节点n不可扩展,则转第(2)步(6)扩展节点n,用估价函数f(x)计算每个子节点的估价值,并按估价值从小到大的顺序依次放入OPEN表的首部,并为每一个子节点都配置指向父节点的指针,转第(2)步(7)转第(2)步四、启发式图搜索策略例3 利用A 搜索算法求解八数码问题的搜索树，其估价函数定义为 ：状态的深度，每步为单位代价。：以“不在位”的数码数作为启发信息的度量。四、启发式图搜索策略4.3 A 搜索算法四、启发式图搜索策略open表和closed表内状态排列的变化情况 四、启发式图搜索策略