第六讲状态空间搜索策略上ppt课件.ppt

《第六讲状态空间搜索策略上ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第六章问题求解与搜索策略6.1基本概念6.2状态空间的搜索策略6.3与/或树的搜索策略6.4搜索的完备性与效率问题求解问题求解是人工智能的核心问题之一问题求解的目的机器自动找出某问题的正确解决策略更进一步，能够举一反三，具有解决同类问题的能力是从人工智能初期的智力难题、棋类游戏等问题的研究中开始形成和发展起来的一大类技术，搜索技术是问题求解的主要手段之一问题表示解的搜索示例——八数码难题在3×3的棋盘，摆有八个棋子，每个棋子上标有1至8的某一数字。棋盘上还有一个空格，与空格相邻的棋子可以移到空格中。12384567初始状态81324567目标

2、状态如何将棋盘从某一初始状态变成最后的目标状态？问题示例4怎样找到两点之间的最短路径呢？6.1.2状态空间表示法（1）很多问题的求解过程都可以看作是一个搜索过程。问题及其求解过程可以用状态空间表示法来表示。（2）状态空间用“状态”和“算符”来表示问题。状态状态用以描述问题在求解过程中不同时刻的状态，一般用一个向量表示：SK=(Sk0,Sk1,…)算符使问题从一个状态转变为另一个状态的操作称为算符。在产生式系统中，一条产生式规则就是一个算符。状态空间由所有可能出现的状态及一切可用算符所构成的集合称为问题的状态空间。（3）采用状态空间求解问题，可

3、以用下面的一个三元组表示：(S,F,G)其中S是问题初始状态的集合；F是算符的集合；G是目标状态的集合。传教士野人问题（Missionaries&Cannibals，MC问题）有三个传教士M和三个野人C过河，只有一条能装下两个人的船，在河的一方或者船上，如果野人的人数大于传教士的人数，那么传教士就会有危险，你能不能提出一种安全的渡河方法呢？状态：问题在某一时刻所处的“位置”，“情况”等根据问题所关心的因素，一般用向量形式表示，每一位表示一个因素0：右岸1：左岸初始状态：(0,0,0)目标状态：(3,3,1)状态可有多种表示方法：(左岸传教士数

4、,右岸传教士数,左岸野人数,右岸野人数,船的位置)或(左岸传教士数,左岸野人数,船的位置)算子（算符，操作符）——使状态发生改变的操作MC问题中的算子将传教士或野人运到河对岸Move-1m1c-lr：将一个传教士(m)一个野人(c)从左岸(l)运到右岸(r)所有可能操作Move-1m1c-lrMove-1m1c-rlMove-2c-lrMove-2c-rlMove-2m-lrMove-2m-rlMove-1c-lrMove-1c-rlMove-1m-lrMove-1m-rl传教士野人问题状态空间图MC6.2状态空间的搜索策略求解过程转化为在状

5、态空间图中搜索一条从初始节点到目标节点的路径问题必须记住哪些点走过了必须记住下一步还可以走哪些点必须记住从目标返回的路径OPEN表(记录还没有扩展的点)CLOSED表(记录已经扩展的点)每个状态的节点结构中必须有指向父节点的指针6.2.1状态空间的一般搜索过程OPEN表和CLOSE表OPEN表用于存放刚生成的节点。对于不同的搜索策略，节点在OPEN表中的排列顺序是不同的。CLOSE表用于存放将要扩展的节点。对一个节点的扩展是指：用所有可适用的算符对该节点进行操作，生成一组子节点OPEN表CLOSE表状态节点父节点编号状态节点父节点搜索的一般过

6、程把初始节点S0放入OPEN表，并建立目前只包含S0的图，记为G；检查OPEN表是否为空，若为空则问题无解，退出；把OPEN表的第一个节点取出放入CLOSE表，并计该节点为n；考察节点n是否为目标节点。若是，则求得了问题的解，退出；扩展节点n，生成一组子节点。把其中不是节点n先辈的那些子节点记做集合M，并把这些子节点作为节点n的子节点加入G中；对于那些未曾在G中出现过的M成员设置一个指向父节点（即节点n）的指针，并把它们放入OPEN表；（不在OPEN表）按某种搜索策略对OPEN表中的节点进行排序；转第2步。一些说明一个节点经一个算符操作后一般

7、只生成一个子节点。但适用于一个节点的算符可能有多个，此时就会生成一组子节点。这些子节点中可能有些是当前扩展节点的父节点、祖父节点等，此时不能把这些先辈节点作为当前扩展节点的子节点。一个新生成的节点，它可能是第一次被生成的节点，也可能是先前已作为其它节点的子节点被生成过，当前又作为另一个节点的子节点被再次生成。此时，它究竟应选择哪个节点作为父节点？一般由原始节点到该节点的代价来决定，处于代价小的路途上的那个节点就作为该节点的父节点。在搜索过程中，一旦某个被考察的节点是目标节点就得到了一个解。该解是由从初始节点到该目标节点路径上的算符构成。如果在

8、搜索中一直找不到目标节点，而且OPEN表中不再有可供扩展的节点，则搜索失败。通过搜索得到的图称为搜索图，搜索图是状态空间图的一个子集。由搜索图中的所有节点及反向指针