【正文】 的有序搜索法 . 同時， A*算法也是一種最好優(yōu)先的算法 . 只不過要加上一些約束條件罷了 . 由于在一些問題求解時，我們希望能夠求解出狀態(tài)空間搜索的最短路徑，也就是用最快的方法求解問題， A*就是解決此類問題 的 . 其中 A*算法的流程描述如下： 1．首先生成一個搜索的圖 G， 這個圖開始只有初始狀態(tài) n0。 } ()。 } for(int i=0。 (false)。 } (false)。 自動演示功能的代碼部分如下： void CJiugongDlg::OnButtonAuto() { 22 // TODO: Add your control notification handler code here if(m_binitdown==false||m_bobjdown==false){ MessageBox(初始狀態(tài)或者目標狀態(tài)沒有輸入 !!!,錯誤警告 )。玩家在能力不足時或想知道怎么能完成時，點擊菜單中的自動演示，系統(tǒng)將自動完成數(shù)字排序。 resultprestate=src。j++){ resultstate[i][j]=srcstate[i][j]。 for(int i=0。y3。 } bool CJiuG::MoveDown(JGState *src,JGState *result) //下移 { int x,y,tempx,tempy。 resultcurdistance=srccurdistance+1。j3。 } } } if(tempx==0) //判斷是否可移 return false。x++) //尋找空格位置 { for(y=0。 return true。 resultstate[tempx][tempy+1]=0。i++){ for(int j=0。 tempy=y。x3。 resultnextstate=NULL。} } resultstate[tempx][tempy] = srcstate[tempx][tempy1]。i3。y++){ if(srcstate[x][y]==0){ tempx=x。 for(x=0。j++){ if(temp[i]temp[j]) result++。 } } } //判斷奇偶性 for(i=0。i++){ for(j=0。 int k=0。 判斷該游戲是否有解得原理是根據(jù)初始態(tài)和目標態(tài) 的秩序計算數(shù)字的逆序奇偶性，若不同為奇數(shù)或同為偶數(shù)，則無路徑。 Y Y N 開始 初始化 s_0，把 s_0 送入 open 表 open 表為空？ 把 open 表中的首節(jié)點，從 open表中移出 ，放人 closed 表 節(jié)點為目標 節(jié)點？ 拓展節(jié)點 n，將有效子節(jié)點加入open 表，無效子節(jié)點刪除 成功，退出 失敗，退出 N 18 第 5 章 游戲功能模塊的具體實現(xiàn) 可達性判斷 可達性是指 8 數(shù)碼的最初狀態(tài)能否通過有限次的變化最終得到終態(tài)。這一段的具體過程可以參考程序流程部分。 在 8 數(shù)碼問題中，常用的啟發(fā)函數(shù)為： “ 不在位 ” 數(shù)碼個數(shù)，或數(shù)碼 “ 不在位 ” 的距離和。 最后，為提高程序的運行效率，減少程序擴展節(jié)點時搜索量，將當前 0 所處位置 (i_0： 0 在 s[3][3]中所處行號， j_0： 0 在 s[3][3]中所處列號 )也存儲在 DATA中。而為了保證在搜索到目標狀態(tài)后能夠順利復(fù)現(xiàn)尋優(yōu)路徑，當前狀態(tài)的 DATA 中還應(yīng)該包括一個指向其父節(jié)點的指針father，這樣，才能在達到目標狀態(tài)后，通過指 針 father 逐層回溯到初始狀態(tài)，即復(fù)現(xiàn)尋優(yōu)路徑。因此在表示當前狀態(tài)的變量中，必須要有能指向下一個擴展節(jié)點的指針，以完成對 open 表中元素的索引。 3 8 2 1 0 5 7 6 4 圖 48 初始狀態(tài) 圖 49 目標狀態(tài) 1 2 3 8 0 4 7 5 6 則要求以圖 48 為初始狀態(tài)，通過交換 0 和 0 的上、下、左、右四個方位的數(shù)字（每次只能和其中 一個交換），達到圖 49 所示目標狀態(tài)。并且通常把 8 個符號在棋格上的排列順序稱作 8 數(shù)碼的狀態(tài)。 圖 46 自 動拼圖 游戲規(guī)則 關(guān)于游戲的簡介，如玩家不會使用本游戲，可以參照游戲規(guī)則察看游戲的操作方法。自動演示 [6]的原理是：是在游戲開始之前，記錄各個數(shù)字的原始位置，及其目的位置，根據(jù)最短路徑算法，走一條最省時的路徑，然后連一條虛擬的線。當所有數(shù)字方塊的排列順序與游戲開始設(shè)置的排列順序完全一致時，游戲就勝利結(jié)束了。需要注意的是，數(shù)字要根據(jù)事件做出反應(yīng)，根據(jù)開始 結(jié)束 獲取文檔內(nèi)部數(shù)據(jù)的訪問操作權(quán)限 創(chuàng)建用于中介的內(nèi)存設(shè)備環(huán)境以及與其其關(guān)聯(lián)的內(nèi)存位圖 在內(nèi)存位圖中進行數(shù)字的拼湊繪制 14 移動方向，進行移動處理。 數(shù)據(jù)的移動 對于空白方塊的移動，將用如下方法 ： 在原始初始化好的地圖數(shù)據(jù)的基礎(chǔ)上，先將分割后的數(shù)據(jù)區(qū)域中數(shù)字為 0 的一塊地方設(shè)置成為可移動模塊，以便騰出一個方塊位置，供相鄰的數(shù)字移動。 數(shù)據(jù)輸入與輸出 該游戲的數(shù)據(jù)輸入是通過鍵盤進行操作的，限制只能輸入 0~8 的數(shù)字。 圖 44 主窗體界面 圖像的繪制 游戲區(qū)域的視圖繪制 [6]較為簡單。流程圖如圖 42 所示。 10 第 4 章 游戲功能模塊設(shè)計 系統(tǒng)模塊設(shè)計 8 數(shù)碼游戲程序的整體功能模塊 [6]，里面包含數(shù)據(jù)輸入、功能選擇 、輸出模塊等。 假設(shè) A*算法未能終止在最佳路徑上 ， 而是終止在某個目標節(jié)點 t 處 ， 則有 f(t)=g(t)f*(S0) 但由引理 2 可知 ， 在 A*算法結(jié)束前 ,必有最佳路徑上的一個節(jié)點 n’在 Open表中 ， 且有 f(n’) ≤ f*(S0)f(t), 這時 ， A*算法一定會選擇 n’來擴展 ,而不可能選擇 t， 從而也不會去測試目標節(jié)點 t， 這就與假設(shè) A*算法終止在 目標節(jié)點 t 相矛盾。 定理 3： A*算法是可采納的 ， 即若存在從初始節(jié)點 S0到目標節(jié)點 Sg 的路徑 ， 則 A*算法必能結(jié)束在最佳路徑上。因此 ,算法必定會成功結(jié)束。 證明： 首先證明算法必定會結(jié)束。 一般來說 ， 對任意一個狀態(tài)空間圖 ,當從初始節(jié)點到目標節(jié)點有路徑存在時 ，如果搜索算法能在有限步內(nèi)找到一條從初始節(jié)點到目標節(jié)點的最佳路徑 ， 并在此路徑上結(jié)束 ， 則稱該搜索算法是可納的。通過比較，該游戲選擇了 A*算法來實現(xiàn)該功能。所以，可以把這些功能劃分為區(qū)域，設(shè)計成按鈕的形式，通過鼠標交互功能呢，實現(xiàn)用戶的各種功能操作。 玩家可以選擇人工，自主進行空格的移動以達到最終狀態(tài)排列；也 可以選擇機器功能讓電腦自動進行排列 ，實現(xiàn)數(shù)字的最終狀態(tài)排列。 操作特性分析 八數(shù)碼是在 3 3 方格盤上 ,放有八個數(shù)碼 ， 剩下一個位置為空 ， 每一空格其上下左右的數(shù)碼可移至空格。成為人們在工作之余不可或缺的好伙伴。則評估函數(shù)為 f(n )=g(n)+h(n)： 表示從初始節(jié)點到節(jié)點 n的一條最佳路徑的實際代價 h(n)加上從節(jié)點 n到目標節(jié)點的一條最佳路徑的代價之和 ， 最終可以找到一條從初始節(jié)點到目標節(jié)點的最佳路徑的代價。然后 , 搜索就可能沿著某個被認為是最有希望的邊緣區(qū)段向外擴展 。 A*算法 是一種常用的啟發(fā)式搜索算法 。 (4)文檔類 CDocument 類：是 CCmdTarget 類的子類，負責封裝和維護文檔。應(yīng)用程序類 CWinApp 是 CWinThread 的子類，封裝了初始化、運行、終止應(yīng)用程序 的代碼。 6 MFC 類庫包括： (1)CCmdTarget 類：是 CObject 類的子類，它是 MFC 庫中所有具有消息映射屬性的類的公共基類。這些代碼包括由 Visual C++自帶的組件和從用戶工程中增 加到 Gallery 中去的用戶自定義組件。 實用 WizardBar 還可以增加一個新類，建立一個新的函數(shù)或方法，跳到一個已存在的函數(shù)或方法。 使用 ClassWizard 可 以實現(xiàn)創(chuàng)建新類，映射消息到函數(shù)，新建或刪除消息處理函數(shù)，查看已被處理的消息并跳到消息處理代碼處，定義成員變量。 ClassWizard 所能識別的類必須在 ClassWizard 數(shù)據(jù)庫文件 (.CLW)中登記。接著用戶還可以指定其具有一些特性，如多文檔接口或工具條 、 是否對數(shù)據(jù)庫、 OLE 的支持等，然后 AppWizard 生成一些文件，這些文件構(gòu)成程序的框架。 FileView(文件視圖 )：顯示所創(chuàng)建的工程 ， 展開文件夾可以查看工程中所包含的文件。在一個項目工作區(qū)中，可以處理一個工程和它所包含的文件、一個工程的子工程、多個相互獨立的工程、多個相互依賴的工程。 Developer Studio 包含了一個文本編輯器、資源編輯器、工程編譯工具、一個增量連接器、源代碼瀏覽器、集成調(diào)試工具以及一套聯(lián)機文檔 (MSDN)。 第 六 章：主要介紹了游戲的部分數(shù)據(jù)測試 ，以檢測游戲的主要功能是否能夠準確執(zhí)行 。 第二章：主要是對游戲主要開發(fā)工具 VisualC++、 MFC 的概述 、使用的主要技術(shù)。本論文主要工作內(nèi)容是該游戲的 主 要的功能模塊的設(shè)計和實現(xiàn)，如：判斷游戲是否有解，空白模塊移動，自動演示模塊，最優(yōu)解搜索功能的實現(xiàn)，及鼠標交互 3 操作的功能。在前人的研究基礎(chǔ)上結(jié)合算法處理對 8 數(shù)碼游戲進行設(shè)計。 通過比較顯示出啟發(fā)式搜索的優(yōu)越性 ： 一方面 ， 當發(fā)現(xiàn)目標節(jié)點時 ， 可以同時找到從初始狀態(tài)到達目標狀態(tài)的一條最短路徑 ； 另一方面 ， 由于搜索不是盲目的 ， 因此不需要擴展每一層的所有節(jié)點 ， 只需要擴展最有希望到達目標的節(jié)點即可。廣度優(yōu)先搜索是從初始狀態(tài)一層一層向下找 ， 直到找到目標為止。深度優(yōu)先搜索是按照一定的順 序先搜索完一個分支 ， 再搜索另一個分支 ， 以至找到目標為止。在人工智能領(lǐng)域 ， 所提供的每種問題求解方法，都需要某種對解答 2 的搜索 ， 從提出問題 (即初始狀態(tài) )到問題的解決 (即最終狀態(tài) )， 有個求解的過程 ，也就是搜索過程。介紹了八數(shù)碼問題 , 然后在啟發(fā)式搜索算法上對 A* 算法定義進行了解釋 ， 并在其旨在提高搜索效率的方面作了比較 詳盡的介紹 ， 詳細描述了基于圖搜索算法的解決此類問題的一種啟發(fā)式搜索算法 A* 算法。 課題背景及意義 背景說明 8 數(shù)碼游戲操作能培養(yǎng)手眼協(xié)調(diào)能力─游戲需要耐心的操作 ， 以及手眼協(xié)調(diào)能力 ， 只要一不協(xié)調(diào)就不能將數(shù)據(jù)塊放在正確的位置。能夠滿