人工智能课件：启发式图搜索

1、1一字棋种状态国际象棋有种状态西洋跳棋游戏种状态围棋种状态。这样的状态空间难以或者说不可能遍历搜索，则必须采用，以减少搜索的3.33.3启发式图搜索启发式图搜索启发式信息启发式信息 无信息搜索一般需要产生大量的节点，因而效率较低。为提高效率，我们可以使用一些问题相关的信息，以减小搜索量，这些信息就称为启发式信息。 启发式搜索启发式搜索使用启发式信息指导的搜索过程称为启发式搜索。启发式图搜索: 对节点排序。23.33.3启发式图搜索启发式图搜索3九宫棋盘，双方轮流摆棋子X/O 三子一线（一行，一列或一条对角线）在9个位置上摆放空，X，O有种棋局共有987即种不同的棋局状态用剪枝以减少状态空间：第

2、一步实际上只有三种走法，角、边的中央和棋盘正中，这时状态空间的大小为在状态空间的第二层上，由对称性还可进一步减少到。3.33.3启发式图搜索启发式图搜索4使用 只须搜索占据棋盘正中位置的棋局状态，而其他的各种棋局状态连同它们的延伸棋局状态都不必再考虑了只留三分之一状态空间 X X X 赢的机率 赢的机率 3.33.3启发式图搜索启发式图搜索5使用每状态旁标记其启发值3.33.3启发式图搜索启发式图搜索6：估计待搜索结点的“有希望”程度，并依此给它们排定次序（在open表）：任意一种函数，如有的定义为结点x处于最佳路径上的概率，或是x结点和目的结点之间的距离或差异，或是x格局的得分等等3.33.

3、3启发式图搜索启发式图搜索例子例子: : 八数码问题评价函数 f(n) = d(n) + W(n) d(n): 节点n的深度; W(n):与目标相比, 错位的数字数目;1238476528316475初始状态目标状态 73.33.3启发式图搜索启发式图搜索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

4、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)K(5)L(5)M(7)目标12345612384765例子例子: eight-puzzlef(n) = g(n) + h(n)f(n) = g(n) + h(n)g(n): g(n): 节点节点n n的深度的深度; ;h(n):h(n):与目标相比与目标相比, , 错位的数字数目错位的数字数目; ;893.33.3启发式图搜索启发式图搜索10初始 s(4) 2 8 3 1 2 3 1 6 4 8 4 7 5 7 6 5 目的（0）（下页）粗箭头线（下页）粗箭头线为解路，图

5、中状态旁括号内的数字表示该状态的估价函数值，其估价函数估价函数定义为：f(n) = d(n) + w(n)f(n) = d(n) + w(n)其中d(n)代表状态的深度，每步为单位代价 w(n)表示以“不在位”的将牌数作为启发信息的度量3.33.3启发式图搜索启发式图搜索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

6、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)K(5)L(5)M(7)目标12345612384765例子例子: eight-puzzlef(n) = g(n) + h(n)f(n) = g(n) + h(n)g(n): g(n): 节点节点n n的深度的深度; ;h(n):h(n):与目标相比与目标相比, , 错位的数字数目错位的数字数目; ;1112 3.33.3启发式图搜索启发式图搜索13：当我们要求估价函数f(n)中的h(n)都小于等于h*(n)即：3.33.3启发式图搜索启发式图搜索14八数码

7、例中的八数码例中的即为即为h(n),h(n),它表示了它表示了“不在位不在位”的将牌的将牌数，这个数，这个w(n)w(n)是否满足是否满足的条件？的条件？3.33.3启发式图搜索启发式图搜索15八数码例中的即为h(n),它表示了“不在位”的将牌数，这个w(n)满足了的条件，因此，前面页的八数码A搜索树是A*搜索树，所得的解路为最优解路,其步数为状态L(5)上所标注的3.33.3启发式图搜索启发式图搜索AradBucharestOradeaZerindFaragasNeamtIasiVasluiHirsovaEforieUrziceniGiurguiPitestiSibiuDobretaCraiovaRimnicuMehadiaTimisoaraLugoj8792142869886211101909915171751401181117075120138