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

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