湖南農業(yè)大學畢業(yè)論文設計

1、湖南農業(yè)大學畢業(yè)論文（設計）,,課 題 “移動十五”的實現(xiàn) 院 （系） 計算機與信息工程學院 年級專業(yè) 2000級 計算機科學與技術學生姓名 黎 陟 指導老師 彭 佳 紅,摘要,拼圖游戲是一類曾一度廣受歡迎的益智類游戲。數(shù)字拼圖就是其中的一種。拼圖游戲的基本規(guī)則就是將原來雜亂無章的圖片碎快或數(shù)字通過移動交換位置而拼成具有一定形狀的圖形或有序的

2、數(shù)字序列。 本次設計的目的就是通過“移動十五的實現(xiàn)”來模擬這一拼圖過程，找出其最優(yōu)解，并試圖由這些最優(yōu)解找出其中潛在的某些規(guī)律性。,,“移動十五”就是在一個4*4方陣中填入0-15這16個數(shù)（其中0代表空格），只有在0上下左右四個方位的數(shù)字才可與0交換（移入空格）。在如此規(guī)則之下移動方陣中的數(shù)字，以達到一定的目標狀態(tài) 本設計采用回溯法來實現(xiàn)找最優(yōu)解,移動十五概述系統(tǒng)設計與實現(xiàn)程序演示總結,移動十五概述,“移動

3、十五”就是在一個4*4方陣中填入0-15這16個數(shù)（其中0代表空格），只有在0上下左右四個方位的數(shù)字才可與0交換（移入空格）。在如此規(guī)則之下移動方陣中的數(shù)字，以達到一定的目標狀態(tài)。下面圖1—1和圖1—2分別表示一個初始狀態(tài)和一個目標狀態(tài)。,圖1-1初態(tài),圖1-2目標態(tài),設計要求從給定的狀態(tài)找到達到給定的目標狀態(tài)的最優(yōu)解，并演示此最優(yōu)解。,系統(tǒng)設計與實現(xiàn),1.設計思路 本程序從界面設計入手，結合界面來調用相關模塊以實現(xiàn)各相

4、應功能。 然后重點進行算法的實現(xiàn)。 首先構思出算法的主要思想，根據(jù)此思想給出算法的基本步驟。然后設計合適的數(shù)據(jù)結構，寫出算法的自然語言形式的代碼。最后結合程序將算法用動態(tài)效果體現(xiàn)出來。,,最后進行系統(tǒng)的完善，包括界面的完善，以及算法正確性的驗證。,界面的實現(xiàn),程序首先設置一主窗口，通過下拉菜單來進行各項功能選擇：ＰＬＡＹ：用戶進入數(shù)字拼圖游戲，將一隨機產生的初始狀態(tài)通過移動變?yōu)閺男〉酱笈帕械臄?shù)字序

5、列的終狀態(tài)。ＳＨＯＷ：給出一初始狀態(tài)，演示其達到目的狀態(tài)最優(yōu)路徑的過程。ＣＨＯＯＳＥ：進行難度選擇（即選擇９格或１６格）。ＥＸＩＴ：退出程序。,,然后進行每個模塊的界面設計，主要是數(shù)字方格的動態(tài)演示過程的實現(xiàn)。 其中數(shù)字方格及移動操作都設計為單個模塊，以便更方便地與算法所用的數(shù)據(jù)結構結合。 最后是添加各種效果，如提示文字、按鈕效果等。,算法的設計與實現(xiàn),本設計核心算法采用回溯法，以回溯來窮搜舉所有可能

6、由初始態(tài)達到目標狀態(tài)的路徑（規(guī)定了最大路徑長度，即最大解深度）。,算法步驟,首先根據(jù)設定的規(guī)則進行移動，利用一個棧Stack將每一次移動后的狀態(tài)以棧頂結點形式保存。每次移動前都判斷移動后的狀態(tài)是否與棧中各結點狀態(tài)相同，若相同，則改變方向（即更改規(guī)則）進行移動。若此狀態(tài)下移動規(guī)則用完，則從棧中彈出頂點結點，即回溯一步。,如此繼續(xù)，直至找到一個解（即到達目標狀態(tài)的一條路徑），并保存。此時需回溯兩步，改變移動方向以繼續(xù)找更優(yōu)解，因為回溯一步實

