223-知识表示与问题求解(状态空间法)讲解课件.ppt

1、1智能控制技术上海大学机电工程与自动化学院杜鑫 自动化系仪自教研室22.2 知识表示与问题求解知识表示知识表示与问题求解与问题求解自动化系仪自教研室32.2 知识表示与问题求解知识表示知识表示与问题求解与问题求解自动化系仪自教研室例:三数码难题（3 puzzle problem）123123123312312312初始棋局目标棋局自动化系仪自教研室5q状态空间表示法就是以“状态空间”的形式来表示问题及其搜索过程的一种方法。q状态空间表示法是人工智能中最基本的形式化方最基本的形式化方法法，是讨论问题求解技术的基础。自动化系仪自教研室61. 1. 状态状态是描述问题求解过程中不同时刻状况的数据结构

2、。一般用一组变量的有序集合表示： Q=(q0，q1，.，qn) 其中每个元素qi(i=0，l，2，n) 为状态变量。2.2.3.1 2.2.3.1 问题状态空间的构成问题状态空间的构成当给每一个变量以确定的值时，就得到了一个具体的状态。自动化系仪自教研室7算符：引起状态中某些变量发生变化，从而使问题由一个状态变为另一个状态的操作。2. 2. 算符算符算符可分为走步、过程、规则、数学算子、运算符号、逻辑符号等。例如：在产生式系统中，每一条产生式规则就是一个算符；而在下棋程序中，一个算符就是一个走步。2.2.3.1 2.2.3.1 问题状态空间的构成问题状态空间的构成自动化系仪自教研室8状态空间：

3、一个问题的全部状态及一切可用算符构成的集合。3. 3. 状态空间状态空间状态空间由三部分构成：问题的所有可能初始状态构成的集合S；算符集合F；目标状态集合G。用一个三元组表示为：(S，F，G)2.2.3.1 2.2.3.1 问题状态空间的构成问题状态空间的构成自动化系仪自教研室9状态空间图：状态空间的图示形式。其中节点表示状态；有向边(弧)表示算符。3. 3. 状态空间状态空间2.2.3.1 2.2.3.1 问题状态空间的构成问题状态空间的构成自动化系仪自教研室10状态空间的问题求解就是从问题的初始状态集S出发，经过一系列的算符运算，到达目标状态。4. 4. 问题的解问题的解由初始状态到目标状

4、态所用算符的序列就构成了问题的一个解。2.2.3.1 2.2.3.1 问题状态空间的构成问题状态空间的构成自动化系仪自教研室11(1)定义状态的描述形式。2.2.3.22.2.3.2用状态空间表示问题的步骤用状态空间表示问题的步骤(2)用所定义的状态描述形式把问题的所有可能的状态都表示出来，并确定出问题的初始状态集合描述和目标状态集合描述。(3)定义一组算符，使得利用这组算符可把问题由一种状态转变为另一种状态。问题求解过程是一个不断把算符作用于状态的过程自动化系仪自教研室(4) 首先将适用算符作用于初始状态，以产生新的状态；(5) 然后再把一些适用的算符作用于新的状态；这样继续下去，直到产生的

5、状态为目标状态为止。(6 )这时，就得到了问题的一个解，这个解是从初始状态到目标状态所用算符构成的序列。问题：最优解问题；搜索策略问题。2.2.3.22.2.3.2用状态空间表示问题的步骤用状态空间表示问题的步骤自动化系仪自教研室13v例如下棋、迷宫及各种游戏。例如下棋、迷宫及各种游戏。OriginalStateMiddleStateGoalState2.2.3.22.2.3.2用状态空间表示问题的步骤用状态空间表示问题的步骤自动化系仪自教研室14HanoiHanoi塔塔在梵城（Hana）地下有一个僧侣的秘密组织，他们有3个大型的塔柱，左边的塔柱上由方到小套着64个金盘。僧侣们的工作是要把这6

6、4个金盘从左边塔柱转移到右边塔柱上去。但转移过程有规定的：1、每次只能搬动一只盘子，盘十只能在3个塔柱上安放，不允许放在地上；2、在每个塔柱上，只允许把小盘十叠在大盘上，反之不允许。据传说，僧侣们完成这个任务时，世界的末日就来临了。自动化系仪自教研室15HanoiHanoi塔塔19世纪，法国的一位数学家douard Lucas (18421891) 对该课题进行过研究，他指示，要完成这个任务，僧侣们搬动金盘的总次数：18446744073709551615（20位）假设僧侣们个个身强力壮，每天24小时不知头疲倦地工作，而且一秒钟移动一个金盘，那么，完成这个任务也得花5800亿年亿年。自动化系仪

