【正文】 M 中不能有 n 的祖先。但是 ， 對于這種搜索方式 ， 使用正確的評估函數(shù)是相當(dāng)重要的 ， 評估函數(shù)選擇的正確與否與搜索的效率直接相關(guān)。//目標(biāo)狀態(tài) JGState StateCur。 virtual ~CJiuG()。//搜索深度 int ComputeJO(JGState *jo)。//定義九宮結(jié)構(gòu) class CJiuG { public: JGState StateInit。 要想得到最優(yōu) 解和較高的搜索效率 的就需要使用 A*算法 搜索，九宮的所以排列有 9！種，也就是 362880 種排法，數(shù)據(jù)量是非常大的，我使用的 A*搜索， 相對于廣度優(yōu)先算法可以減少 很多 節(jié)點(diǎn)占用 的內(nèi)存， 提高了搜索效率 。 成功 失敗 是 否 是 否 24 4．選擇 open 上的第一個結(jié)點(diǎn)，把它添加到 close 里并命名為 n，且從 open中刪除。 } 路徑搜索的實(shí)現(xiàn) 最后介紹一下搜索函數(shù) [10]的原理，首先得到源數(shù)組，將其轉(zhuǎn)換成 WORD 型，與目標(biāo)比較，如果相同完成，不同就交換一下數(shù)據(jù)和空格位置，加入二叉樹，搜索下一個結(jié)果，直到?jīng)]有步可走了，在搜索剛剛搜索到的位置的子位置，這樣直到找到目標(biāo)結(jié)果為止，該程序的實(shí)現(xiàn)在函數(shù) bool CJiuG::Search()中 ,其原理圖如圖41 所示 。 m_nstep=0。 (false)。 return true。i++){ for(int j=0。x3。 } } resultstate[tempx][tempy]=srcstate[tempx1][tempy]。y++){ if(srcstate[x][y]==0){ tempx=x。 resultprestate=src。 for(int i=0。 } bool CJiuG::MoveRight(JGState *src,JGState *result) //右移 { int x,y,tempx,tempy。j3。x++){ for(y=0。i++){ for(j=i+1。 //除去 0，將其余 8 個數(shù)依次加入到數(shù)組中 for(i=0。以往的算法都以未找到解決方案且 open 表為空來作為當(dāng)前給定的初始與終結(jié)狀態(tài)互不可達(dá)的判斷依據(jù)。 (3)規(guī)則庫設(shè)計(jì) 0 在某一位置時，能選擇向左、向右、向上、向下移動中的哪幾種策略進(jìn)行移動，主要是由當(dāng)前 0 所處位置（更具體地說是當(dāng)前位置的行列號）和其祖父節(jié)點(diǎn)（為提高搜索效率，新擴(kuò)展的節(jié)點(diǎn)應(yīng)當(dāng)至少不為其祖父節(jié)點(diǎn)）所決定的。 根據(jù) A*算法的定義，當(dāng)前節(jié)點(diǎn)的代價值由估價函數(shù)給出，即： f(n)=ｇ (n)+h(n) 其中： g(x)是從初始節(jié)點(diǎn)到節(jié)點(diǎn) x 的最小代價； h(n)是啟發(fā)函數(shù)。但要在計(jì)算機(jī)上通過編程解決該問題，還應(yīng)當(dāng)解決該問題在計(jì)算機(jī)上表示的方式，并設(shè)計(jì)合適的啟發(fā)函數(shù)，以提高搜索效率。 15 圖 47 游戲規(guī)則 算法分析 問題描述 8 數(shù)碼問題又稱 9 宮問題，與游戲 “ 華容道 ” 類似。 自動演示 自動演示是由 游戲自動完成的。 空白模塊的移動是通過鼠標(biāo)左鍵移動。先載入一個內(nèi)存位圖，再從源視圖像位圖中選擇適當(dāng)?shù)膮^(qū)域?qū)⑵淇截惖絻?nèi)存位圖中，當(dāng)所有這些圖像方塊都繪制到內(nèi)存位圖后，再一次性地將整體圖像從內(nèi)存位圖拷貝到屏幕去。具體的模塊設(shè)計(jì)如圖 41 所示。 由定理 1 和定理 2 可知 ， 無論是對有限圖還是無限圖 ， A*算法都能夠找到某個目標(biāo)節(jié)點(diǎn)而結(jié)束。因此 ,A*算法必然會結(jié)束。 A*算法是一個很重要的啟發(fā)式搜索算法。其中最主要模塊是實(shí)現(xiàn)數(shù)字移動模塊和最優(yōu)解搜索模塊。 8 數(shù)碼游戲是廣受歡迎的一種智力游戲，能夠鍛煉人的思維能力 ， 動手 能力。對于八數(shù)碼問題的求解 ， 可以用錯位碼的個數(shù)作為狀態(tài)描述好壞的一個度量 g(n)： 即節(jié)點(diǎn)的錯位碼個數(shù) (即和目標(biāo)節(jié)點(diǎn)比較 , 位置不正確的數(shù)字個數(shù) )。 關(guān)鍵技術(shù)介紹 該游戲主要的功能模塊是最優(yōu)解搜索功能。 (2)CWinThread 類：是 CCmdTarget 的子類。 WizardBar 包含了 3 個相關(guān)的下拉列表框，分別是類 (Class)、過濾器 (Filter)和成員 (Member)。使用 ClassWizard，可以將成員函數(shù)或變量加入到一個類中，或修改已經(jīng)存在的函數(shù)和變量。 RourceView(資源視圖 )：顯示項(xiàng)目中所包含的資源文件 ， 展開文件夾可顯示所有的資源類型。 Developer Studio 采用標(biāo)準(zhǔn)的多窗口用戶界面，提供了大量實(shí)用工具以支持可視化編程 的特性，包括項(xiàng)目工作區(qū)、 AppWizard(應(yīng)用程序向?qū)?)、 ClassWizard(類向?qū)?)、 WizardBar(向?qū)Чぞ邨l )、Component Gallery(組件畫廊 )等。 第 四 章：主要是對游戲進(jìn)行設(shè)計(jì)，包括框架搭建、算法設(shè)計(jì)及分析。 簡單介紹了該游戲開發(fā)工具 Visual C++和 MFC，選擇這兩種開發(fā)工具簡化了游戲的界面的設(shè)計(jì)與實(shí)現(xiàn)。因此 ， 這種策略是完備的。盲目搜索是指在不具有對待定問題的任何有關(guān)信息的條件下 ， 按固定的步驟進(jìn)行的搜索 ， 如深度優(yōu)先搜索和廣度優(yōu)先搜索；啟發(fā)式搜索是指在搜索中加入了與問題有關(guān)的啟發(fā)性信息 ， 這些信息可以指導(dǎo)搜索朝著最有希望的方向前進(jìn) ， 加速問題的求解過程 ， 并找到最優(yōu)解 ， 如 A* 算法。 本程序使用的是微軟最新開發(fā)的軟件： Visual C++， VC++比 C 更簡潔，為可視化界面操作，利用類實(shí)現(xiàn)各種不同的功能。使用游戲軟 件自然是為了滿足人們對娛樂性的要求，而有些軟件大都采用 3D 設(shè)計(jì)對系統(tǒng)配置的要求較高。問 題給定初始位置和目標(biāo)位置 ,要求通過一系列的數(shù)碼移動 ,將初始狀態(tài)轉(zhuǎn)化為目標(biāo)狀態(tài)。其中的 MFC是由微軟公司編寫的一套專門用于 Windows 編程的 C++ 基礎(chǔ)類庫，它封裝了 Windows API 的絕大多數(shù)功能，為用戶開發(fā) Windows 應(yīng)用程序建立了一個非常靈活的應(yīng)用程序框架?，F(xiàn)在越來越多的人投入到這種小游戲的開發(fā)當(dāng)中， 它已經(jīng)成為一類必不可少的游戲軟件。再依據(jù)這種算法用可視化編程語言 VC+ + 來實(shí)現(xiàn)八數(shù)碼問題的求解過程 ， 取得了預(yù)期的搜索解 ， 提高了搜索效率。由于一個有解的問題可能含有無窮分支 ， 該搜索如果誤入無窮分枝 (即深度無限 )， 則不可能找到目標(biāo)節(jié)點(diǎn)。但是 ， 對于這種搜索方式 ， 使用正確的評估函數(shù)是相當(dāng)重要的 ， 評估函數(shù)選擇的正確與否與搜索的效率直接相關(guān)。 其中最優(yōu)解搜索功能主要是使用 了 A*算法來實(shí) 現(xiàn)最短路徑搜索。 第 七 章：對自己所做的工作進(jìn)行總結(jié)，同時對數(shù)碼游戲做了展望。 項(xiàng)目工作區(qū)底部有一組項(xiàng)目視圖切換選項(xiàng)卡 (包括 3 種視圖 )，用于從不同的角度查看項(xiàng)目中包含的工程和聯(lián)機(jī)文檔。 由于 AppWizard 生成的程序是一個基本的 Windows 程序，用戶可以直接編 5 譯并運(yùn)行。執(zhí)行對話框數(shù)據(jù)檢驗(yàn)、創(chuàng)建新類時，會自動加入方法和屬性 ， 建立整個類對象的框架模型 ，處理現(xiàn)有的類和類庫。 MFC 應(yīng)用程序框架 MFC 簡介： MFC[4](Microsoft Foundation Class)是由微軟公司編寫的一套專門用于 Windows 編程的 C++ 基礎(chǔ)類庫 ， VC++ 編程基本上都是圍繞著 MFC 類庫來進(jìn)行的。 (3)CWnd 類：窗口類，是 CcmdTarget 類的子類，從 CWnd 派生的類可以擁有自己的窗口，并對它進(jìn)行控制。 所謂啟發(fā)式搜索就是在搜索中要對每一個搜索的位置進(jìn)行評估，從中選擇最好、可能容易到達(dá)目標(biāo)的位置，再從這個位置向前進(jìn)行搜索，這樣就可以在搜索中省略大量無關(guān)的結(jié)點(diǎn)，提高了效率。 7 第 3 章 游戲的系統(tǒng)分析 需求分析 當(dāng)前各種游戲軟件層出不窮。問題給定初始位置和目標(biāo)位置 ， 要求通過一系列的數(shù)碼移動 ， 將初始狀態(tài)轉(zhuǎn)化為目標(biāo)狀態(tài)。 數(shù)字移動分析，通過分析空白滑塊的可移動方向，設(shè)計(jì)程序。 A*算法是可納的 ， 即它能在有限步內(nèi)終止并找到最優(yōu)解。 引理 1： 對無限圖 ， 如果從初始節(jié)點(diǎn) S0到目標(biāo)節(jié)點(diǎn) Sg有路徑存在 ， 且 A*算法不終止的話 ,則從 Open 表中選出的節(jié)點(diǎn)必將具有任意大的 f 值。因此 ， A*算法只能終止在最佳路徑上。 輸入模塊 初始狀態(tài) 目標(biāo)狀態(tài) 輸出模塊 步數(shù)輸出 最優(yōu)解 八數(shù)碼游戲 選擇模塊 人工 機(jī)器 自動演示 數(shù)字移動 自動演示 顯示走步 11 圖 42 邊界判斷流程圖 鼠標(biāo)交互設(shè)計(jì) 鼠標(biāo)左 鍵單擊事件，鼠標(biāo)左鍵事件 [7]是點(diǎn)擊可移動的數(shù)據(jù)塊，使得數(shù)據(jù)塊可進(jìn)行移動，如果達(dá)到邊界，則不可移動；反之，則可以繼續(xù)移動，如圖 43所示。點(diǎn)擊輸入初始狀態(tài)按鈕，玩家可以在編輯框中輸入 0~8 九個數(shù)字，則輸入的數(shù)據(jù)排列為初始態(tài)，游戲并把數(shù)字為 0 的模塊設(shè)置為可移動的空白模塊；然后在點(diǎn)擊輸入目標(biāo)狀態(tài)按鈕，玩家可以輸入想要達(dá)到的目標(biāo)狀態(tài)排列順序。并且在作真正的位置移動 前，需判斷其是否到了邊界而不能移動，當(dāng)檢測到?jīng)]有到達(dá)邊界時才開始作真正的移動操作。當(dāng)玩家想要實(shí)現(xiàn)自動演示功能時，需要先選擇機(jī)器按鈕，再點(diǎn)擊搜索最優(yōu)解按鈕，此時游戲?qū)袛鄶?shù)字排列實(shí)現(xiàn)的最少步數(shù)及該游戲是否有解。開始時，規(guī)則給定一個初始狀態(tài)和一個目標(biāo)狀態(tài)，并要求被試者對棋 格內(nèi)的符號經(jīng)過若干次移動由初始狀態(tài)達(dá)到目標(biāo)狀態(tài)，這個過程中只有空格附近的符號可以朝空格的方向移動，且每次只能移動一個符號。從這一點(diǎn)上看， open 表中的元素相互間即構(gòu)成了一個線性表，因此初步選定使用結(jié)構(gòu) 體表示問題的狀態(tài)。 (2)啟發(fā)函數(shù)的設(shè)計(jì) 根據(jù) A*算法的定義，啟發(fā)函數(shù)應(yīng)滿足： h(n)≤ h*(n)。 算法流程圖如圖 410 所示： 圖 410 算法流程圖 其中 ，擴(kuò)展節(jié)點(diǎn) n 的具體步驟如下： a) 首先判斷其是否在 closed 表已經(jīng)出現(xiàn)過 , 如果出現(xiàn)過，并且新節(jié)點(diǎn)的代價值比其小，則應(yīng)將其從 closed 表刪除，同時將新節(jié)點(diǎn)加入到 open 表；如果沒有出現(xiàn)過，則轉(zhuǎn) b。 判斷有無解 ，通過 返回 0 為偶，返回 1 為奇 .， 判斷是否有路徑。j3。 } } result=result%2。 tempy=y。 resultstate[tempx][tempy1] = 0。x++){ for(y=0。j3。 } bool CJiuG::MoveUp(JGState *src,JGState *result) //上移，上面的左移，右移，下面的下移，結(jié)構(gòu)一樣 { int x,y,tempx,tempy。 for(int i=0。//深度加一 resultprestate=src。y++){ if(srcstate[x][y]==0){ tempx=x。 } } resultstate[tempx][tempy]=resultstate[tempx+1][tempy]。 自動演示的原理是：此功能是根據(jù)圖的寬度優(yōu)先算法實(shí)現(xiàn)的。 (false)。i=()。生成一個叫 open的表 ， 把 n0 添加到這個表里。把 M添加到 G 中，并讓他們成為 n 的后繼。 A*算法的具體 類結(jié)構(gòu)如下： typedef struct JiuGongState{ int curdistance。//當(dāng)前狀態(tài) CPtrList OpenList。 bool MoveLeft(JGState *src,JGState *result)。 public: int m_ndepth。//下一個節(jié)點(diǎn)的指針 }JGState。 算法的具體實(shí)現(xiàn) 九宮問題的求解方法就是交換空格 (0)位置，直至到達(dá)目標(biāo)位置為止。并把他放入 closed 表中 擴(kuò)展 N，把它的后繼節(jié)點(diǎn)放入 open表的末端，提供返回到 N 的指針。 ()。 (false)。 (f