【正文】 錄解 。對于不同的搜索策略，節(jié)點在 OPEN 表中的排列順序是不同的。 一般來說，在滿足 h(n)≤ h*(n)的前提下， h(n)的值越大越好。} else { 對節(jié)點 x 進行擴展，其子節(jié)點集合為 {y0,y1,...,yk1}。 OPEN← OPEN+{yi}。 if(x==T) {記錄解 。其中， g*(x)是從初始狀態(tài) S0到狀態(tài) x 的最小代價； h*(x)是從狀態(tài) x 到目標狀態(tài) T 的最小代價，若有多個目標狀態(tài)，則為其中最小的一個。 A*算法涉及兩張表，即OPEN 表和 CLOSE 表。 void BranchBound() { 定義活結(jié)點列表 Q，一般是優(yōu)先隊列或者 FIFO 隊列 定義當初始狀態(tài)前活結(jié)點 CurrNode CurrNode 進隊列 。這個過程一直持續(xù)到找到所求的解或活結(jié)點表為空時為止[2]。 } for each(CurrentState 的后繼狀態(tài) NextState) { Backtrack(level + 1, NextState) } } 分支限界法簡介 分支限界法類似于回溯法，也是在問題的解空間上搜索問題解的算法。如果在當前擴展結(jié)點處不能再向縱深方向移動，則當前的擴展結(jié)點就成為死結(jié)點（所有的孩子結(jié)點已經(jīng)產(chǎn)生的結(jié)點稱做死結(jié)點），此時，應(yīng)往回移動（回溯）到最近的一個活結(jié)點處，并使這個活結(jié)點成為當前的擴展結(jié)點。窮舉搜索的思想是不管狀態(tài)優(yōu)劣， “ 一個都不放過 ” ，顯然是最沒有 “ 技術(shù)含量 ” 的，適用于問題規(guī)模較小或者找不到更好的搜索方法的情況，對于問題規(guī)模較大的情況下不適用。 圖 CClientSocket 類的設(shè)計 監(jiān)聽套接字類的設(shè)計 監(jiān)聽套接字類 CLintenSocket 類繼承自 MFC 的 CSocket 類， CLintenSocket主要針對 OnAccept()（接收到套接字連接請求的處理函數(shù)）、 .m_hWnd（游戲窗體句柄）、 StartGame()（游戲開始）、 SetHWnd()（設(shè)置窗體句柄）等進行相應(yīng)定義。其詳細定義的相關(guān)類圖如圖 所示。一個系統(tǒng)的類模型可以由多張類圖描述，一個類也可以出現(xiàn)在幾張類圖中。 圖 單人游戲模式每隔 1 秒的扣時操作的順序圖 雙人對戰(zhàn)模式下的處理一次鼠標點擊事件的順序圖如圖 所示。 “ 游戲設(shè)置 ”子系統(tǒng)包含 “ 局域網(wǎng)連接設(shè)置 ” 功能模塊。本文選擇用順序圖對交互進行建模。 游戲牌對象的狀態(tài)，包括 “ 選中 ” 、 “ 未選中 ” 、 “ 清除 ”3 個狀態(tài)。 圖 局域網(wǎng)對戰(zhàn)模式活動圖 開發(fā)工具的選擇 在軟件開發(fā)行業(yè)中，各種可視化程序設(shè)計工具和編譯平臺如： Visual C++、Visual C、 Delphi、 C++Builder、 Java 等都是當今的主流。 活動圖的終止點，即活動圖的最后活動稱為結(jié)束活動，本身無活動。 表 “進行局域網(wǎng)雙人對戰(zhàn)游戲 ” 用例的用例描述 名稱 描述 用例名稱 進行局域網(wǎng)雙人對戰(zhàn)游戲 執(zhí)行者 玩家 目的 在局域網(wǎng)雙人對戰(zhàn)模式下進行游戲 類型 主要的 過程描述 1．玩家選擇作為同時作為服務(wù)端和客戶端，還是僅作為客戶端。 連連看局域網(wǎng)對戰(zhàn)游戲的用例圖，如圖 所示。在用例圖中標識用例名和執(zhí)行者名，用例圖中使用連線描述執(zhí)行者和用例之間的關(guān)系。一個系統(tǒng)的用例模型由若干用例圖組成，主要用于需求分析階段，它的建立是系統(tǒng)開發(fā)者和用戶反復討論的結(jié)果，表明了開發(fā)者和用戶對需求規(guī)格說明達成的共識。 論文內(nèi)容與結(jié)構(gòu) 本章為第 1 章，即緒論部分，本章之后，各章安排如下。傳統(tǒng)的軟件工程方法是面向過程的，將數(shù)據(jù)和處理過程分離，增加了軟件開發(fā)的難度。問題的求解實際上就是在這個圖中找到一條路徑可以從開始到結(jié)果。連連看游戲上手極其簡單，但是要熟練地掌握其中的操作與圖案消除技巧，難度卻不低，其普及程度也是非常高。 連連看游戲就是很經(jīng)典的小游戲。 objectoriented。程序開發(fā)出來后， 不僅正確實現(xiàn)了相關(guān)的功能和性能，而且具有良好的穩(wěn)定性、可維護性和可擴充性，證明了分支限界法和面向?qū)ο蠹夹g(shù)在在連連看局域網(wǎng)對戰(zhàn)游戲開發(fā)中的可行性。 本文研究以面向?qū)ο蠹夹g(shù)為主要開發(fā)方法，以分支限界法作為兩張游戲牌的尋路算法，將傳統(tǒng)的連連看單機游戲擴充為局域網(wǎng)上的雙人對戰(zhàn)游戲，重點闡述了分支限界法與面相對象開發(fā)思想在連連看局域網(wǎng)對戰(zhàn)游戲中的應(yīng)用。 Lianliankan game。指以 互聯(lián)網(wǎng) 為傳輸媒介 ，以 游戲運營商 服務(wù)器和用戶計算機為處理終端，以游戲客戶端軟件為 信息交互 窗口的旨在實現(xiàn)娛樂、休閑、交流和取得虛擬成就的具有可持續(xù)性的個體性多人在線游戲。局域網(wǎng)連連看對戰(zhàn)這樣的智力游戲也被人們所接受，從而連連看從棋盤也走向了網(wǎng)絡(luò)，局域網(wǎng)連連看對戰(zhàn)不限制地點的模式深受連連看愛好者的喜愛。由于求解問題的過程中分枝有很多，主要是求解過程中求解條件的不確定性，不完備性造成的，使得求解的路徑很多這就構(gòu)成了一個圖，稱為狀態(tài)空間。 圖 僅 3 個物品的 01 背包問題的狀態(tài)空間樹 面向?qū)ο蠓椒ê喗? 隨著軟件形式化方法及新型軟件的開發(fā)，傳統(tǒng)的軟件工程方法的局限性逐漸暴露出來 [3,4]。面向?qū)ο蟪绦蛟O(shè)計的一些顯著的特性包括 [3,4]： 1．程序設(shè)計的重點在于數(shù)據(jù)而不是過程； 2．程序被劃分為所謂的對象； 3．數(shù)據(jù)結(jié)構(gòu)為表現(xiàn)對象的特性而設(shè)計； 4．函數(shù)作為對某個對象數(shù)據(jù)的操作，與數(shù)據(jù)結(jié)構(gòu)緊密的結(jié)合在一起； 5．重要數(shù)據(jù)被隱藏起來，不能為外部函數(shù)訪問； 6．對象之間可以通過函數(shù)溝通； 7．新的數(shù)據(jù)和函數(shù)可以在需要的時候輕而易舉的添加進來； 8．在程序設(shè)計過程中遵循由下至上（ bottomup）的設(shè)計方法。 用例模型（ Use Case Model） [4]是表達系統(tǒng)外部事物（執(zhí)行者）與系統(tǒng)之間交互的可視化工具。 用例圖（ Use Case Diagram） [4,5]描述了各種外部執(zhí)行者與系統(tǒng)所提供的用例（ use case）之間的連接。在進行局域網(wǎng)雙人對戰(zhàn)時，首先要設(shè)置局域網(wǎng)連接，因此 “ 局域網(wǎng)連接 ” 用例應(yīng)作為 “ 局域網(wǎng)雙人對戰(zhàn) ” 用例的擴展用例。 “ 進行局域網(wǎng)雙人對戰(zhàn)游戲 ” 用例的用例描述如表 所示。 遷移的開始端點，即活動圖的起始點稱為起始活動，其本身無活動。 圖 單人游戲模式活動圖 局域網(wǎng)雙人對戰(zhàn)游戲模式下的活動圖，如圖 所示。 游戲牌對象的狀態(tài)圖 經(jīng)過分析，可以得出，此次開發(fā)的連連看局域網(wǎng)對戰(zhàn)游戲程序的核 心部分是游戲牌對象。交互圖定義了四種圖，即：順序圖、通信圖、時間圖和交互概覽圖。 “ 游戲模式選擇 ” 子系統(tǒng)包含 “ 單人游戲 ” 、和 “ 局域網(wǎng)雙人對戰(zhàn) ”兩個功能模塊（這兩個模塊可以包含共同的、可以復用的子模塊）。 圖 單人游戲模式下的處理一次鼠標點擊事件的順序圖 單人游戲模式下，每隔 1 秒鐘之后的扣時操作的順序圖如圖 所示。類圖是系統(tǒng)的一種靜態(tài)模型，它是其他圖的基礎(chǔ)。 圖 CCard 類的設(shè)計 棋盤類的設(shè)計 棋盤類 CBoard 主要針對 m_nWidth（棋盤寬度）、 m_nHeight（棋盤高度）、m_nTypeNum（不同類型的花色數(shù)）、 m_nRemainCount（剩余游戲牌數(shù)）、m_nSpendTime（消耗的時間）、 m_nLimitTime（總共時限）、 Find()（路徑查找）、IsEmpty()（判斷當前位置是否為空）、 m_GameState（游戲狀態(tài)）、 m_IP（ IP 地址）、二維數(shù)組 m_ppDist（ m_ppDist[i][j]表示從某個網(wǎng)格出發(fā)到第 i 行第 j 列的網(wǎng)格需要的最少拐彎數(shù)次）、 m_bFind（是否存在路徑）、 ClearPair()（清除路徑）、Exchange()（改變棋盤當前布局）、 Find()（查找路徑）、 InMap()（判斷參數(shù)表示的行列位置是否在棋盤內(nèi)）、 GetHeight()（獲取游戲牌集合的行 數(shù)，棋盤行數(shù) = 游戲牌集合的行數(shù) + 2）、 GetWidth()（獲取游戲牌列數(shù)，棋盤列數(shù) = 游戲牌集合的列數(shù) + 2）、 GetTypeNum()（獲取游戲牌花色種類）、 Success()（判斷是否勝利）、 AddTime()（設(shè)置游戲時間）、 GetGameState()（獲取游戲狀態(tài)）等進行相應(yīng)定義。其詳細定義的相關(guān)類圖如圖 所示。 ? 算法設(shè)計 狀態(tài)空間搜索算法簡介 窮舉搜索法簡介 窮舉搜索法 [2]是編程中常用到的一種方法，通常在找不到解決問題的規(guī)律時對可能是解的眾多候選解按某種順序進行逐一枚舉和檢驗，并從中找出那些符合要求的候選解作為問題的解。這個開始結(jié)點就成為一個活結(jié)點（自身已生成但其孩子結(jié)點還沒有全部生成的結(jié)點稱為活結(jié)點），同時成為當前的擴展結(jié)點（正在產(chǎn)生孩子結(jié)點的結(jié)點稱為擴展結(jié)點），在當前的擴展結(jié)點處，搜索向縱深方向移至一個新結(jié)點，這個新結(jié)點就成為一個新的活結(jié)點，并成為當前擴展結(jié)點。 } if(CurrentState 肯定不包含問題的最優(yōu)解 ) { return。此后，從活結(jié)點表中取下一結(jié)點成為當前擴展結(jié)點，并重復上述結(jié)點擴展過程。 分支限界法可用偽代碼表示如下。 A*算法 [6]是一種啟發(fā)式搜索算法，在一定程度上，可以減少搜索的盲目性。且 f*(x)=g*(x)+h*(x)。 CLOSED← CLOSED+{x}。 predyi← x。 for(i← 0。 h(n)的值越大，攜帶的啟發(fā)性信息越多， A*算法搜索時擴展的節(jié)點就越少，搜索效率就越高。 OPEN 表的節(jié)點信息至少包含兩個域：節(jié)點所表示的狀態(tài)，以及父節(jié)點的指針。 return。 2．優(yōu)先隊列式分支限界法：優(yōu)先隊列式分支限界法將活結(jié)點表組織成一個優(yōu)先隊列，交按優(yōu)先隊列中規(guī)定的結(jié)點優(yōu)先級選取優(yōu)先級最高的下一個結(jié)點成為當前擴展結(jié)點。在搜索問題的解空間樹時，分支限界法與回溯法對當前擴展結(jié)點所使用的擴展方式不同。 void Backtrack(int level, STATETYPE CurrentState) { if(CurrentState 包含問題的解 ) { 記錄解 。回溯法有 “ 通用的解題法 ” 之稱。其詳細定義的相關(guān)類圖如圖 所示。 圖 CDraw 類的設(shè)計 控制器類的設(shè)計 控制器類 CControl，該類繼承自 MFC 的 CDialogEx 類， CControl 主要針對m_pDraw（控制器所控制的繪圖器指針）、 m_pBoard（控制器所控制的棋盤指針）、 m_nTimer（游戲定時器）、 m_nGameMode（游戲模式，單機還是局域網(wǎng)）、m_pClientSocket（客戶端套接字指針）、 m_pListenSocket（服務(wù)端的監(jiān)聽套接字指針）、 OnLButtonDown()（鼠標左鍵響應(yīng)事件）、 OnTimer()（定時器啟動響應(yīng)函數(shù)）、 GetBoard()（獲取棋盤指針）、 SendToSocket()（發(fā)送套接字數(shù)據(jù)包）、CloseAllSocket()（關(guān)閉所有套接字）、 GetGameMode()（獲取游戲模式，單機還是局域網(wǎng)）、 GetClientSocket()（獲取客戶端套接字）、 SetGameMode()（設(shè)置游戲模式，單機還是局域網(wǎng)）等進行相應(yīng)定義。長式圖形符號也是由一個矩形實績方框表示，但它用兩條實績分成 3 部分，上邊部分書寫類名，中間部分描述類的屬性，下邊部分描述類的操作。 圖 客戶端套接字處理接收到的數(shù)據(jù)包的順序圖 類圖建模 類圖的相關(guān)概念 由 UML 中的類圖和對象圖組成的可視化模型能有效地描述一個軟件系統(tǒng)，它具有強大的模型描述表達能力。玩家可以根據(jù)個人喜好來選擇游戲模式。 MVC 模式的優(yōu)點包括：低耦合性、高重用性、可適用性、較低的生命周期成本、快速的部屬、可維護性、以及有利于軟件的工程化管理等。在待開發(fā)的系統(tǒng)中，對象都是通過傳遞消息進行交互的。 系統(tǒng)的開發(fā)平臺和運行平臺，分別如表 和表 所示。玩家可以根據(jù)個人喜好來選擇游戲模式。 表 “設(shè)置局域網(wǎng)連接 ” 用例的用例描述 名稱 描述 用例名稱 設(shè)置局域網(wǎng)連接 執(zhí)行者 玩家 目的 設(shè)置局域網(wǎng)雙人對戰(zhàn)模式下的局域網(wǎng)連接 類型 主要的、基本的 過程描述 1．玩家輸入名稱，選擇將當前系統(tǒng)既作為整個游戲的服務(wù)端又作為自己的客戶端，還是僅作為客戶端，如果當前系統(tǒng)既作為服務(wù)端又作為客戶端，轉(zhuǎn) 2，否則轉(zhuǎn) 8； 2．輸入端口號； 3．創(chuàng)建監(jiān)聽，等到客戶端連接； 4．將自己同時作為客戶端，連接本機的服務(wù)端； 5．等待另一玩家客戶端的連接； 6．如果監(jiān)測到另一玩家的客戶端的連接請求，轉(zhuǎn) 7，否則轉(zhuǎn) 5； 7．如果包含自己在內(nèi)的連接數(shù)已經(jīng)超過 2 個，則拒絕該客戶端的連接； 8．接受另一玩家的客戶端的連接請求，并發(fā)送數(shù)據(jù)包給對方玩家，轉(zhuǎn)13； 9．輸入需要連接的服務(wù)端的 IP 地址和端口號； 10．發(fā)送連接請求給服務(wù)端；