7、自教研室16HanoiHanoi塔塔观自在菩萨，行深般若波罗蜜多时，照见五蕴皆空，度一切苦厄。舍利子，色不异空，空不异色；色即是空，空即是色。受想行识，亦复如是。舍利子，是诸法空相，不生不灭，不垢不净，不增不减。19世纪，法国的一位数学家douard Lucas (18421891) 对该课题进行过研究，他指示，要完成这个任务，僧侣们搬动金盘的总次数：18446744073709551615（20位）假设僧侣们个个身强力壮，每天24小时不知头疲倦地工作，而且一秒钟移动一个金盘，那么，完成这个任务也得花5800亿年亿年。自动化系仪自教研室17已知3个柱子l、2、3和两个盘子A、B(A比B小)。初

8、始状态下，A、B依次放在1柱上；目标状态是A、B依次放在柱子3上。条件是每次可移动一个盘子，盘子上方是空顶方可移动，而且任何时候都不允许大盘在小盘之上。例例2.2.3.1 2.2.3.1 二阶二阶HanoiHanoi塔问题塔问题自动化系仪自教研室18定义问题状态的描述形式 设用Sk=(SkA，SkB)表示问题的状态，SkA表示盘子A所在的柱号，SkB表示盘子B所在的柱号。第一步：用状态空间表示问题用状态描述形式把问题的所有可能的状态都表示出来。本问题共有九种可能状态: S0=(1，1)， S1=(1，2)， S2=(1，3) S3=(2，1)， S4=(2，2)， S5=(2，3) S6=(3

9、，1)， S7=(3，2)， S8=(3，3) 问题的初始状态集合为S=S0，目标状态集合为G=S8。自动化系仪自教研室19自动化系仪自教研室v算符A(i，j)表示把盘子A从第i号柱子移到第j号柱子上的操作；v算符B(i，j)表示把盘子B从第i号柱子移到第j号柱子上的操作。v算符组F中共有12个算符:A(1，2)，A(1，3)，A(2，1)，A(2，3)，A(3，1)，A(3，2)B(1，2)，B(1，3)，B(2，1)，B(2，3)，B(3，1)，B(3，2)v问题的状态空间(S，F，G)构造完成。定义一组算符F自动化系仪自教研室21根据状态空间的9种可能状态和12种算符，构造它的状态空间图

10、：第二步：问题求解自动化系仪自教研室22在状态空间图中，从初始节点(1，1)(状态S0)到目标节点(3，3)(状态S8)的任何一条通路都是问题的一个解。最短的路径长度是3，它由3个算符组成：A(1，2)、B(1，3)、A(2，3)。自动化系仪自教研室三枚钱币处于反、正、反状态，每次只许翻动一枚钱币，问连续翻动三次后，能否出现全正或全反状态。 初始状态初始状态QsQs目标状态集合目标状态集合Q0, Q7v例例1 1：翻转钱币问题：翻转钱币问题自动化系仪自教研室引入一个三元组引入一个三元组(q(q0 0,q,q1 1,q,q2 2) )来描述总状态，钱币正面为来描述总状态，钱币正面为0 0，反面，

11、反面为为1 1，全部可能的状态为：，全部可能的状态为： Q Q0 0=(0,0,0)=(0,0,0) ; Q ; Q1 1=(0,0,1); Q=(0,0,1); Q2 2=(0,1,0)=(0,1,0) Q Q3 3=(0,1,1) ; Q=(0,1,1) ; Q4 4=(1,0,0); =(1,0,0); Q Q5 5=(1,0,1)=(1,0,1) Q Q6 6=(1,1,0) ; =(1,1,0) ; Q Q7 7=(1,1,1)=(1,1,1)。翻动钱币的操作抽象为改变上述状态的算子，翻动钱币的操作抽象为改变上述状态的算子， 即即F Fa, b, ca, b, c a: a:把钱币把

12、钱币q q0 0翻转一次翻转一次 b:b:把钱币把钱币q q1 1翻转一次翻转一次 c:c:把钱币把钱币q q2 2翻转一次翻转一次 问题的状态空间为问题的状态空间为 v例例2.2.3.22.2.3.2：翻转钱币问题：翻转钱币问题自动化系仪自教研室问题的状态空间为： 构造状态空间图：构造状态空间图： 507QabcQQ， ， ， ，aabaababaababaabaabbbbbbbccbcccbccbcccbccbv例例2.2.3.22.2.3.2：翻转钱币问题：翻转钱币问题自动化系仪自教研室图图2-5 2-5 翻动三次后三枚钱币问题的状态变化翻动三次后三枚钱币问题的状态变化翻转钱币问题状态空

