【正文】 //計算狀態(tài)的奇偶性 CJiuG()。//初始狀態(tài) JGState StateObj。 A*算法屬于 啟發(fā)式搜索 ，其 的優(yōu)越性 在于 ： 一方面 ， 當發(fā)現目標節(jié)點時 ，可以同時找到從初始狀態(tài)到達目標狀態(tài)的一條最短路徑 ； 另一方面 ， 由于搜索不是盲目的 ， 因此不需要擴展每一層的所有節(jié)點 ， 只需要擴展最有希望到達目標的節(jié)點即可。 5．如果 n 是終態(tài)，那么問題得到解退出，否則到第 7 步。 23 圖 51 路徑搜索流程圖 算法描述與實現 算法描述 該游戲的最優(yōu)解搜索功能主要使用了 A*算法 [11]。 if(()==0){ MessageBox(無解或還沒有搜索 ,警告 )。 return。 } 自動演示模塊的具體實現 自動演示是由系統(tǒng)自動完成的。j3。x++){ for(y=0。 resultstate[tempx1][tempy]=0。 tempy=y。 resultnextstate=NULL。i3。 for(x=0。j++){ resultstate[i][j]=srcstate[i][j]。y3。j8。i3。本文采用通過判斷兩狀態(tài)各自逆序數之和的奇偶性是否相同來判斷兩狀態(tài)之間是否可達。 17 當然，按照 A*算法的思想，每擴展出一個新節(jié)點，都要判斷其是否為有效子節(jié)點，不為有效子節(jié)點的不能加入到 open 表中。 因此，在 DATA 還應包括表示當前節(jié)點代價、最小代價和啟發(fā)信息的 f、 ｇ、h。 (1)狀態(tài)的表示 在 A*算法中，需要用到 open 表和 closed 表，特別是在 open 表中，待擴展 16 節(jié)點間有很嚴格的擴展順序。意在給定的 33? 棋格的8 個格子內分別放一個符號，符號之間互不相同，余下的一格為空格。玩家在能力不足時或想知道怎么能完成時，點擊菜單中的自動拼圖，系統(tǒng)將自動完成拼圖。鼠標左鍵的移動是點擊操作區(qū)域的方向按鈕，使空白滑塊進行移動。圖像繪制流程如圖 45： 13 圖 45 8數碼游戲圖像繪制流程圖 根據上面的設計，可以開始繪制游戲區(qū)域了，游戲區(qū)域視圖繪制也需要在其相關的視圖類中重寫圖像繪制處 理函數到 jiugong 中去重寫，添寫相應代碼。 圖 41 8數碼游戲模塊圖 移動模塊和鼠標交互模塊流程圖設計 移動模塊設計 8 數碼游戲選擇人工按鈕時，需要判斷空白模塊的移動方向趨勢，如果可以則按玩家的選擇移動空白模塊，如果不能則不允許移動，并給出提示。 再證明 A*算法只能終止在最佳路徑上 (反證法 )。 然后證明算法一定會成功結束 ， 由于至少存在一條由初始節(jié)點到目標節(jié)點的路徑 ,設此路徑 S0= n0,n1 ,…,nk =Sg 算法開始時 ， 節(jié)點 n0 在 Open 表中 ， 而且路徑中任一節(jié)點 ni 離開 Open 表后 ,其后繼節(jié)點 ni+1 必然進入 Open 表 ， 這樣 ， 在 Open 表變?yōu)榭罩?， 目標節(jié)點必然出現在 Open 表中。如果一般圖搜索過程進行如下限制 ,則它就成為 A*算法： (1) 把 OPEN表中的節(jié)點按估價函數 f(x)= g(x)+h(x)的值從小到大進行排序 ； (2) g(x)是對 g*(x)的估計 ,g(x)0； (3) h(x)是 h*(x)的下界 ， 即對所有的 x 均有： h(x)≤ h*(x) 其中 ,g*(x)是從初始節(jié)點到節(jié)點 x 的最小代價 ， h*(x)是節(jié)點 x 到目標節(jié)點的最小代價 ， 若有多個目標節(jié)點 ， 則為其中最小的一個。 界面設計分析，該游戲可以由用戶實現輸入數據初始狀態(tài)和目標狀態(tài) 、 選擇實現方式、移動功能、選擇自動演示、設置搜索深度的功能。 ， 功能描述 該數碼游戲的基本功能：對于這個具有移動拼湊功能的游戲，其功能描述如下：玩家通過手動設置數字的初始狀態(tài)和最終狀態(tài)，玩家主要是對設置的初始狀態(tài)進行移動，使其最終排列成為玩家設置的最終狀態(tài)排列，玩家也可以選擇機器功能讓電腦自動進行排列，并可以自動演示其搜索過程，玩家還可以自己設置搜索的深度，一旦超過玩家設置的深度則算無 解。另外 ， 為了避免由于過分的優(yōu)化試探而進入到無目的的漫游 ， 加上一個深度因子 h(n)： 即搜索中節(jié)點 n 的深度。在該功能中，通過分析比較，選擇了 A*算法來實現該功能。 CWinThread 是所有線程類的基類，封裝了應用程序操作的多線程功能。 Component Gallery(組件畫廊 ) Component Gallery 是一個組件庫，保存著可以共享和重用的代碼。 Wizard 使函數或變量放在何處，如何稱呼它們以及其他一些細節(jié)問題大大簡化。 AppWizard(應用程序向導 ) AppWizard 是一個標準的 C++源 代碼生成器，它首先通過一系列的對話框來提示用戶輸入所需創(chuàng)建的程序信息。 項目工作區(qū) 在 Developer Studio 中，項目工作區(qū)用于組織項目、元素以及項目信息在屏幕上的顯示方式。 第 五 章：主要是進行游戲的實現，包括游戲的界面、核心功能、用戶交互操作的實現。通過系統(tǒng)的分析和策劃，實現了游戲的主要功能。以上兩種搜索有一個很大的缺陷 ， 就是它們都是在一個給定的狀態(tài)空間中窮舉 ， 極容易遇到以下問題：搜索中易出現循環(huán) ， 即訪問某一個狀態(tài)后又來訪 問該狀態(tài)；搜索路徑不佳便無法得到較好的中間狀態(tài)集 (即中間狀態(tài)集的元素數量過大 )；搜索過程中訪問了過多的無用狀態(tài) ， 這些狀態(tài)對最后的結果無幫助。 八數碼游戲的研究現狀主要是如何選擇更更快速 、 更高效地找到問題的解答。 課題意義 在人工智能領域中 ， 八數碼問題一直都是一個游戲難題。 在眾多游戲軟件中，也不乏一些小游戲的身影 ， 它們對系統(tǒng)的配置要求較低。 作為本游戲的開發(fā)工具， Visual C++成為首選。它具有可視化的編程界面、詳細的提示、以及完善的幫助文檔，使得我在軟件開發(fā)過程中少走了很多彎路，提高了我的開發(fā)效率。能夠滿足人們對娛樂性的需求 ， 是人們在完成工作 娛樂時候的最好選擇。介紹了八數碼問題 , 然后在啟發(fā)式搜索算法上對 A* 算法定義進行了解釋 ， 并在其旨在提高搜索效率的方面作了比較 詳盡的介紹 ， 詳細描述了基于圖搜索算法的解決此類問題的一種啟發(fā)式搜索算法 A* 算法。深度優(yōu)先搜索是按照一定的順 序先搜索完一個分支 ， 再搜索另一個分支 ， 以至找到目標為止。 通過比較顯示出啟發(fā)式搜索的優(yōu)越性 ： 一方面 ， 當發(fā)現目標節(jié)點時 ， 可以同時找到從初始狀態(tài)到達目標狀態(tài)的一條最短路徑 ； 另一方面 ， 由于搜索不是盲目的 ， 因此不需要擴展每一層的所有節(jié)點 ， 只需要擴展最有希望到達目標的節(jié)點即可。本論文主要工作內容是該游戲的 主 要的功能模塊的設計和實現，如：判斷游戲是否有解，空白模塊移動，自動演示模塊，最優(yōu)解搜索功能的實現，及鼠標交互 3 操作的功能。 第 六 章：主要介紹了游戲的部分數據測試 ，以檢測游戲的主要功能是否能夠準確執(zhí)行 。在一個項目工作區(qū)中，可以處理一個工程和它所包含的文件、一個工程的子工程、多個相互獨立的工程、多個相互依賴的工程。接著用戶還可以指定其具有一些特性，如多文檔接口或工具條 、 是否對數據庫、 OLE 的支持等，然后 AppWizard 生成一些文件，這些文件構成程序的框架。 使用 ClassWizard 可 以實現創(chuàng)建新類，映射消息到函數，新建或刪除消息處理函數，查看已被處理的消息并跳到消息處理代碼處，定義成員變量。這些代碼包括由 Visual C++自帶的組件和從用戶工程中增 加到 Gallery 中去的用戶自定義組件。應用程序類 CWinApp 是 CWinThread 的子類，封裝了初始化、運行、終止應用程序 的代碼。 A*算法 是一種常用的啟發(fā)式搜索算法 。則評估函數為 f(n )=g(n)+h(n)： 表示從初始節(jié)點到節(jié)點 n的一條最佳路徑的實際代價 h(n)加上從節(jié)點 n到目標節(jié)點的一條最佳路徑的代價之和 ， 最終可以找到一條從初始節(jié)點到目標節(jié)點的最佳路徑的代價。 操作特性分析 八數碼是在 3 3 方格盤上 ,放有八個數碼 ， 剩下一個位置為空 ， 每一空格其上下左右的數碼可移至空格。所以，可以把這些功能劃分為區(qū)域，設計成按鈕的形式，通過鼠標交互功能呢，實現用戶的各種功能操作。 一般來說 ， 對任意一個狀態(tài)空間圖 ,當從初始節(jié)點到目標節(jié)點有路徑存在時 ，如果搜索算法能在有限步內找到一條從初始節(jié)點到目標節(jié)點的最佳路徑 ， 并在此路徑上結束 ， 則稱該搜索算法是可納的。因此 ,算法必定會成功結束。 假設 A*算法未能終止在最佳路徑上 ， 而是終止在某個目標節(jié)點 t 處 ， 則有 f(t)=g(t)f*(S0) 但由引理 2 可知 ， 在 A*算法結束前 ,必有最佳路徑上的一個節(jié)點 n’在 Open表中 ， 且有 f(n’) ≤ f*(S0)f(t), 這時 ， A*算法一定會選擇 n’來擴展 ,而不可能選擇 t， 從而也不會去測試目標節(jié)點 t， 這就與假設 A*算法終止在 目標節(jié)點 t 相矛盾。流程圖如圖 42 所示。 數據輸入與輸出 該游戲的數據輸入是通過鍵盤進行操作的，限制只能輸入 0~8 的數字。需要注意的是，數字要根據事件做出反應，根據開始 結束 獲取文檔內部數據的訪問操作權限 創(chuàng)建用于中介的內存設備環(huán)境以及與其其關聯的內存位圖 在內存位圖中進行數字的拼湊繪制 14 移動方向，進行移動處理。自動演示 [6]的原理是：是在游戲開始之前，記錄各個數字的原始位置，及其目的位置，根據最短路徑算法，走一條最省時的路徑，然后連一條虛擬的線。并且通常把 8 個符號在棋格上的排列順序稱作 8 數碼的狀態(tài)。因此在表示當前狀態(tài)的變量中，必須要有能指向下一個擴展節(jié)點的指針，以完成對 open 表中元素的索引。 最后，為提高程序的運行效率，減少程序擴展節(jié)點時搜索量，將當前 0 所處位置 (i_0： 0 在 s[3][3]中所處行號， j_0： 0 在 s[3][3]中所處列號 )也存儲在 DATA中。這一段的具體過程可以參考程序流程部分。 判斷該游戲是否有解得原理是根據初始態(tài)和目標態(tài) 的秩序計算數字的逆序奇偶性，若不同為奇數或同為偶數，則無路徑。i++){ for(j=0。j++){ if(temp[i]temp[j]) result++。y++){ if(srcstate[x][y]==0){ tempx=x。} } resultstate[tempx][tempy] = srcstate[tempx][tempy1]。x3。i++){ for(int j=0。 return true。 } } } if(tempx==0) //判斷是否可移 return false。 resultcurdistance=srccurdistance+1。y3。j++){ resultstate[i][j]=srcstate[i][j]。玩家在能力不足時或想知道怎么能完成時，點擊菜單中的自動演示，系統(tǒng)將自動完成數字排序。 } (false)。 } for(int i=0。 A*算法在人工智能中是基于 A 算法的一種典型的啟發(fā)式搜索，主要是對估價函數加以特別的定義和描述時，從而得到一種具有較強的啟發(fā)能力的有序搜索法 . 同時， A*算法也是一種最好優(yōu)先的算法 . 只不過要加上一些約束條件罷了 . 由于在一些問題求解時，我們希望能夠求解出狀態(tài)空間搜索的最短路徑，也就是用最快的方法求解問題， A*就是解決此類問題 的 . 其中 A*算法的流程描述如下： 1．首先生成一個搜索的圖 G， 這個圖開始只有初始狀態(tài) n0。 6．把 n 結點擴展，生成其后續(xù)狀態(tài)集 M，注意