人工智能（第4版）课件 启发式搜索

启发式搜索内容回顾人工智能的问题求解方法状态空间法内容回顾

状态空间法初始状态S0

目标状态Sk

操作符序列（O1，O2，…，Ok）……终点S1S2S3Sk-3Sk-2Sk-1…O1O2O3Ok-2Ok-1Ok起点Sk∈GS0内容回顾人工智能的问题求解方法状态空间法初始状态

目标状态操作符问题状态空间法的基本思想内容回顾人工智能的问题求解方法状态空间法初始状态

目标状态操作符问题状态空间法的基本思想搜索策略盲目搜索方法（非启发式搜索）内容回顾人工智能的问题求解方法状态空间法初始状态

目标状态操作符问题状态空间法的基本思想搜索策略盲目搜索方法（非启发式搜索）宽度优先搜索深度优先搜索盲目搜索方法12345679810......12345679810......宽度优先搜索深度优先搜索内容回顾人工智能的问题求解方法状态空间法初始状态

目标状态操作符问题状态空间法的基本思想搜索策略盲目搜索方法（非启发式搜索）宽度优先搜索深度优先搜索启发式搜索问题和思路——非启发式国际象棋：每一步对弈：平均35种走法；一个回合：(35)2种走法；一盘棋假如50个回合：(35)2*50

种走法；万亿次的计算机运算速度：1022

次/秒；所需时间：(35)2*50

/

1022≈103*50/1022

=10128秒

≈10120年非启发式搜索方法效率低。共性特征初始状态/算子/目标状态是确定的搜索空间是确定的空间太大如何有效的搜索这个空间？需要某些有关具体问题领域的特性信息——启发式信息启发式搜索的依据（1）人们善于利用一些线索来帮助自己选择搜索方向。（2）现实问题往往只需一个解，而不要求最优解或全部解。（3）启发式信息可以避免某些领域里的组合爆炸问题。启发式信息的表示如何将抽象的启发式信息具体化？一般有两种途径：启发式信息的表示（1）表示为估计函数确定一个启发式函数f(n),n

为被搜索的节点,它把问题状态的描述映射成问题解决的程度，通常这种程度用数值来表示，就是启发式函数的值。这个值的大小用来决定最佳搜索路径。启发式信息的表示（2）表示成规则如果存在一个有趣的二元函数f(x,y)，那么看看两变元相同时会发生什么？若f表示乘法：导致发现平方；若f表示集合并运算：导致发现恒等函数；若f表示思考：导致发现反省；若f表示谋杀：导致发现自杀。启发式函数的表示方法启发式函数是一种映射函数，它把对问题状态的描述映射成一种希望的程度。启发式函数设计得好，对有效引导搜索过程有着重要的作用。在有的情况下，非常简单的启发式函数搜索路径能够作出非常令人满意的估计,当然也有一些场合需要使用非常复杂的启发式函数。启发式函数能够估计已找到的状态与达到目标的有利程度。这样的启发式函数能够有效地帮助决定哪些后继节点应被产生。八数码问题283

1

64751

238

4765初始状态

S0

问题状态空间为：

a11

a12

a13a21

a22

a23a31

a32

a33目标状态

Sg

问题状态和操作的形式化①问题状态的形式化二维数组A，

aij

=0,1,2,…,8，(i,j=1,2,3)②操作的形式化操作集合F={f1，f2，f3，f4}f1：if空格左边不是边界then空格左移f2：if空格右边不是边界then空格右移f3：if空格上边不是边界then空格上移f4：if空格下边不是边界then空格下移a11

a12

a13a21

a22

a23a31

a32

a33启发式函数f=数字错放位置的个数，f=0，则达到目标。

28316475S0S1S2S3S4S5S6S7f(S0)=4f(S1)=3f(S2)=5f(S3)=6f(S4)=3f(S5)=4f(S6)=3f(S7)=4

28314765

28316475

28316475

23184765

2831647528314765

28314765启发式信息的表示当f值相同时如何决定走步?现在定义：f2=所有数字当前位置以最短路径走到正确位置的步数之和。在这个定义之下，各状态的启发式函数值为：

数码12345678

F2(S0）=1+1+0+0+0+1+0+2=5F2(S1）=1+1+0+0+0+0+0+2=4启发式信息的表示数码12345678F2(S2）=1+1+0+0+0+1+1+2=6F2(S3）=1+1+0+0+1+1+0+2=6F2(S4）=1+1+0+0+0+0+0+1=3F2(S5）=1+1+0+0+0+1+0+2=5F2(S6）=1+2+0+0+0+0+0+2=5f(S4)=f(S6)=3,并且f2(S4)<f2(S6),下一步搜索从S4出发，产生其后继节点。启发式信息的表示(3)启发式函数应能够估计出可能加速达到目标的程度

这可以帮助确定当扩展一个节点时，那些节点应从搜索树中删除。启发式函数对搜索树(图)的每一节点的真正优点估计得愈精确,解题过程就愈少走弯路。八皇后问题在8*8棋盘要求放下8个皇后，要求没有一个皇后能够攻击其它皇后，即要使得在任何一行、一列或对角线上都不存在两个或两个以上的皇后。启发式信息的表示求解这个问题的过程为：

（a）定义状态空间。设状态空间的一点为：8*8矩阵。

（b）定义操作规则。按如下规则放置皇后：启发式信息的表示第一个皇后放第一行。第二个皇后放在第二行且不与第一个皇后在同一列或对角线的空格上。

……

第i个皇后放在第i行且不与前面i–1个皇后在同一列或对角线的空格上。

……

启发式信息的表示可使用如下启发式函数：设x为当前要放置Queen的空格f（x）=剩下未放行中能够用来放Queen的空格数不难看出，f（x）愈大愈好，应选择f（x）最大的空格来放置皇后。例如，在放置了三个Q后，第4个Q可放在第4行的A，B，C三个位置。启发式信息的表示（红线表示）

Q

Q

Q

QQ1.3.1启发式信息的表示（用红线表示）

Q

Q

Q

1.3.1启发式信息的表示（用红线表示）

Q

Q

Q

1.3.1启发式信息的表示（用红线表示）

Q

Q

Q

1.3.1启发式信息的表示（用红线表示）

Q

Q

Q

A

BC

1.3.1启发式信息的表示（用红线表示）

Q

Q

Q

A

BC

1.3.1启发式信息的表示（用红线表示）

Q

Q

Q

A

BC

1.3.1启发式信息的表示（用红线表示）

Q

Q

Q

A

BC

a

a

a

a

a

a

aa

1.3.1启发式信息的表示（用红线表示）

Q

Q

Q

A

BC

1.3.1启发式信息的表示（用红线表示）

Q

Q

Q

A

BC

1.3.1启发式信息的表示（用红线表示）

Q

Q

Q

A

BC

b

b

b

b

b

b

b

bb

1.3.1启发式信息的表示（用红线表示）

Q

Q

Q

A

BC

c

c

c

c

c

c

c

c

cc

1.3.1启发式信息的表示（用红线表示）

Q

Q

Q

A

BC

ab