13、间图的另一种表示：翻转钱币问题状态空间图的另一种表示：v例例2.2.3.22.2.3.2：翻转钱币问题：翻转钱币问题自动化系仪自教研室v例例2.2.3.32.2.3.3：修道士和野人问题：修道士和野人问题在河的左岸有三个修道士、三个野人和一条船，修道士在河的左岸有三个修道士、三个野人和一条船，修道士们想用这条船将所有的人都运过河去，但受到以下条件们想用这条船将所有的人都运过河去，但受到以下条件的限制：的限制：1 1）修道士和野人都会划船，但船一次）修道士和野人都会划船，但船一次最多最多只能只能运两个人运两个人；2 2）在任何岸边）在任何岸边野人数目野人数目都都不得超过修道士不得超过修道士，否则

14、修道士，否则修道士就会被野人吃掉。就会被野人吃掉。自动化系仪自教研室1、问题的状态可以用一个三元数组来描述： S(m, c, b) m：左岸的修道士数 c：左岸的野人数 b：左岸的船数 右岸的状态不必标出，因为： 右岸的修道士数 m 3m 右岸的野人数 c 3c 右岸的船数 b 1bv例例2.2.3.32.2.3.3：修道士和野人问题：修道士和野人问题自动化系仪自教研室状态m, c, b状态m, c, b状态m, c, b状态m, c, bS03 3 1S81 3 1S163 3 0S241 3 0S13 2 1S91 2 1S173 2 0S251 2 0S23 1 1S101 1 1S18

15、3 1 0S261 1 0S33 0 1S111 0 1S193 0 0S271 0 0S42 3 1S120 3 1S202 3 0S28 0 3 0S52 2 1S130 2 1S212 2 0S290 2 0S62 1 1S140 1 1S222 1 0S300 1 0S72 0 1S150 0 1S232 0 0S310 0 0状态不合法状态不合法由合理的状态转换规则无法退出由合理的状态转换规则无法退出v例例2.2.3.32.2.3.3：修道士和野人问题：修道士和野人问题自动化系仪自教研室2.2.操作集操作集F Fpp0101, p, p1010,p,p1111,p,p0202,p,p

16、2020,q,q0101,q,q1010,q,q1111, q, q0202,q,q2020 q20b=0, (m=0,c=2)或(m=1,c=1)b=1, m=m+2q02b=0, m=0或3, c2b=1, c=c+2q11b=0, m=c, c2b=1, m=m+1, c=c+1q10b=0, (m=0,c=1)或(m=2,c=2)b=1, m=m+1q01b=0, m=0或3, c2b=1, c=c+1p20b=1, (m=3,c=1)或(m=2,c=2)b=0, m=m-2p02b=1, m=0或3, c2b=0, c=c-2p11b=1, m=c, c1b=0, m=m-1, c=

17、c-1p10b=1, (m=3,c=2)或(m=1,c=1)b=0, m=m-1p01b=1, m=0或3, c1b=0, c=c-1操作符条 件动 作v例例2.2.3.32.2.3.3：修道士和野人问题：修道士和野人问题自动化系仪自教研室3.状态空间给出状态和操作的描述之后，该问题的状态空间是：S0， P 01，P 10，P 11，P 02，P 20，Q01，Q 10，Q 11，Q 02，Q 20，S31。v例例2.2.3.32.2.3.3：修道士和野人问题：修道士和野人问题自动化系仪自教研室S0(3,3,1)S18(3,1,0)p02q02S17(3,2,0)p01q01S21(2,2,0

18、)p11q11S1(3,2,1)q01p01p10q10S19(3,0,0)q02p02S2(3,1,1)q01p01S26(1,1,0)q20p20S0(0,0,0)q11p11S14(0,1,1)p01q01p02q02S10(1,1,1)p10q10S13(0,2,1)q01p01S30(0,1,0)p02q02S12(0,3,1)p01q01S29(0,2,0)p20q20S5(2,2,1)q11p114.4.状态空间图：状态空间图：四条四条S S0 0到到S S3131长度相等的最短路径，对应的长度相等的最短路径，对应的操作序列就是该问题的四个最优解操作序列就是该问题的四个最优解v例

