A星算法求解八數(shù)碼問(wèn)題

1 A 算法求解八數(shù)碼問(wèn)題算法求解八數(shù)碼問(wèn)題 1 八數(shù)碼問(wèn)題描述 所謂八數(shù)碼問(wèn)題起源于一種游戲 在一個(gè) 3 3 的方陣中放入八個(gè)數(shù)碼 1 2 3 4 5 6 7 8 其中一個(gè)單元格是空的 將任意擺放的數(shù)碼盤(pán) 城初始狀 態(tài) 逐步擺成某個(gè)指定的數(shù)碼盤(pán)的排列 目標(biāo)狀態(tài) 如圖 1 所示 圖 1 八數(shù)碼問(wèn)題的某個(gè)初始狀態(tài)和目標(biāo)狀態(tài) 對(duì)于以上問(wèn)題 我們可以把數(shù)碼的移動(dòng)等效城空格的移動(dòng) 如圖 1 的初始排列 數(shù)碼 7 右移等于空格左移 那么對(duì)于每一個(gè)排列 可能的一次數(shù)碼移動(dòng)最多只有 4 中 即空格 左移 空格右移 空格上移 空格下移 最少有兩種 當(dāng)空格位于方陣的 4 個(gè)角時(shí) 所以 問(wèn)題就轉(zhuǎn)換成如何從初始狀態(tài)開(kāi)始 使空格經(jīng)過(guò)最小的移動(dòng)次數(shù)最后排列成目標(biāo)狀態(tài) 2 八數(shù)碼問(wèn)題的求解算法 2 1 盲目搜索 寬度優(yōu)先搜索算法 深度優(yōu)先搜索算法 2 2 啟發(fā)式搜索 啟發(fā)式搜索算法的基本思想是 定義一個(gè)評(píng)價(jià)函數(shù) f 對(duì)當(dāng)前的搜索狀態(tài)進(jìn)行評(píng)估 找出一個(gè)最有希望的節(jié)點(diǎn)來(lái)擴(kuò)展 先定義下面幾個(gè)函數(shù)的含義 f n g n h n 1 式中 g n 表示從初始節(jié)點(diǎn) s 到當(dāng)前節(jié)點(diǎn) n 的最短路徑的耗散值 h n 表示從當(dāng)前 節(jié)點(diǎn) n 到目標(biāo)節(jié)點(diǎn) g 的最短路徑的耗散值 f n 表示從初始節(jié)點(diǎn) s 經(jīng)過(guò) n 到目標(biāo)節(jié)點(diǎn) g 的最短路徑的耗散值 評(píng)價(jià)函數(shù)的形式可定義如 2 式所示 f n g n h n 2 其中 n 是被評(píng)價(jià)的當(dāng)前節(jié)點(diǎn) f n g n 和 h n 分別表示是對(duì) f n g n 和 h n 3 個(gè)函數(shù)值的估計(jì)值 利用評(píng)價(jià)函數(shù) f n g n h n 來(lái)排列 OPEN 表節(jié)點(diǎn)順序的圖搜索算法稱為算法 A 在 A 算法中 如果對(duì)所有的 x h x h x 3 成立 則稱好 h x 為 h x 的下界 它表示某種偏于保守的估計(jì) 采用 h x 的下界 h x 為啟發(fā)函數(shù)的 A 算法 稱為 A 算法 針對(duì)八數(shù)碼問(wèn)題啟發(fā)函數(shù)設(shè)計(jì)如下 f n d n p n 4 其中 A 算法中的 g n 根據(jù)具體情況設(shè)計(jì)為 d n 意為 n 節(jié)點(diǎn)的深度 而 h n 設(shè)計(jì)為 2 g SUC g OLD SUC OLD 把它添加到 BESTNDOE 的后繼結(jié)點(diǎn)表中 重新確定 OLD 的父輩節(jié)點(diǎn)為 BESTNODE 并修正父輩節(jié)點(diǎn)的 g 值和 f 值 記下 g OLD 是 成功 SUC CLOSED 把 SUCCESSOR 放入 OPEN 表 添進(jìn) BESTNODE 的后 裔表 計(jì)算 f 值 是否 是 否 是 否 否 否 開(kāi)始 把 S 放入 OPEN 表 記 f h OPEN NULL 是 失敗 擴(kuò)展 BESTNODE 產(chǎn)生其后繼結(jié)點(diǎn) SUCCESSOR 選取 OPEN 表上未設(shè)置過(guò)的具有最小 f 值的節(jié) 點(diǎn) BESTNODE 放入 CLOSED 表 BESTNODE 是 目標(biāo)節(jié)點(diǎn) 建立從 SUCCESSOR 返回 BESTNODE 的指針 計(jì)算 g SUC g BES k BES SUC SUC OPEN 3 圖 2 A 算法流程圖 p n 意為放錯(cuò)的數(shù)碼與正確的位置距離之和 由于實(shí)際情況中 一個(gè)將牌的移動(dòng)都是單步進(jìn)行的 沒(méi)有交換拍等這樣的操作 所 以要把所有的不在位的將牌 移動(dòng)到各自的目標(biāo)位置上 至少要移動(dòng)從他們各自的位 置到目標(biāo)位置的距離和這么多次 所以最有路徑的耗散值不會(huì)比該值小 因此該啟發(fā) 函數(shù) h n 滿足 A 算法的條件 3 A 算法流程圖 如圖 2 4 A 算法總結(jié) 4 1 把起始狀態(tài)添加到開(kāi)啟列表 4 2 重復(fù)如下工作 a 尋找開(kāi)啟列表中 f 值最低的節(jié)點(diǎn) 我們稱它為 BESTNOE b 把它切換到關(guān)閉列表中 c 對(duì)相鄰的 4 個(gè)節(jié)點(diǎn)中的每一個(gè) 如果它不在開(kāi)啟列表 也不在關(guān)閉列表 把它添加到開(kāi)啟列表中 把 BESTNODE 作為這一節(jié)點(diǎn)的父節(jié)點(diǎn) 記錄這一節(jié)點(diǎn)的 f 和 g 值 如果它已在開(kāi)啟或關(guān)閉列表中 用 g 值為參考檢查新的路徑是否更好 更低 的 g 值意味著更好的路徑 如果這樣 就把這一節(jié)點(diǎn)的父節(jié)點(diǎn)改為 BESTNODE 并且重 新計(jì)算這一節(jié)點(diǎn)的 f 和 g 值 如果保持開(kāi)啟列表的 f 值排序 改變之后需要重新對(duì)開(kāi)啟 列表排序 d 停止 把目標(biāo)節(jié)點(diǎn)添加到關(guān)閉列表 這時(shí)候路徑被找到 或者沒(méi)有找到路徑 開(kāi)啟列 表已經(jīng)空了 這時(shí)候路徑不存在 4 3 保存路徑 從目標(biāo)節(jié)點(diǎn)開(kāi)始 沿著每一節(jié)點(diǎn)的父節(jié)點(diǎn)移動(dòng)直到回到起始節(jié)點(diǎn) 這 就是求得的路徑 5 數(shù)據(jù)結(jié)構(gòu) 采用結(jié)構(gòu)體來(lái)保存八數(shù)碼的狀態(tài) f 和 g 的值以及該節(jié)點(diǎn)的父節(jié)點(diǎn) struct Node int s 3 3 保存八數(shù)碼狀態(tài) 0 代表空格 int f g 啟發(fā)函數(shù)中的 f 和 g 值 struct Node next struct Node previous 保存其父節(jié)點(diǎn) 6 實(shí)驗(yàn)結(jié)果 如圖 3 所示 4 圖 3 A 算法求解八數(shù)碼問(wèn)題實(shí)驗(yàn)結(jié)果 7 源代碼 代碼 利用 A 算法求解八數(shù)碼問(wèn)題 八數(shù)碼問(wèn)題的啟發(fā)函數(shù)設(shè)計(jì)為 f n d n p n 其中 A 算法中的 g n 根據(jù)具體情況設(shè)計(jì)為 d n 意為 n 節(jié)點(diǎn)的深度 而 h n 設(shè)計(jì)為 p n 意為放錯(cuò)的數(shù)碼與正確的位置距離之和 后繼結(jié)點(diǎn)的獲取 數(shù)碼的移動(dòng)等效為空格的移動(dòng) 首先判斷空格上下左右的可移動(dòng)性 其次移動(dòng)空格獲取后繼結(jié)點(diǎn) include include include 八數(shù)碼狀態(tài)對(duì)應(yīng)的節(jié)點(diǎn)結(jié)構(gòu)體 5 struct Node int s 3 3 保存八數(shù)碼狀態(tài) 0 代表空格 int f g 啟發(fā)函數(shù)中的 f 和 g 值 struct Node next struct Node previous 保存其父節(jié)點(diǎn) int open N 0 記錄 Open 列表中節(jié)點(diǎn)數(shù)目 八數(shù)碼初始狀態(tài) int inital s 3 3 2 8 3 1 6 4 7 0 5 八數(shù)碼目標(biāo)狀態(tài) int final s 3 3 1 2 3 8 0 4 7 6 5 添加節(jié)點(diǎn)函數(shù)入口 方法 通過(guò)插入排序向指定表添加 void Add Node struct Node head struct Node p struct Node q if head next 考慮鏈表為空 q head next if p f next f 考慮插入的節(jié)點(diǎn)值比鏈表的第一個(gè)節(jié)點(diǎn)值小 p next head next head next p else while q next 考慮插入節(jié)點(diǎn) x 形如 a x f f q f p f q next p break 6 q q next if q next NULL 考慮插入的節(jié)點(diǎn)值比鏈表最后一個(gè)元素的值更大 q next p else head next p 刪除節(jié)點(diǎn)函數(shù)入口 void del Node struct Node head struct Node p struct Node q q head while q next if q next p q next p next p next NULL if q next NULL return free p q q next 判斷兩個(gè)數(shù)組是否相等函數(shù)入口 int equal int s1 3 3 int s2 3 3 int i j flag 0 for i 0 i 3 i for j 0 jnext int flag 0 while q if equal q s s flag 1 Old Node next q return 1 else q q next if flag return 0 計(jì)算 p n 的函數(shù)入口 其中 p n 為放錯(cuò)位的數(shù)碼與其正確的位置之間距離之和 具體方法 放錯(cuò)位的數(shù)碼與其正確的位置對(duì)應(yīng)下標(biāo)差的絕對(duì)值之和 int wrong sum int s 3 3 int i j fi fj sum 0 for i 0 i 3 i for j 0 j 3 j for fi 0 fi 3 fi for fj 0 fj 3 fj if final s fi fj s i j sum fabs i fi fabs j fj break return sum 獲取后繼結(jié)點(diǎn)函數(shù)入口 檢查空格每種移動(dòng)的合法性 如果合法則移動(dòng)空格得到后繼結(jié)點(diǎn) int get successor struct Node BESTNODE int direction struct Node Successor 擴(kuò)展 BESTNODE 產(chǎn)生其后繼結(jié)點(diǎn) SUCCESSOR int i j i 0 j 0 temp 8 for i 0 i 3 i for j 0 js i j BESTNODE s i j 獲取空格所在位置 for i 0 i 3 i for j 0 js i j 0 i 0 i j 0 j break switch direction case 0 if i 0 1 1 temp Successor s i 0 j 0 Successor s i 0 j 0 Successor s i 0 1 j 0 Successor s i 0 1 j 0 temp return 1 else return 0 case 1 if j 0 1 1 temp Successor s i 0 j 0 Successor s i 0 j 0 Successor s i 0 j 0 1 Successor s i 0 j 0 1 temp return 1 else return 0 case 2 if j 0 1 s i 0 j 0 Successor s i 0 j 0 Successor s i 0 j 0 1 Successor s i 0 j 0 1 temp return 1 else return 0 case 3 if i 0 1 s i 0 j 0 Successor s i 0 j 0 Successor s i 0 1 j 0 Successor s i 0 1 j 0 temp return 1 else return 0 9 從 OPen 表獲取最佳節(jié)點(diǎn)函數(shù)入口 struct Node get BESTNODE struct Node Open return Open next 輸出最佳路徑函數(shù)入口 void print Path struct Node head struct Node q q1 p int i j count 1 p struct Node malloc sizeof struct Node 通過(guò)頭插法變更節(jié)點(diǎn)輸出次序 p previous NULL q head while q q1 q previous q previous p previous p previous q q q1 q p previous while q if q p previous printf 八數(shù)碼的初始狀態(tài) n else if q previous NULL printf 八數(shù)碼的目標(biāo)狀態(tài) n else printf 八數(shù)碼的中間態(tài) d n count for i 0 i 3 i for j 0 js i j if j 2 printf n printf f d g d n n q f q g q q previous 10 A 子算法入口 處理后繼結(jié)點(diǎn) void sub A algorithm struct Node Open struct Node BESTNODE struct Node Closed struct Node Successor struct Node Old Node struct Node malloc sizeof struct Node Successor previous BESTNODE 建立從 successor 返回 BESTNODE 的指針 Successor g BESTNODE g 1 計(jì)算后繼結(jié)點(diǎn)的 g 值 檢查后繼結(jié)點(diǎn)是否已存在于 Open 和 Closed 表中 如果存在 該節(jié)點(diǎn)記為 old Node 比 較后繼結(jié)點(diǎn)的 g 值和表中 old Node 節(jié)點(diǎn) g 值 前者小代表新的路徑比老路徑更好 將 Old Node 的父節(jié)點(diǎn)改為 BESTNODE 并修 改其 f g 值 后者小則什么也不做 即不存在 Open 也不存在 Closed 表則將其加入 OPen 表 并計(jì)算其 f 值 if exit Node Open Successor s Old Node if Successor g g Old Node next previous BESTNODE 將 Old Node 的父節(jié)點(diǎn)改為 BESTNODE Old Node next g Successor g 修改 g 值 Old Node next f Old Node g wrong sum Old Node s 修改 f 值 排序 del Node Open Old Node Add Node Open Old Node else if exit Node Closed Successor s Old Node if Successor g g Old Node next previous BESTNODE Old Node next g Successor g Old Node next f Old Node g wrong sum Old Node s 排序 del Node Closed Old Node Add Node Closed Old Node else Successor f Successor g wrong sum Successor s Add Node Open Successor open N 11 A 算法入口 八數(shù)碼問(wèn)題的啟發(fā)函數(shù)為 f n d n p n 其中 A 算法中的 g n 根據(jù)具體情況設(shè)計(jì)為 d n 意為 n 節(jié)點(diǎn)的深度 而 h n 設(shè)計(jì)為 p n 意為放錯(cuò)的數(shù)碼與正確的位置距離之和 void A algorithm struct Node Open struct Node Closed A 算法 int i j struct Node BESTNODE inital Successor inital struct Node malloc sizeof struct Node 初始化起始節(jié)點(diǎn) for i 0 i 3 i for j 0 js i j inital s i j inital f wrong sum inital s inital g 0 inital previous NULL inital next NULL Add Node Open inital 把初始節(jié)點(diǎn)放入 OPEN 表 open N while 1 if open N 0 printf failure return else BESTNODE get BESTNODE Open 從 OPEN 表獲取 f 值最小的 BESTNODE 將 其從 OPEN 表刪除并加入 CLOSED 表中 del Node Open BESTNODE open N Add Node Closed BESTNODE if equal BESTNODE s final s 判斷 BESTNODE 是否為目標(biāo)節(jié)點(diǎn) printf success n print Path BESTNODE return 針對(duì)八數(shù)碼問(wèn)題 后繼結(jié)點(diǎn) Successor 的擴(kuò)展方法 空格 二維數(shù)組中的 0 12 上下左右移動(dòng) 判斷每種移動(dòng)的有效性 有效則轉(zhuǎn)向 A 子算法處理后繼節(jié)點(diǎn) 否則進(jìn)行下一 種移動(dòng) else Successor struct Node malloc sizeof struct Node Successor next NULL if get successor BESTNODE 0 Successor sub A algorithm Open BESTNODE Closed Successor Successor