人工智能狀態(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 代價(jià)樹的寬度優(yōu)先搜索5.2.6 代價(jià)樹的深度優(yōu)先搜索5.3 啟發(fā)式搜索戰(zhàn)略5.3.1 啟發(fā)信息與估價(jià)函數(shù)5.3.2 最正確優(yōu)先搜索5.3.3 A*算法 需求重點(diǎn)掌握的問(wèn)題用寬度優(yōu)先搜索和深度優(yōu)先搜索求解八數(shù)碼問(wèn)題；用代價(jià)樹的寬度優(yōu)先搜索和深度優(yōu)先搜索求解推銷員游覽問(wèn)題；用全局最正確優(yōu)先搜索八數(shù)碼問(wèn)題。形狀空間搜索戰(zhàn)略搜索是人工智能的根本問(wèn)題，

2、是推理不可分割的一部分問(wèn)題求解就是搜索過(guò)程搜索對(duì)應(yīng)的知識(shí)表示法：形狀空間表示法、與/或樹表示法 6對(duì)節(jié)點(diǎn)n進(jìn)展擴(kuò)展，將它的一切后繼節(jié)點(diǎn)放入OPEN表的末端，并為這些后繼節(jié)點(diǎn)設(shè)置指向父節(jié)點(diǎn)n的指針，然后轉(zhuǎ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), 并標(biāo)志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), 并標(biāo)志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, 計(jì)算f(n, mi):=g(n, mi)+h(mi);7, OPEN中的節(jié)點(diǎn)按f值從小到大排序；8, GO LOOP； 一個(gè)A算法的例子定義評(píng)價(jià)函數(shù)：f(n) = g(n) + h(n)g(n)為從初始節(jié)點(diǎn)到當(dāng)前節(jié)點(diǎn)的代價(jià)值h(n)為當(dāng)前節(jié)點(diǎn)“不在位的位置數(shù)2 8 31 6 47

5、51 2 38 47 6 5h計(jì)算舉例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ù)碼問(wèn)題h1(n) = “不