19、例2.2.3.32.2.3.3：修道士和野人问题：修道士和野人问题自动化系仪自教研室 思考题：( (猴子摘香蕉猴子摘香蕉) )自动化系仪自教研室 猴子猴子香蕉香蕉箱子箱子 猴子猴子香蕉香蕉箱子箱子 Ha!Ha! 思考题：( (猴子摘香蕉猴子摘香蕉) )自动化系仪自教研室隐式状态空间图：利用有关状态描述和状态转换（操作）的知识定义的状态空间图。在计算机中仅存储描述问题状态及操作的有关知识，包括该问题的各状态分量的取值情况、分量之间的约束条件、开始状态、终止状态，以及全部操作的条件和动作等。隐式状态空间图也称为是状态空间图的隐式表示或隐式图。v显式显式状态空间图状态空间图 vsvs 隐式隐式状态空

20、间图状态空间图显式状态空间图显式状态空间图：表示了问题所有可能的状态及状：表示了问题所有可能的状态及状态之间的关系，这种表示方式称为态之间的关系，这种表示方式称为显式状态空间图显式状态空间图，或称为，或称为状态空间图的显示表示状态空间图的显示表示。自动化系仪自教研室 重排九宫问题的状态表示重排九宫问题的状态表示v显式显式状态空间图状态空间图 vsvs 隐式隐式状态空间图状态空间图重排九宫问题的隐式图描述为：重排九宫问题的隐式图描述为： 自动化系仪自教研室（1）有关状态的知识： v显式显式状态空间图状态空间图 vsvs 隐式隐式状态空间图状态空间图重排九宫问题的隐式图描述为：重排九宫问题的隐式图

21、描述为： 初始状态：初始状态： S0 （0，1，2，3，5，6，4，7，8） 目标状态：目标状态： Sg （0，1，2，3，4，5，6，7，8）状态状态S的定义：的定义：S(X0，X1，X2，X3，X4 ，X5， X6 ，X7 ，X8) 其中，其中， Xi 0，1，2，3，4，5，6，7，8， 自动化系仪自教研室0组规则 R1(X0=0 ) (X2=n ) X0 = n X2 =0； R2(X0=0 ) (X4=n ) X0 = n X4 =0； R3(X0=0 ) (X6=n ) X0 = n X6 =0； R4(X0=0 ) (X8=n ) X0 = n X8 =0；1组规则 R5(X1=

22、0 ) (X2=n ) X1 = n X2 =0； R6(X1=0 ) (X8=n ) X1 = n X8 =0；v显式显式状态空间图状态空间图 vsvs 隐式隐式状态空间图状态空间图重排九宫问题的隐式图描述为：重排九宫问题的隐式图描述为： （2 2）有关操作的知识（规则）：）有关操作的知识（规则）：自动化系仪自教研室（S0, r1 , r2 , , r24 , Sg）v显式显式状态空间图状态空间图 vsvs 隐式隐式状态空间图状态空间图重排九宫问题的隐式图描述为：重排九宫问题的隐式图描述为： 这里仅给出了初始节点和目标节点，其余节点需用状态转这里仅给出了初始节点和目标节点，其余节点需用状态转

23、换规则来产生。类似于这样表示的状态图称为换规则来产生。类似于这样表示的状态图称为隐式状态图隐式状态图，或者说或者说状态图状态图的的隐式表示隐式表示。自动化系仪自教研室402.2 知识表示与问题求解知识表示知识表示与问题求解与问题求解自动化系仪自教研室v状态空间图搜索中的通用数据结构状态空间图搜索中的通用数据结构CLOSED表：表：用来记录考察过的节点以及节点之间的关用来记录考察过的节点以及节点之间的关系，如每个节点指向父节点的编号（返回指针）。系，如每个节点指向父节点的编号（返回指针）。CLOSED表中存放的就是一定搜索策略下的搜索树。表中存放的就是一定搜索策略下的搜索树。节点父节点编号编号节

24、点父节点编号OPEN表表CLOSED表表OPEN表：表：专门登记已经生成但还没有考察的节点，即待专门登记已经生成但还没有考察的节点，即待考察节点。考察节点。自动化系仪自教研室v盲目搜索盲目搜索盲目搜索盲目搜索: :搜索时不参考与具搜索时不参考与具体待求解问题相关的任何信体待求解问题相关的任何信息，只是按预先设定的顺序息，只是按预先设定的顺序逐个考察节点。盲目搜索与逐个考察节点。盲目搜索与问题无关，具有问题无关，具有通用性通用性。状态空间图搜索状态空间图搜索广度优先搜索广度优先搜索深度优先搜索深度优先搜索迭代加深搜索迭代加深搜索自动化系仪自教研室盲目搜索盲目搜索-广度优先搜索算法广度优先搜索算法

