【正文】 i++){ if(yi不屬于 OPEN 且 yi不屬于 CLOSED) { g(yi)← g(x)+C(x,yi)。 while(OPEN≠ Φ且 found==false) { x← OPEN 表中第一個節(jié)點 。 CLOSE 表的節(jié)點信息至少包含三個域：節(jié)點的編號、節(jié)點 所表示的狀態(tài)，以及父節(jié)點的指針。 } 將 NextNode 插入到 Q中 。結點優(yōu)先級的高低與 p 值大小相關，根據(jù)問題的不同情況，采用大根堆或小根堆來描述優(yōu)先隊列。活結點一旦成為擴展結點，就一次性產(chǎn)生其所有孩子結點。 } if(CurrentState 是終止狀態(tài) ) { return。回溯法是一個既帶有系統(tǒng)性又帶有跳躍性的搜索算法。其詳細定義的相關類圖如圖 所示。 圖 CControl類的設計 客戶套接字類的設計 客戶套接字 CClientSocket 類繼承自 MFC 的 CSocket 類。 通過以上的分析，可以初步得出連連看局域網(wǎng)對戰(zhàn)游戲類關系圖，如圖 所示： 圖 游戲的類關系圖 游戲牌類的設計 該類主要針對 m_nIndex（游戲牌序號）、 m_bIsNone（是否能被清除）、m_Pos（當前位置）、 Clear()（清除游戲牌）、 SetPos()（設置位置）、 SetIndex()（設置游戲牌序列號）、 m_bSelected（游戲牌是否選中）、 GetIndex()（獲取游戲牌序列號）、 GetPos()（獲取當前位置）、 IsNone()（判斷是否為空）、 HasPic()（將當前位置改為非空函數(shù)）、 Selected()（選中游戲牌）等進行相應定義。 類圖由若干類的圖形符號及表示其之間關系的圖形符號組成。結合之前的用例描述，分析游戲系統(tǒng)的業(yè)務流程，得出了連連看局域網(wǎng)對戰(zhàn)游戲系統(tǒng)的活動圖。 這里可以將棋盤對象和游戲牌對象的集合看作游戲的模型，此外，還需要編寫一個繪圖類，繪圖類的對象負責在界面上通過 Windows GDI 函數(shù)將棋盤及其內(nèi)部的游戲牌等對象在游戲對話框繪制出來，還需要編寫一個控制器類，控制器類的對象通過接收玩家的鼠標控制，改變棋盤及其游戲牌集合的某些狀態(tài)，并控制繪圖器對象將模型對應的對象改變后的結果，重新繪制在對話框內(nèi)。 交互圖是用來描述對象之間以及對象參與者之間的動態(tài)協(xié)作關系和協(xié)作過程中行為次序的圖形文檔。 表 游戲的開發(fā)平臺 軟硬件 最低要求 CPU 內(nèi)存 2G 以上 DDR 內(nèi)存 硬盤 160G， 5400 轉以上硬盤 顯示設備 1024*768 分辨率以上 操作系統(tǒng) Windows 7 簡體中文旗艦版 32 位 開發(fā)平臺 Visual Studio 20xx（含 Visual C++ 20xx） 其他工具 Office20xx（含 Word、 Visio 等組件） 表 游戲的運行平臺 軟硬件 最低要求 CPU 1GHz 內(nèi)存 512 以上 DDR 內(nèi)存，如使用 Windows Vista/20xx/7 系統(tǒng)則需要 1G 內(nèi)存 硬盤 80G， 5400 轉以上硬盤 顯示設備 1024*768 分辨率以上 操作系統(tǒng) Windows XP/20xx/Vista/20xx/7 狀態(tài)圖建模 狀態(tài)圖的概念 一個類的對象的各種狀態(tài)以及這些狀態(tài)的遷移組成一個狀態(tài)圖。結合之前的用例描述，分析游戲系統(tǒng)的業(yè)務流程，得 出了連連看局域網(wǎng)對戰(zhàn)游戲系統(tǒng)的活動圖。 用圓角矩形框表示在工作流程中執(zhí)行某個活動或步驟，即活動。 2．在棋盤內(nèi)除了最上方和最下方兩行，最左邊和最右邊一列，其余每一個位置隨機擺一張花色的游戲牌，每一種花色的游戲牌出現(xiàn)的次數(shù)必須是偶數(shù)，并且滿足存在一對能夠消去的游戲牌（花色相同、存在一條拐彎次數(shù)不超過 2 的路徑），啟動計時器的秒數(shù)，游戲開始。而系統(tǒng)需要提供單人游戲模式、局域網(wǎng)雙人對戰(zhàn)模式，這顯然是處于系統(tǒng)內(nèi)。通過執(zhí)行者與系統(tǒng)中的用例進行交互，具體描述系統(tǒng)是如何提供這些功能來完成相應的服務的 [4]。 ? 面向對象分析與設計 用例圖建模 用例建模與用例圖的概念 用例建模是用于描述一個系統(tǒng)的功能（即系統(tǒng)應該做什么）的建模技術，用例建模不僅用于獲取新系統(tǒng)的客戶需求，還可以作為對已有系統(tǒng)進行升級時的指南。 如果是按照以下 4 個概念設計和實現(xiàn)的系統(tǒng)，稱為是面向對象的，即：面向對象 =對象 +類 +繼承 +通信 [3,4]。如當 n=3 時，其解空間為 {(0,0,0), (0,0,1), (0,1,0), (0,1,1), (1,0,0), (1,0,1), (1,1,0), (1,1,1)}，這個解空間可以用一顆完全二叉樹來表示，如圖 所示。而所謂狀態(tài)空間也叫做解空間，是指該系統(tǒng)的全部可能狀態(tài)的集合 [2]。 連連看游戲并沒有絢爛的畫面和龐大的場景，操作簡單，對硬件和環(huán)境要求不高，但是卻變化無窮，容易上手，男女皆宜，節(jié)奏很快，令人上癮。如 Windows 操作系統(tǒng)自帶的紙牌、掃雷等小游戲程序，這一類游戲操作簡單，難度比較低，對硬件的環(huán)境要求不高。 套接字 Abstract Branch and bound method is an algorithm that used widely in statespace search. This algorithm based on breadthfirst or with the way (maximum benefit) in favor of smallest cost to search the problem in State space . During the search ,pruning is used to improve the search efficiency . The branch and bound method , the backtrack method ,and the A* algorithm is monly used in the games of path finding process. Objectoriented (Objectoriented, OO) development methods are industry respected software development methods. Objectoriented development methods can better adapt to change in demand, easy to implement software reusability, maintainability, Modifiability, and scalability. Lianliankan games is a simple yet fun popular games, with a certain mathematical and dynamical .while the expansion of the mon traditional games for multiplayer fighting game on the LAN, make the traditional game have a confrontational and provocative. This articles’ research use the objectoriented technology as the main development methods and take the branch and bound method as two game pathfinding algorithms. The traditional lianliankan games expanded into a double play against the game on the LAN ,focused on the application of branch and bound method and the objectoriented development methods in the LAN battle game. The developed program not only implement the functionality and performance properly, but also has good stability, maintainability and scalability. It proves that the bound method and objectoriented technology is feasible in the multiplayer fighting game on the LAN. Keywords: state space。 面向對象（ Objectoriented， OO）開發(fā)方法是目前業(yè)界推崇的軟件開發(fā)方法，使用面向對象開發(fā)方法能更好地適應當前的需求變化，容易實現(xiàn)軟件復用性、可維護性、可修改性和可擴充性。 分支限界法 。伴著游戲產(chǎn)業(yè)日益壯大，現(xiàn)代人類日常生活中經(jīng)常用游戲來休閑娛樂，游戲市場有很大的潛力，很多國家都對游戲市場十分重視。飽受工作壓力的人們沒有太多的時間進行復雜的游戲，而對于這種動動鼠標就能過關的游戲情有獨鐘。由于連連看游戲具有的數(shù)學性、動態(tài)性與知名度，也經(jīng)常拿來作為程序設計的練習題材。 狀態(tài)空間搜索廣泛應用于優(yōu)化問題中，如經(jīng)典的 “ 01 背包問題 ” 、 “ 旅行商問題 ” 、 “ 迷宮問題 ” 、 “ 最大團問題 ” 、 “ n 皇后問題 ” 等，在計算機求解的過程中，都需要進行狀態(tài)空間 搜索。同時，傳統(tǒng)的軟件工程方法難于支持軟件復用。 第 3 章，標題為 “ 算法設計 ” ，重點闡述分支限界法對兩張游戲牌進行 “ 尋路 ” 的算法，來判斷兩張游戲牌能否消去，同時給出了自動找出一對能消去的游戲牌、游戲牌重新排列、隨機發(fā)牌、處理選中游戲牌、服務端套接字處理數(shù)據(jù)包、客戶端套接字處理數(shù)據(jù)包等主要過程的算法設計。用例圖的主要成分有用例、執(zhí)行者和系統(tǒng)，它用簡單的圖符準確地描述了執(zhí)行者與系統(tǒng)的交互情況以及系統(tǒng)的功能。執(zhí)行者（ actor）[4,5]是指在系統(tǒng)外部與系統(tǒng)交互的人或其他系統(tǒng)，他以某種方式參與系統(tǒng)內(nèi)用例的執(zhí)行。下面將給出“ 進行單人游戲 ” 用例、 “ 進行局域網(wǎng)雙人對戰(zhàn)游戲 ” 用例、 “ 設置局域網(wǎng)連接 ” 用例的用例，與其有關聯(lián)的擴展用例和包含用例、子用例將會在這三個用例中一并描述。 “ 設置局域網(wǎng)連接 ” 用例的用例描述如表 所示。 游戲的活動圖 連連看局域網(wǎng)對戰(zhàn)游戲系統(tǒng)根據(jù)其業(yè)務邏輯來看，提供了單人游戲模式和局域網(wǎng)雙人對戰(zhàn)模式。 此次開發(fā)的連連看局域網(wǎng)對戰(zhàn)游戲程序，既沒有涉及到數(shù)據(jù)庫，也沒有涉及到中間件等環(huán)境。 因此，得到棋盤對象的狀態(tài)圖如圖 所示： 圖 棋盤對象的狀態(tài)圖 對象交互建模 交互建模與順序圖的概念 一次交互就是指在特定語境中，為了實現(xiàn)某一個目標，而在一組對象之間進行交換的一組消息所表示的行為。 程序結構介紹 在 Web 開發(fā)中，有一種常用的開發(fā)模式，被稱為 MVC 模式（ ModelView Controller），這種模式開發(fā)的 Web 系統(tǒng)大致由模型（ Model）、視圖（ View）和控制器（ Controller）三個基本部分組成。 圖 系統(tǒng)模塊結構圖 “選中游戲牌”過程的順序圖 連連看局域網(wǎng)對戰(zhàn)游戲系統(tǒng)根據(jù)其業(yè)務邏輯來看，提供了單人游戲模式和局域網(wǎng)雙人對戰(zhàn)模式。 圖 雙人對戰(zhàn)模式每隔 1 秒的扣時操作的順序圖 雙人對戰(zhàn)模式下，客戶端套接字處理接收到的數(shù)據(jù)包的順序圖，如圖 所示。短式圖形符號由一個矩形實績方框及在方框內(nèi)書寫的類名表示。其詳細定義的相關類圖如圖 所示。 圖 CListenSocket類的設計 服務套接字類的設計 服務套接字 CServerSocket 類繼承自 MFC 的 CSocket 類， CServerSocket 主要針對 OnReceive()（接收到客戶端套接字發(fā)送過來的數(shù)據(jù)時的處理函數(shù)）、 .m_nWnd（游戲窗體句柄）、 OnClose()（關閉套接字時的處理函數(shù)）、SetHWnd()（設置游戲窗體句柄）等進行相應定義。但當探索到某一步時，發(fā)現(xiàn)原先選擇并不優(yōu)或達不到目標，就退回一步重新選擇，這種走不通就退回再走的技術為回溯法，而滿足回溯條件的某個狀態(tài)的點稱為 “ 回溯點 ” 。 回溯法的算法設計使用偽代碼表示如下。 分支限界法常以廣度優(yōu)先或以最小耗費（最大效益）優(yōu)先的方式搜索解空間樹 [2]。 1．隊列式（ FIFO）分支限界法：隊列式分支限界法將活結點表組織成一個隊列，并按隊列的先進先出原則選取下一個結點為當前擴展結點。 for each(CurrNode 生成的孩子節(jié)點 NextNode) { if(NextNode 包含解 )