人工智能狀態(tài)空間搜索策略ppt課件

1、第五章 形狀空間搜索戰(zhàn)略第5章 形狀空間搜索戰(zhàn)略5.1 搜索的概念及種類5.1.1 搜索的概念5.1.2 搜索的種類5.2 盲目搜索戰(zhàn)略5.2.1 形狀空間圖的搜索戰(zhàn)略5.2.2 寬度優(yōu)先搜索5.2.3 深度優(yōu)先搜索5.2.4 有界深度優(yōu)先搜索5.2.5 代價樹的寬度優(yōu)先搜索5.2.6 代價樹的深度優(yōu)先搜索5.3 啟發(fā)式搜索戰(zhàn)略5.3.1 啟發(fā)信息與估價函數(shù)5.3.2 最正確優(yōu)先搜索5.3.3 A*算法 需求重點掌握的問題用寬度優(yōu)先搜索和深度優(yōu)先搜索求解八數(shù)碼問題；用代價樹的寬度優(yōu)先搜索和深度優(yōu)先搜索求解推銷員游覽問題；用全局最正確優(yōu)先搜索八數(shù)碼問題。形狀空間搜索戰(zhàn)略搜索是人工智能的根本問題，

2、是推理不可分割的一部分問題求解就是搜索過程搜索對應的知識表示法：形狀空間表示法、與/或樹表示法 6對節(jié)點n進展擴展，將它的一切后繼節(jié)點放入OPEN表的末端，并為這些后繼節(jié)點設置指向父節(jié)點n的指針，然后轉步驟2寬度優(yōu)先搜索1, G:=G0(G0=s), OPEN:=(s), CLOSED:=( );2, LOOP: IF OPEN=( ) THEN EXIT (FAIL);3, n:=FIRST(OPEN);4, IF GOAL(n) THEN EXIT (SUCCESS);5, REMOVE(n, OPEN), ADD(n, CLOSED);6, EXPAND(n) mi, G:=ADD(mi

3、, G);7, ADD(OPEN, mj), 并標志mj到n的指針;8, GO LOOP;深度優(yōu)先搜索1, G:=G0(G0=s), OPEN:=(s), CLOSED:=( );2, LOOP: IF OPEN=( ) THEN EXIT (FAIL);3, n:=FIRST(OPEN);4, IF GOAL(n) THEN EXIT (SUCCESS);5, REMOVE(n, OPEN), ADD(n, CLOSED);6, EXPAND(n) mi, G:=ADD(mi, G);7, ADD(mj, OPEN), 并標志mj到n的指針;8, GO LOOP;A算法1, OPEN:=(s

4、), f(s):=g(s)+h(s);2, LOOP: IF OPEN=( ) THEN EXIT(FAIL);3, n:=FIRST(OPEN);4, IF GOAL(n) THEN EXIT(SUCCESS);5, REMOVE(n, OPEN), ADD(n, CLOSED);6, EXPAND(n) mi, 計算f(n, mi):=g(n, mi)+h(mi);7, OPEN中的節(jié)點按f值從小到大排序；8, GO LOOP； 一個A算法的例子定義評價函數(shù)：f(n) = g(n) + h(n)g(n)為從初始節(jié)點到當前節(jié)點的代價值h(n)為當前節(jié)點“不在位的位置數(shù)2 8 31 6 47

5、51 2 38 47 6 5h計算舉例h(n) =4 2 8 31 6 47 51 2 3457 6 82 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)K(5)L(5)M(7)目的123456A*條件舉例8數(shù)碼問題h1(n) = “不