25、v广度优先搜索（广度优先搜索（A A?eded）基本思想）基本思想广度优先搜索是严格按节点在树中的出现位置广度优先搜索是严格按节点在树中的出现位置一层一层一层一层向下向下的搜索过程。通过将的搜索过程。通过将OPEN表设计为一个队列来实表设计为一个队列来实现，将现，将新生成的子节点新生成的子节点放在放在OPEN表的后面表的后面，保证，保证先生先生成的节点先考察成的节点先考察。自动化系仪自教研室步1 把初始结点S0放入OPEN表中；步2 若OPEN表为空，则搜索失败，退出；步3 否则，取OPEN表中第一个结点N放在CLOSED表中；并冠以顺序编号n；步4 若结点N为目标结点，则搜索成功。利用CLO

26、SED表中的返回指针找出S0到N的路径即为所求解，退出；步5 若N不可扩展，转步2；步6 否则，扩展N，将其所有子结点配上指向N的返回指针放入OPEN表的尾部，转步2。v广度优先搜索算法广度优先搜索算法盲目搜索盲目搜索-广度优先搜索算法广度优先搜索算法自动化系仪自教研室v广度优先搜索算法流程图广度优先搜索算法流程图盲目搜索盲目搜索-广度优先搜索算法广度优先搜索算法自动化系仪自教研室1 2 38 57 4 611 2 38 5 67 481 38 2 57 4 6101 2 38 4 5 7 671 2 38 4 57 6 6 1 38 2 57 4 6111 2 38 4 57 621 2 3

27、8 5 7 4 631 2 38 4 57 641 2 37 8 5 4 612 2 31 8 57 4 6131 2 38 47 6 5141 2 3 4 58 7 6151 28 5 37 4 6171 3 58 27 4 6188 1 3 2 57 4 6191 2 37 8 54 6202 31 8 5 7 4 6211 28 4 37 6 5221 2 3 8 57 4 651 2 38 47 6 523八数码广度优先搜索八数码广度优先搜索1 28 5 37 4 69161 2 38 5 67 4v使用广度优先搜索算法求解重排九宫问题使用广度优先搜索算法求解重排九宫问题盲目搜索盲目搜

28、索-广度优先搜索算法广度优先搜索算法自动化系仪自教研室缺点搜索效率低。v广度优先搜索的特点：广度优先搜索的特点：广度优先中广度优先中OPENOPEN表表是一个是一个队列队列，CLOSEDCLOSED表表是一个是一个顺顺 序表序表，表中各节点按顺序编号，正被考察的节点在表，表中各节点按顺序编号，正被考察的节点在表中编号最大。中编号最大。广度优先搜索又称为广度优先搜索又称为宽度优先宽度优先或或横向搜索横向搜索。广度优先策略是广度优先策略是完备完备的，即如果问题的解存在，则它一的，即如果问题的解存在，则它一定可以找到解，并且找到的解还是最优解。定可以找到解，并且找到的解还是最优解。广度优先搜索策略与

29、问题无关，具有通用性。广度优先搜索策略与问题无关，具有通用性。盲目搜索盲目搜索-广度优先搜索算法广度优先搜索算法自动化系仪自教研室盲目搜索盲目搜索-深度优先搜索算法深度优先搜索算法v深度优先搜索的基本思想深度优先搜索的基本思想深度优先搜索是一种深度优先搜索是一种一直向下一直向下的搜索过程，它优先在自的搜索过程，它优先在自己的子结点集合中选择下一个被考察的结点，己的子结点集合中选择下一个被考察的结点，不断向纵不断向纵深方向前进，直到到达叶子结点或受到深度限制深方向前进，直到到达叶子结点或受到深度限制时，才时，才返回到上一级结点沿另一方向继续前进。返回到上一级结点沿另一方向继续前进。自动化系仪自教

30、研室与广度优先搜索策略的唯一不同点就是与广度优先搜索策略的唯一不同点就是OPENOPEN表表被设计被设计成成后进先出的栈后进先出的栈，新生成的子结点放在新生成的子结点放在OPENOPEN表的前面，后生成的结点优表的前面，后生成的结点优先被考察。先被考察。深度优先搜索算法只需深度优先搜索算法只需将宽度优先搜索算法步将宽度优先搜索算法步6 6修改为修改为：步步6 6 否则，扩展否则，扩展N N，将其所有子结点配上指向，将其所有子结点配上指向N N的指针的指针放入放入OPENOPEN表的表的首部首部，转步，转步2 2。 盲目搜索盲目搜索-深度优先搜索算法深度优先搜索算法v深度优先搜索算法深度优先搜索