7、際上沒有意義。若不行，則再回溯一步，且更改移動方向，繼續(xù)找。若找到一個更優(yōu)解，則將此更優(yōu)解替換先前的最優(yōu)解。直到棧中沒有結點，則此時的最優(yōu)解即為所要求的最優(yōu)解。,算法具體步驟如下：1. 讀取初始狀態(tài)start和目標狀態(tài)goal，判斷輸入的狀態(tài)是否合法，不合法退出。（合法性主要是指是否有重復的或是否越界）；2．初始狀態(tài)start是否與目標狀態(tài)goal完全相同以及初始狀態(tài)start是可達到目標狀態(tài)goal，完全相同或不能達到 就退出；

8、3．置初始解數(shù)為0,解深度為0；,4.初始狀態(tài)start作為當前結點infor的狀態(tài)infor->state，同時作為棧頂界點的狀態(tài)。置深度infor->deep=0;移動規(guī)則infor->rule=0; 5.將棧頂結點賦給infor. 6.判斷infor->rule是否大于等于4。若是，表示當前狀態(tài)已向各個方向進行過搜索，因此應回溯一步，即棧頂結點指針first減1，彈出一結點，同時棧頂結點的

9、rule值加1。此時繼續(xù)判斷first是否為-1，若是，表明?？?，跳至 15。否則返回5。 7.繼續(xù)判斷當前結點深度是否大于預測深度或當前最優(yōu)解深度，若大于則回溯一步，同時棧頂結點規(guī)則加一，返回5。,（ 8.根據(jù)當前狀態(tài)的空格‘0’位置，根據(jù)移動規(guī)則獲得預移入空格的方格位置（x,y)。移動規(guī)則0，1，2，3分別對應‘0’的下，右，左，上四個相鄰位置，移入規(guī)則是可根據(jù)需要自定義的。9. 判斷當前預移入方格的位置是否越界。若越

10、界，則當前狀態(tài)結點的移動規(guī)則infor->rule+1,返回5；否則繼續(xù)。10. 預先判斷移動后的狀態(tài)是否與棧中某一結點狀態(tài)相同。若是，則當前結點移動規(guī)則加1，返回5。否則繼續(xù)。,11.交換方格（移入空格），當前結點狀態(tài)infor為移后的狀態(tài)，且infor->rule重置為0,infor->deep+1。12.infor入棧，若infor的狀態(tài)與目標態(tài)不同返回5，否則轉13。13.如果預測深度exp大于當前結點i

11、nfo的深度info->deep,去掉以前深度較大的結果,深度result[Rp].deep等于當前結點的深度info->deep14．保存結果，置有解標志，flag=1;轉5； 15. 顯示保存的結果，即最優(yōu)解。16. 結束。,總結,用C語言設計界面的難處。要想成為一個優(yōu)秀而純粹的程序員，數(shù)據(jù)結構的深入學習是必須的課程，對各種算法更應要有自己獨到而深刻的理解。在精通一門設計語言的情況下，如能對各種設計語言都有一定程

12、度的掌握，那么這樣的程序員才有更強的生命力，才能在社會立足和發(fā)展。,設計過程中的優(yōu)缺點 1.優(yōu)點：界面的設計；整個設計過程工 程化思想的運用；算法與界面的結合。 2. 缺點：對于無解這種情況采取了回避； 程序代碼仍顯凌亂，且冗余度仍較大； 對程序設計的整體規(guī)劃仍有所欠缺；在文擋及演示稿的編寫過程中，對所用到的辦公軟件不熟悉。,多謝各位答辯老師 指導