31、算法自动化系仪自教研室1 2 38 57 4 611 2 38 4 5 7 631 2 38 4 57 6 1 2 38 4 57 61 2 38 5 7 4 61 2 38 4 57 61 2 38 47 6 541 28 4 37 6 51 2 3 8 57 4 621 2 38 47 6 55v使用深度优先搜索算法求解重排九宫问题使用深度优先搜索算法求解重排九宫问题盲目搜索盲目搜索-深度优先搜索算法深度优先搜索算法自动化系仪自教研室深度优先搜索的特点：OPEN表为一个堆栈。深度优先又称纵向搜索。一般不能保证找到最优解。如下图所示：图图 深度优先搜索不具有完备性示意图深度优先搜索不具有完备

32、性示意图v深度优先搜索的特点：深度优先搜索的特点：盲目搜索盲目搜索-深度优先搜索算法深度优先搜索算法自动化系仪自教研室为克服深度优先搜索的不足，可对其深度进行限制盲目搜索盲目搜索-有界深度优先搜索算法有界深度优先搜索算法v有界深度有界深度优先搜索的提出：优先搜索的提出：即使能求出解，它也不一定是最优解。即使能求出解，它也不一定是最优解。深度界限的选择很重要深度界限的选择很重要d dmm 若太小，则达不到解的深度，得不到解；若太大，若太小，则达不到解的深度，得不到解；若太大，既浪费了计算机的存储空间与时间，又降低了搜索效既浪费了计算机的存储空间与时间，又降低了搜索效率。由于解的路径长度事先难以预

33、料，所以要恰当地率。由于解的路径长度事先难以预料，所以要恰当地给出给出d dmm的值是比较困难的。的值是比较困难的。自动化系仪自教研室当在dm界限之内找不到解时，可以将深度界限dm不断扩大，每次增加一个深度增量d，直到找到解，或者搜索完整棵树。这样算法的完备性得到了保证，称为可变界深度优先搜索算法(或迭代加深搜索)。 盲目搜索盲目搜索-有界深度优先搜索算法有界深度优先搜索算法v有界深度有界深度优先搜索的思路优先搜索的思路-迭代加深迭代加深 当当d d =1=1时，算法开始蜕变为时，算法开始蜕变为广度优先搜索广度优先搜索算法。算法。自动化系仪自教研室人工智能盲目搜索盲目搜索-迭代加深优先搜索算法

34、迭代加深优先搜索算法自动化系仪自教研室步1 把初始结点S0放入OPEN表中，置d(S0)=0，dm=dm0，G=NULL。步2 若OPEN表为空，则考察CLOSED表是否有待扩展结点： （1）若无待扩展结点，则判断G表是否为空： 若为空，搜索失败，退出； 否则，取出G表最后面的结点Sg， Sg即为所求最优解，搜索成功，退出； （2）若有待扩展结点，则取出CLOSED表中待扩展结点放入到OPEN表中，令dm=dm+d，转步2；v有界深度有界深度优先搜索的思路优先搜索的思路-迭代加深迭代加深盲目搜索盲目搜索-迭代加深优先搜索算法迭代加深优先搜索算法自动化系仪自教研室步3 取OPEN表中首部的结点N

35、放在CLOSED表中；并冠以顺序编号n； 步4 若d（N）dm，则标N为待扩展结点，转步2；步5 若N是目标结点Sg ，则令dmd（ Sg ）-1 ，把Sg放到G 表的尾部，转步2。步6 若N不可扩展，则转步2； 步7 否则，扩展N，将其所有子结点Ni配上指向N的返回指针放入OPEN表首部， 置d（ Ni ）d（N）1 ，转步2。 v有界深度有界深度优先搜索的思路优先搜索的思路-迭代加深迭代加深盲目搜索盲目搜索-迭代加深优先搜索算法迭代加深优先搜索算法自动化系仪自教研室八数码难题的深度优先搜八数码难题的深度优先搜索树索树( (深度约束深度约束=4)=4)12384567123845671238

36、4567123845671238456712384567123845671345612367812384567123845671 23845671 2384567Goal123845671238456741238567v对对n应用一个算符以产应用一个算符以产生该节点的一个后继节生该节点的一个后继节点放入点放入OPEN表的前端表的前端81324567Goal:自动化系仪自教研室58vCombines depth- and breadth firstvOptimal and complete, memory efficient迭代加深迭代加深( (深度约束深度约束=1)=1)12384567123

37、8456712384567123845671238456781324567Goal:迭代加深算法迭代加深算法 Demo 自动化系仪自教研室59迭代加深迭代加深( (深度约束深度约束=2)=2)123845671238456712384567123845674123856712 3845671238456712384567123845671238456712384567123845675671238481324567Goal:自动化系仪自教研室60迭代加深迭代加深( (深度约束深度约束=3)=3)123845671238456712384567123845674123856712 3845671

38、23845671238456712384567123845671238456712384567123845671 238456712 38456712384567123845671238456712384567123845675671238481324567Goal:自动化系仪自教研室61迭代加深迭代加深( (深度约束深度约束=4)=4)123845671238456712384567123845671238456712384567123845671345612367812384567123845671 23845671 2384567Goal1238456712384567412385678

39、1324567Goal:自动化系仪自教研室问题：当问题：当d d 1 1 时，时， 是否能保证找到最优解？是否能保证找到最优解？v有界深度有界深度优先搜索的思路优先搜索的思路-迭代加深迭代加深盲目搜索盲目搜索-迭代加深优先搜索算法迭代加深优先搜索算法自动化系仪自教研室v盲目搜索盲目搜索& &启发式搜索启发式搜索状态空间图搜索状态空间图搜索广度优先搜索广度优先搜索深度优先搜索深度优先搜索迭代加深搜索迭代加深搜索A A搜索搜索A A* *搜索搜索状态组合爆炸状态组合爆炸自动化系仪自教研室64隐式部分隐式部分(362866 states)显式部分显式部分(14 states)571456312384

40、5671238456712384567（4）（6）（6）2123845671238456712384567（6）（5）（5）1238456712 384567（5）（7）1238456712384567（6）（7）12384567（5）813245671 2384567（7）123846（4）75Initial StateGoal自动化系仪自教研室 8数码问题数码问题 9! =362,880 states 15数码问题数码问题 1.3 x 1012 states24数码问题数码问题 1025 states100 millions states/sec 109 yearsv盲目搜索的困境盲目搜索

41、的困境- -状态组合爆炸状态组合爆炸！自动化系仪自教研室启发性知识 就是与被求解问题自身特性相关的知识，包括被求解问题的解的特性、解的分布规律和在实际当中求解此类问题的经验、技巧等，对应于问题求解框架中的控制性知识。v启发式搜索的基本思想启发式搜索的基本思想启发函数启发函数 要实现启发式搜索，需要把启发性知识形式化，即用一要实现启发式搜索，需要把启发性知识形式化，即用一定的函数表示出来，通过函数计算来评价每种选择的价值定的函数表示出来，通过函数计算来评价每种选择的价值大小，用以大小，用以指导搜索过程指导搜索过程，这样的函数称为启发函数。，这样的函数称为启发函数。 启发式搜索启发式搜索自动化系仪

42、自教研室v启发式搜索的基本思想启发式搜索的基本思想用启发函数来导航，其搜索算法就要在状态图一般搜索用启发函数来导航，其搜索算法就要在状态图一般搜索算法基础上再算法基础上再增加启发函数值增加启发函数值的的计算计算与与传播传播过程，并且过程，并且由由启发函数值启发函数值来来确定确定节点的节点的扩展顺序扩展顺序。启发式搜索启发式搜索自动化系仪自教研室在很多实际问题中，已经付出的实际代价是必须考虑的，如TSP问题等。将两者同时考虑，用于指导搜索的算法称为A算法和A*算法。启发函数是对当前结点到达目标结点未来可能要付启发函数是对当前结点到达目标结点未来可能要付出的代价的估计。出的代价的估计。在全局择优和

43、局部择优搜索算法中，都没有考虑从在全局择优和局部择优搜索算法中，都没有考虑从初始结点到当前结点已经付出的实际代价。初始结点到当前结点已经付出的实际代价。v启发函数启发函数/ /代价函数代价函数/ /估价函数估价函数启发式搜索启发式搜索自动化系仪自教研室为了防止在单独利用启发函数的时候误入歧途，将启发函为了防止在单独利用启发函数的时候误入歧途，将启发函数数h h（x x）与代价函数）与代价函数g g（x x）相结合，即初始节点）相结合，即初始节点S S0 0到达节到达节点点x x处已付出的处已付出的代价与代价与节点节点x x 到达目标节点到达目标节点S Sg g的的接近程度估接近程度估计值总和计

44、值总和。v估价函数估价函数初始节点初始节点节点节点n 目标节点目标节点g(n) h(n) f f（x x） g g（x x）h h（x x）启发式搜索启发式搜索自动化系仪自教研室lAlgorithm A (A A算法算法)lUniform-Cost search （等代价搜索等代价搜索）分支界限分支界限/瞎子爬山瞎子爬山lGreedy Search （贪婪搜索贪婪搜索）lAlgorithm A* (A A星算法星算法) f(n) = g(n) f(n) = h(n) f(n) = g(n) + h(n) f(n) = g(n) + h(n) , h(n) = h*(n) v估价函数及其相应算法

45、估价函数及其相应算法启发式搜索启发式搜索自动化系仪自教研室开始开始把把S放入放入OPEN表表OPEN表为空表？表为空表？把第一个节点把第一个节点(n)从从OPEN表移至表移至CLOSED表表n为目标节点吗？为目标节点吗？把把n的后继节点放入的后继节点放入OPEN表的表的末端，提供返回节点末端，提供返回节点n的指针的指针修改指针方向修改指针方向根据最佳优先根据最佳优先重排重排OPEN表表失败失败成功成功是是是是否否否否(1)(3)(4)(5)(6)(7)(7)(8)(9)OPEN CLOSED(1)(2)启发式搜索启发式搜索自动化系仪自教研室1.全局择优搜索基本思想：在OPEN表中保留所有已生成

46、而未考察的节点，并用启发函数h(x)对它们全部进行估价，从中选出最优节点进行扩展，而不管这个节点出现在搜索树的什么地方。2.局部择优搜索局部择优搜索基本思想：局部择优搜索是在启发性知识导航下的深度优基本思想：局部择优搜索是在启发性知识导航下的深度优先搜索，在先搜索，在OPEN表中保留所有已生成而未考察的结点，表中保留所有已生成而未考察的结点，对其中对其中新生成的每个子结点新生成的每个子结点x计算启发函数计算启发函数，从全部子结，从全部子结点中选出最优结点进行扩展，其选择下一个要考察结点的点中选出最优结点进行扩展，其选择下一个要考察结点的范围是刚刚生成的全部子结点，范围是刚刚生成的全部子结点，v

47、启发式搜索的两类基本策略启发式搜索的两类基本策略启发式搜索启发式搜索自动化系仪自教研室f f（x x） g g（x x）h h（x x）g g（x x）：对某一确定的节点，是确定的值。）：对某一确定的节点，是确定的值。h h（x x）：不同的问题启发函数的定义不同，相同的）：不同的问题启发函数的定义不同，相同的问题也可以定义出不同的启发函数。问题也可以定义出不同的启发函数。估价函数定义探讨估价函数定义探讨启发式搜索启发式搜索v如何设计合理的启发函数？如何设计合理的启发函数？衡量衡量启发式函数启发式函数h h（x x）优劣的标准是看其是否能够准优劣的标准是看其是否能够准确反映出节点确反映出节点x

48、 x到达目标的难易程度（距离）。到达目标的难易程度（距离）。自动化系仪自教研室（3）根据主观经验的主观打分等。在实际设计过程中，在实际设计过程中，启发函数是用来估计搜索树节点启发函数是用来估计搜索树节点x x与目标节点接近程度的一种函数，通常根据下列思与目标节点接近程度的一种函数，通常根据下列思路来选择路来选择启发函数：启发函数：（1）一个结点到目标结点的某种距离或差异的量度；）一个结点到目标结点的某种距离或差异的量度；（2）一个结点处在最佳路径上的概率；）一个结点处在最佳路径上的概率；启发式搜索启发式搜索v如何设计合理的启发函数？如何设计合理的启发函数？自动化系仪自教研室启发式搜索启发式搜索

49、v如何设计合理的启发函数？如何设计合理的启发函数？带有比原问题在操作上更少约束条件的问题称问原问题的带有比原问题在操作上更少约束条件的问题称问原问题的一个松弛问题一个松弛问题松弛问题松弛问题原问题的解原问题的解松弛问题的解松弛问题的解自动化系仪自教研室启发式搜索启发式搜索v如何设计合理的启发函数？如何设计合理的启发函数？带有比原问题在操作上更少约束条件的问题称问原问题的带有比原问题在操作上更少约束条件的问题称问原问题的一个松弛问题一个松弛问题松弛问题松弛问题松弛问题中最优解的代价函数是一个松弛问题中最优解的代价函数是一个admissible的启发函的启发函数！（代价函数的获取可通过移除原问题操

50、作中的约束条数！（代价函数的获取可通过移除原问题操作中的约束条件来得到）件来得到）自动化系仪自教研室启发式搜索启发式搜索v如何设计合理的启发函数？如何设计合理的启发函数？如果一个启发函数如果一个启发函数h(x)满足满足h(x)=h*(x),则该函数为一个则该函数为一个admissible的启发函数，其中的启发函数，其中h*(x)为原问题的最优解代价为原问题的最优解代价函数函数Admissibility原问题的解原问题的解松弛问题的解松弛问题的解自动化系仪自教研室1 48 3 27 6 5S01 2 38 47 6 5Sg估价函数估价函数f（x）g（x）h（x）g( (x) )用节点深度用节点深