八數(shù)碼問(wèn)題課程設(shè)計(jì)報(bào)告_1504092011_曹志

1、合肥學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)系課程設(shè)計(jì)報(bào)告20162017 學(xué)年第 2學(xué)期課程 數(shù)據(jù)結(jié)構(gòu)與算法課程設(shè)計(jì)名稱(chēng) 八數(shù)碼問(wèn)題求解學(xué)生姓名萱直學(xué)號(hào) 1504092011專(zhuān)業(yè)班級(jí) 軟件工程2班指導(dǎo)教師在矍2017題目八數(shù)碼問(wèn)題求解【問(wèn)題描述】八數(shù)碼問(wèn)題：在 3X3的方格棋盤(pán)上，擺放著 1到8這八個(gè)數(shù)碼，有1個(gè)方格是空 的，其初始狀態(tài)如圖 1所示，要求對(duì)空格執(zhí)行空格左移、空格右移、空格上移和空 格下移這四個(gè)操作使得棋盤(pán)從初始狀態(tài)到目標(biāo)狀態(tài)。(a)初始狀態(tài)目標(biāo)狀態(tài))圖一請(qǐng)使用一種盲目搜索算法(深度或廣度優(yōu)先搜索)和一種啟發(fā)式搜索方法編程求解八數(shù)碼問(wèn)題，并對(duì)兩種算法的搜索步驟，搜索時(shí)間進(jìn)行分析對(duì)比。 1、問(wèn)題分析

2、和任務(wù)定義1.1問(wèn)題分析由題目知給出一個(gè)初始狀態(tài)和一個(gè)目標(biāo)狀態(tài)，找出一種從初始轉(zhuǎn)變成目標(biāo)狀態(tài)的移動(dòng)步驟。所謂問(wèn)題的一個(gè)狀態(tài)就是棋子在棋盤(pán)上的一種擺法。解八數(shù)碼問(wèn)題實(shí)際上就是找出從初始狀態(tài)到達(dá)目標(biāo)狀態(tài)所經(jīng)過(guò)的一系列中間過(guò)渡狀態(tài)。要求分別采用廣度優(yōu)先搜索和啟發(fā)式搜索兩種方法對(duì)八數(shù)碼問(wèn)題進(jìn)行求解。且棋盤(pán)通過(guò)空格的上、下、右四種操作來(lái)改變狀態(tài)。所以需要解決的問(wèn)題為每個(gè)狀態(tài)的表示和每個(gè)狀態(tài)變化的操作，設(shè)計(jì)出適合相應(yīng)搜索的數(shù)據(jù)結(jié)構(gòu)，完成相應(yīng)算法思想。1.2任務(wù)定義(1)完成棋盤(pán)狀態(tài)表示。(2)完成空格上下左右移動(dòng)操作變化的表示。(3)分別完成適應(yīng)于廣度優(yōu)先搜索，啟發(fā)式搜索的數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)。(4)得出兩種搜索

3、的搜索路徑，及時(shí)間進(jìn)行對(duì)比分析。2、數(shù)據(jù)結(jié)構(gòu)的選擇和概要設(shè)計(jì)2.1廣度優(yōu)先搜索(1)廣度優(yōu)先搜索思想介紹從初始節(jié)點(diǎn)h開(kāi)始逐層的對(duì)其進(jìn)行擴(kuò)展， 并考察其其是否為目的節(jié)點(diǎn)， 若不是將其 放入待考察隊(duì)列中，在第n層節(jié)點(diǎn)沒(méi)有完全進(jìn)行考察并擴(kuò)展完成前，不對(duì)第n+1層進(jìn)行擴(kuò)展。隊(duì)列中節(jié)點(diǎn)總是按照先后順序進(jìn)行排列，先進(jìn)的排在前面，后進(jìn)的排在后面。由此可知我們可以通過(guò)隊(duì)列的思想完成搜索，其具體搜索過(guò)程如下。1)初始化頭結(jié)點(diǎn) front, front=real;2)若front=null,問(wèn)題無(wú)解，程序結(jié)束。3)對(duì)front指向的節(jié)點(diǎn)進(jìn)行考察，若為目的節(jié)點(diǎn)程序結(jié)束。4)判斷front指向的節(jié)點(diǎn)的空格是否可以上下

4、左右移動(dòng)若可以，擴(kuò)展節(jié)點(diǎn)置于隊(duì)尾。重復(fù)操作(2)。(2)數(shù)據(jù)結(jié)構(gòu)的選擇和概要設(shè)計(jì)1)棋盤(pán)狀態(tài)的表示因?yàn)槊恳粋€(gè)棋盤(pán)狀態(tài)是靜止且確定的所以采取一個(gè)一維數(shù)組便可將其狀態(tài)表示出 來(lái)，數(shù)組按照下標(biāo)順序從左至右從上至下依次對(duì)應(yīng)?？崭窨捎闪銇?lái)表示。此狀態(tài)可表示為 int num9=2,5,4,3Q7,1,8,6。2)搜索結(jié)構(gòu)設(shè)計(jì)根據(jù)算法要求，需要對(duì)棋盤(pán)不斷的進(jìn)行動(dòng)態(tài)擴(kuò)展，且盲目搜索產(chǎn)生的數(shù)據(jù)巨大，所以不能采用靜態(tài)鏈表或數(shù)組存儲(chǔ)，因此選擇采用動(dòng)態(tài)鏈表來(lái)存儲(chǔ)搜索過(guò)程中的每一個(gè)狀態(tài)。因?yàn)樗阉魇歉鶕?jù)一種狀態(tài)對(duì)其進(jìn)行擴(kuò)展，直至達(dá)到目的狀態(tài)，由于要返回一個(gè)最優(yōu)路徑因此需要確定擴(kuò)展關(guān)系，我選擇用一個(gè)*parent來(lái)記錄此

5、關(guān)系。此時(shí)存儲(chǔ)結(jié)構(gòu)可由此圖表示圖三當(dāng)擴(kuò)展至目的狀態(tài)時(shí)可通過(guò)parent指針找到路徑。由此我們可以設(shè)置節(jié)點(diǎn)類(lèi)型為typedef struct Nodestruct Node *parent;int num9;Node *next;QNode;2.2啟發(fā)式搜索(1)啟發(fā)式搜索的思想介紹搜索算法可分為兩大類(lèi)：無(wú)信息的搜索算法和有信息的搜索算法。無(wú)信息的搜索又稱(chēng)盲目搜索，盲目搜索不考慮節(jié)點(diǎn)好壞，而對(duì)于八數(shù)碼問(wèn)題的解決過(guò)程是有跡可循的， 我們通過(guò)是否接近目標(biāo)狀態(tài)來(lái)判斷節(jié)點(diǎn)的好壞，因此可以通過(guò)啟發(fā)式搜索中的A*算法來(lái)解決這個(gè)問(wèn)題。簡(jiǎn)單來(lái)說(shuō) A*就是將估值函數(shù)分成兩個(gè)部分，一個(gè)部分是路徑價(jià)值，另一個(gè)部分是

6、一般性啟發(fā)價(jià)值，合在一起算估整個(gè)結(jié)點(diǎn)的價(jià)值。在本實(shí)驗(yàn)中使用A*算法求解。A*搜索是一種效的搜索算法，它把到達(dá)節(jié)點(diǎn)的耗散g(n)和從該節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)的消耗h(n)結(jié)合起來(lái)對(duì)節(jié)點(diǎn)進(jìn)行評(píng)價(jià)：f(n)=g(n)+h(n)。由此設(shè)計(jì)如下(1)把起始節(jié)點(diǎn)放到 OPEN中，并十算節(jié)點(diǎn)SW f(S)(2)如果OPEN1空表，則失敗退出，無(wú)解；(3)從OPENa中選擇一個(gè)f值最小白節(jié)點(diǎn)i。如果有幾個(gè)節(jié)點(diǎn)值相同，當(dāng)其中有一 個(gè)為目標(biāo)節(jié)點(diǎn)時(shí)，則選擇此目標(biāo)節(jié)點(diǎn)；否則就選擇其中任一個(gè)節(jié)點(diǎn)作為節(jié)點(diǎn)i ；(4)把節(jié)點(diǎn)i從OPEN表中移出，并把它放入 CLOSED的已擴(kuò)展節(jié)點(diǎn)表中；如果i是 個(gè)目標(biāo)節(jié)點(diǎn)，則成功退出，求得一個(gè)解

7、；(5)擴(kuò)展節(jié)點(diǎn)i ,生成其全部后繼節(jié)點(diǎn)。對(duì)于 i的每一個(gè)后繼節(jié)點(diǎn)j :計(jì)算f (j)； 如果j既不在OPENa中，又不在 CLOCE醫(yī)中，則用彳t價(jià)函數(shù) f把它添入OPENg中。 從j加一指向其父節(jié)點(diǎn)i的指針，以便一旦找到目標(biāo)節(jié)點(diǎn)時(shí)記住一個(gè)解答路徑；如果j已在OPENH或CLOSED1中，則比較剛剛對(duì) j計(jì)算過(guò)的f和前面計(jì)算過(guò)的該節(jié)點(diǎn)在表中 的f值。如果新的f較小，則(I)以此新值取代舊值。(II)從j指向i ,而不是指向他 的父節(jié)點(diǎn)。(III)如果節(jié)點(diǎn)j在CLOSED!中，則把它移回 OPENI1中。車(chē)t向(2)。流程圖如下圖四(2)數(shù)據(jù)結(jié)構(gòu)的選擇和概要設(shè)計(jì)由于搜索特點(diǎn)，采用的基礎(chǔ)存儲(chǔ)結(jié)構(gòu)

8、和廣度優(yōu)先搜索相同，不同之處為啟發(fā)式搜索使用兩條鏈表，所以設(shè)計(jì)一個(gè)表結(jié)構(gòu)，用來(lái)聲明兩條鏈表。節(jié)點(diǎn)結(jié)構(gòu)typedef struct Nodedouble g,f;struct Node *parent;int num9;Node； 表結(jié)構(gòu)typedef struct StackNode * npoint;/ 指向狀態(tài)節(jié)點(diǎn)，相當(dāng)于表節(jié)點(diǎn)的數(shù)據(jù)域。struct Stack * next;Stack ；3、詳細(xì)設(shè)計(jì)和編碼3.1 廣度優(yōu)先搜索( 1 )相關(guān)函數(shù)1)空格移動(dòng)函數(shù)int move_up(int num);int move_down(int num);int move_left(int num

9、);int move_right(int num);以上移為例， 找到 0 的位置將其與下標(biāo)比其小三的值交換， 且下標(biāo)為 0,1,2 的數(shù)字 不可移動(dòng)。2)搜索過(guò)程函數(shù)int bfs(int init,int target) ；接收初始狀態(tài)和目的狀態(tài)總領(lǐng)搜索過(guò)程。int cansolve(int num1, int num2) ；判斷兩個(gè)數(shù)列的逆序數(shù)奇偶性，從而判斷八數(shù)碼問(wèn)題是否可解void get_num(QNode *node, int temp)；將節(jié)點(diǎn)中的數(shù)組獲取出來(lái)。void set_num(QNode *node, int temp)；設(shè)置節(jié)點(diǎn)中數(shù)組的數(shù)據(jù)。void print(Q

10、Node *node) ；輸出節(jié)點(diǎn)中信息( 2) 算法偽碼輸入初始狀態(tài)數(shù)組 unit ，目標(biāo)狀態(tài)數(shù)組targetIf( 問(wèn)題可解 )While( 隊(duì)頭指針?lè)强諘r(shí)&&未找到目的節(jié)點(diǎn))If( 隊(duì)頭節(jié)點(diǎn)為目的節(jié)點(diǎn) )結(jié)束循環(huán)；End if對(duì)隊(duì)頭節(jié)點(diǎn)進(jìn)行擴(kuò)展，將擴(kuò)展節(jié)點(diǎn)加入隊(duì)尾；隊(duì)頭指針后移；End whileEnd if3.2 啟發(fā)式搜索設(shè)計(jì)( 1 )所用函數(shù)int Equal(Node * suc,Node * goal) ；判斷節(jié)點(diǎn)是否相等，相等，不相等。Node * Belong(Node * suc,Lstack * list)判斷節(jié)點(diǎn)是否屬于 OPE猷或 CLOSED, 是

11、則返回節(jié)點(diǎn)地址，否則返回空地址。void Putinto(Node * suc,Lstack * list)把節(jié)點(diǎn)放入 OPEN 或 CLOSED中。double Fvalue(Node suc, Node goal, float speed)計(jì)算 f 值。double Distance(Node suc, Node goal, int i)計(jì)算方格的錯(cuò)位距離。int BelongProgram(Lnode * suc ,Lstack * Open ,Lstack * Closed ,Node goal ,float speed)判斷子節(jié)點(diǎn)是否屬于OPEN CLOSED1并作出相應(yīng)的處理。in

12、t Canspread(Node suc, int n) 判斷空格可否向該方向移動(dòng)，表示空格向上向下向左 向右移。void Spreadchild(Node * child,int n) 擴(kuò)展 child 節(jié)點(diǎn)的字節(jié)點(diǎn) n 表示方向表示空格 向上向下向左向右移。int Spread(Lnode * suc, Lstack * Open, Lstack * Closed, Node goal, float speed) 擴(kuò)展后繼節(jié)點(diǎn)總函數(shù)。Node * Process(Lnode * org, Lnode * goal, Lstack * Open, Lstack * Closed, float

13、 speed) 總執(zhí)行函數(shù)。void qf(int init9,int target9) 啟發(fā)式搜索總函數(shù)。( 2 )搜索過(guò)程偽碼輸入：初始狀態(tài)，目標(biāo)狀態(tài)輸出：從初始狀態(tài)到目標(biāo)狀態(tài)的一系列過(guò)程算法描述：Begin ：讀入初始狀態(tài)和目標(biāo)狀態(tài)，并計(jì)算初始狀態(tài)評(píng)價(jià)函數(shù)值f ；根據(jù)初始狀態(tài)和目標(biāo)狀態(tài)，判斷問(wèn)題是否可解；If( 問(wèn)題可解 )把初始狀態(tài)加如 open 表中；While (未找到解&&狀態(tài)表非空)在 open 表中找到評(píng)價(jià)值最小的節(jié)點(diǎn)，作為當(dāng)前結(jié)點(diǎn)， ；判斷當(dāng)前結(jié)點(diǎn)狀態(tài)和目標(biāo)狀態(tài)是否一致， 若一致， 跳出循環(huán)； 否則 跳轉(zhuǎn)到；對(duì)當(dāng)前結(jié)點(diǎn)，分別按照上、下、左、右方向移動(dòng)空格位置

14、來(lái)擴(kuò)展新的狀態(tài)結(jié)點(diǎn)，并在并計(jì)算新擴(kuò)展結(jié)點(diǎn)的評(píng)價(jià)值f 并記錄其父節(jié)點(diǎn)若；對(duì)于新擴(kuò)展的狀態(tài)結(jié)點(diǎn)， 判斷其是否重復(fù)， 若不重復(fù)， 把其加入到open 表中；把當(dāng)前結(jié)點(diǎn)從open 表中移至 Close 表；End whileEnd if輸出結(jié)果；End4、上機(jī)調(diào)試過(guò)程4.1 遇到的問(wèn)題和分析( 1)本次課程設(shè)計(jì)過(guò)程是兩種搜索方式分開(kāi)開(kāi)發(fā)，因此在綜合在一起的時(shí)候兩種方式的代碼合在一起略顯雜糅，程序可讀性較差。( 2)在做啟發(fā)式搜索時(shí)，發(fā)現(xiàn)效率并未達(dá)到預(yù)期，查閱資料得知h 值取得不好，沒(méi)有完全切合搜索規(guī)律， h 值應(yīng)為每個(gè)方格到其正確位置的路徑之和，而我僅統(tǒng)計(jì)的是錯(cuò)位之和同時(shí)發(fā)現(xiàn)若 h 值取得越大其搜索速

15、度越快單難以保證得出的是最優(yōu)解。 因此我設(shè)計(jì)了一個(gè)系數(shù)1000 來(lái)進(jìn)行加速。(3)在設(shè)計(jì)廣度優(yōu)先搜索時(shí)指針操作出現(xiàn)失誤，導(dǎo)致進(jìn)度一度停滯，后放棄改為數(shù)組操作才完成程序4.2 時(shí)空效率分析(1)廣度優(yōu)先搜索是一種十分浪費(fèi)空間的搜索方法，有時(shí)會(huì)陷入死循環(huán)。同時(shí)在時(shí)間效率上廣度優(yōu)先搜索效率不穩(wěn)定，若搜索深度過(guò)大則時(shí)間效率異常緩慢。但可確定找到最優(yōu)解。(2)啟發(fā)式搜索效率較穩(wěn)定，當(dāng)搜素深度較小時(shí)時(shí)間效率不及廣度優(yōu)先但在深度 搜索表現(xiàn)優(yōu)異，同時(shí)啟發(fā)式搜索有選擇的創(chuàng)建節(jié)點(diǎn)，大大節(jié)省空間效率。4.3 試結(jié)果及其分析J 'L:usersAamrnistraToruesKtopuebu(|輸入初始狀態(tài):

16、2 8 3 1 6 4 7 0 5 輸入目標(biāo)狀態(tài)；1 23804765使用廣度優(yōu)先進(jìn)行搜索:1 2 3hj1 2 30 8 47 6 50 2 38 4史2 0 318 46 52 8 31 0 47 6 52 8 31 6 47 0 5推和拼音輸入法圣圖五共花費(fèi)時(shí)間4. 0000ros5得出最優(yōu)解共需6個(gè)節(jié)點(diǎn), 使用啟發(fā)式進(jìn)行搜索：1 2 38 0 47 6 51 2 30 8 47 6 50 2 31 8 47 6 52 0 31 8 47 6 52 8 31 0 47 6 52 8 31 6 47 0 5搜索所用時(shí)間；1000000ms,得出路徑所需節(jié)點(diǎn)6搜狗拼音輸入法全：圖六 '

17、; F:Dev-cpp5.4.0ZIAPppConsolePaue輸入初始狀態(tài)： 2 5 4 3 0 7 1 8 6|輸入目標(biāo)狀態(tài)：11 2 3 8 0 4 7 6 5|無(wú)解flDrocess exited with return value 0 ress any key to continue .圖七7 1 C:LJ sersAd min istratorDe skto pDeb ug課程|fe入初始狀態(tài): 123456780 輸入目標(biāo)狀態(tài)： 123405678使用廣度優(yōu)先進(jìn)行搜索:1 2 34 0 56 7 81 2 34 5 06 7 81 2 34 5 86 7 01 2 34 5 8

18、6 0 71 2 34 5 80 6 71 2 3圖八1 2 30 5 64 1 81 2 34 5 65 7 81 2 34 5 67 0 E1 2 34 5 61 8 0共花費(fèi)時(shí)間43394。眸,得出最優(yōu)解共需13個(gè)節(jié)點(diǎn), 使用后發(fā)式進(jìn)行搜索：1 2 34 0 5& 7 S圖九I 2 31 5 6)1 8I 2 3I 5 6f 0 8I 2 31 5 6I 3 0圖索所用時(shí)間：196. 000000ms,得出路徑所需節(jié)點(diǎn)153ress Enter key to exitPress any key to continue圖十：:U se 0Aid ministry t orDeskt

19、o HOsbuq 湃理設(shè)計(jì)改進(jìn)版輸入初始狀態(tài)： 123456780輸入目標(biāo)狀態(tài)： 013825476使用廣度優(yōu)先進(jìn)行搜索: 0 1 38 2 54 7 61 0 38 2 54 7 61 2 38 0 59 7 61 2 30 8 54 7 61 2 34 8 50 7 61 2 34 8 57 0 6搜索所用時(shí)間：128.000000叫得出路徑所需節(jié)點(diǎn)9Press Enter key to exit'!Press any key to continue圖十(1)實(shí)驗(yàn)結(jié)果實(shí)驗(yàn)數(shù)據(jù)廣廣度優(yōu)先啟發(fā)式搜索時(shí)間最優(yōu)節(jié)點(diǎn)數(shù)時(shí)間最優(yōu)節(jié)點(diǎn)數(shù)初始狀態(tài)283164705 目標(biāo)狀態(tài)1238047654ms

20、6109ms6初始狀態(tài)254307186 目標(biāo)狀態(tài)123804765無(wú)解0無(wú)解無(wú)解無(wú)解初始狀態(tài)123456780目標(biāo)狀態(tài)1234056784399ms15196ms15初始狀態(tài)123456780目標(biāo)狀態(tài)01382547648ms9128ms9初始狀態(tài)123456780目標(biāo)狀態(tài)12304567812537ms16300ms28初始狀態(tài)183265470目標(biāo)狀態(tài)836107245112ms11347ms25表(2)結(jié)果分析。當(dāng)最優(yōu)解步驟較小時(shí)，廣度優(yōu)先時(shí)間效能更好。造成這種現(xiàn)象的原因?yàn)楫?dāng)搜素深度小 時(shí)，啟發(fā)式搜索由于有較多的查重和鏈表操作導(dǎo)致時(shí)間性能下降，而當(dāng)搜索深度較深時(shí)啟發(fā)式搜索對(duì)節(jié)點(diǎn)優(yōu)劣的考

21、察使其在時(shí)間上展現(xiàn)出較大優(yōu)勢(shì)。但啟發(fā)式搜索可能無(wú)法獲取最優(yōu) 解。6、用戶使用說(shuō)明在輸入八數(shù)碼狀態(tài)時(shí)將八數(shù)碼上數(shù)字從上至下從左至右，依次輸入其中空格用0代替,且每個(gè)數(shù)字用空格隔開(kāi)。7、參考文獻(xiàn)1 錢(qián)瑩.基于廣度優(yōu)先的八數(shù)碼問(wèn)題解決方案.電腦學(xué)習(xí)，2008:45-462 張鴻.人工智能中求解八數(shù)碼問(wèn)題算法與實(shí)現(xiàn).軟件導(dǎo)刊，2009:62-648、附錄#include "stdio.h"#include <stdlib.h>#include <time.h>#include <math.h>#include<process.h>ty

22、pedef struct Nodestruct Node *parent;double f,g;int num9;/ int step;Node *next;QNode,*Lnode;typedef struct Stack/OPEN CLOSED 表結(jié)構(gòu)體Node * npoint;struct Stack * next;Stack,* Lstack;int cansolve(int num1, int num2);void input(int num);int move_up(int num);int move_down(int num);int move_left(int num);in

23、t move_right(int num);void get_num(QNode *node, int temp);void set_num(QNode *node, int temp);void print(QNode *node);int isequal(QNode *node, int temp);int bfs(int init9, int target9);Node * Minf(Lstack * Open);Node * Belong(Node * suc,Lstack * list);void Putinto(Node * suc,Lstack * list);int Equal

24、(Node * suc,Node * goal);int Canspread(Node suc, int n);void Spreadchild(Node * child,int n);void Putinto(Node * suc,Lstack * list);double Distance(Node suc, Node goal, int i);void Spreadchild(Node * child,int n);int BelongProgram(Lnode * suc ,Lstack * Open ,Lstack * Closed ,Node goal ,float speed);

25、Node * Process(Lnode * org, Lnode * goal, Lstack * Open, Lstack * Closed, float speed);void qf(int init9,int target9);int main() int init9, target9;l: printf("輸入初始狀態(tài):n");input(init);printf("輸入目標(biāo)狀態(tài):n");input(target);if(cansolve(init,target)printf(" 使用廣度優(yōu)先進(jìn)行搜索:n");bfs(ini

26、t,target);printf(" 使用啟發(fā)式進(jìn)行搜索:n");qf(init,target);elseprintf(" 無(wú)解 ");getchar();system("cls");goto l;Node * Minf(Lstack * Open)/選取OPENI上f值最小的節(jié)點(diǎn)，返回該節(jié)點(diǎn)地址Lstack temp = (*Open)->next,min = (*Open)->next,minp = (*Open);Node * minx;while(temp->next != NULL)if(temp->

27、next ->npoint->f) < (min->npoint->f)min = temp->next;minp = temp;temp = temp->next;minx = min->npoint;temp = minp->next;minp->next = minp->next->next;free(temp);return minx;int Equal(Node * suc,Node * goal)/ 判斷節(jié)點(diǎn)是否相等，相等，不相等f(wàn)or(int i = 0; i < 9; i + )if(suc->

28、numi != goal->numi)return 0;return 1;Node * Belong(Node * suc,Lstack * list)/判斷節(jié)點(diǎn)是否屬于OPENI或CLOSED1,是則返回節(jié)點(diǎn)地址，否則返回空地址Lstack temp = (*list) -> next ;if(temp = NULL)return NULL;while(temp != NULL) if(Equal(suc,temp->npoint)return temp -> npoint;temp = temp->next; return NULL;void Putinto(

29、Node * suc,Lstack * list) /把節(jié)點(diǎn)放入OPEN或CLOSEDa中Stack * temp;temp =(Stack *) malloc(sizeof(Stack);temp->npoint = suc;temp->next = (*list)->next;(*list)->next = temp;/ 計(jì)算 f 值部分 - 開(kāi)始 /double Fvalue(Node suc, Node goal, float speed)/ 計(jì)算 f 值double Distance(Node,Node,int);double h = 0;for(int i

30、= 1; i <= 8; i+)h = h + Distance(suc, goal, i);return h*speed + suc.g; /f = h + g;(speed值增加時(shí)搜索過(guò)程以找到目標(biāo)為優(yōu)先因此可能不會(huì)返回最優(yōu)解)double Distance(Node suc, Node goal, int i)/ 計(jì)算方格的錯(cuò)位距離int k,h1,h2;for(k = 0; k < 9; k+)if(suc.numk = i)h1 = k;if(goal.numk = i)h2 = k;return double(fabs(h1/3 - h2/3) + fabs(h1%3

31、- h2%3);/ 計(jì)算 f 值部分 - 結(jié)束 /擴(kuò)展后繼節(jié)點(diǎn)部分的函數(shù)- 開(kāi)始 /int BelongProgram(Lnode * suc ,Lstack * Open ,Lstack * Closed ,Node goal ,float speed)/判斷子節(jié)點(diǎn)是否屬于OPE減CLOSED1并作出相應(yīng)的處理Node * temp = NULL;int flag = 0;if(Belong(*suc,Open) != NULL) | (Belong(*suc,Closed) != NULL) if(Belong(*suc,Open) != NULL) temp = Belong(*suc,

32、Open);else temp = Belong(*suc,Closed);if(*suc)->g) < (temp->g)temp->parent = (*suc)->parent;temp->g = (*suc)->g;temp->f = (*suc)->f;flag = 1;elsePutinto(* suc, Open);(*suc)->f = Fvalue(*suc, goal, speed);return flag;int Canspread(Node suc, int n)/ 判斷空格可否向該方向移動(dòng)， ，表示空格向上向

33、下向左向右移int i,flag = 0;for(i = 0;i < 9;i+)if(suc.numi = 0)break;switch(n)case 1:if(i/3 != 0)flag = 1;break;case 2:if(i/3 != 2)flag = 1;break;case 3:if(i%3 != 0)flag = 1;break;case 4:if(i%3 != 2)flag = 1;break;default:break;return flag ; void Spreadchild(Node * child,int n)/ 擴(kuò)展 child 節(jié)點(diǎn)的字節(jié)點(diǎn) n 表示方向，

34、， ，表示空格向上向下向左向右移int i,loc,temp;for(i = 0;i < 9;i+) child->numi = child->parent->numi;for(i = 0;i < 9;i+)if(child->numi = 0)break;if(n=0)loc = i%3+(i/3 - 1)*3;else if(n=1)loc = i%3+(i/3 + 1)*3;else if(n=2)loc = i%3-1+(i/3)*3; elseloc = i%3+1+(i/3)*3;temp = child->numloc;child->

35、;numi = temp;child->numloc = 0; float speed)判斷某個(gè)擴(kuò)展子節(jié)點(diǎn)算子節(jié)點(diǎn)的int Spread(Lnode * suc, Lstack * Open, Lstack * Closed, Node goal, / 擴(kuò)展后繼節(jié)點(diǎn)總函數(shù)int i;Node * child;for(i = 0; i < 4; i+) if(Canspread(*suc, i+1)/方向上的子節(jié)點(diǎn)可否擴(kuò)展child = (Node *) malloc(sizeof(Node); /child->g= (*suc)->g+1;/child->pare

36、nt= (*suc);/子節(jié)點(diǎn)父指針指向父節(jié)點(diǎn)Spreadchild(child, i);/ 向該方向移動(dòng)空格生成子節(jié)點(diǎn)if(BelongProgram(&child, Open, Closed, goal, speed) /判斷子節(jié)點(diǎn)是否屬于OPEr< CLOSED1并作出相應(yīng)的處理free(child);/step+;return 1;/擴(kuò)展后繼節(jié)點(diǎn)部分的函數(shù)- 結(jié)束/Node * Process(Lnode * org, Lnode * goal, Lstack * Open, Lstack * Closed, float speed) / 總執(zhí)行函數(shù)while(1)判斷

37、OPEN從 OPEN將節(jié)點(diǎn)放如果當(dāng)前if(*Open)->next = NULL)return NULL;/表是否為空，為空則失敗退出Node * minf = Minf(Open);/表中取出 f 值最小的節(jié)點(diǎn)Putinto(minf, Closed);/入 CLOSED中if(Equal(minf, *goal)return minf;/節(jié)點(diǎn)是目標(biāo)節(jié)點(diǎn)，則成功退出Spread(&minf, Open, Closed, *goal, speed);/ 當(dāng)前節(jié)點(diǎn)不是目標(biāo)節(jié)點(diǎn)時(shí)擴(kuò)展當(dāng)前節(jié)點(diǎn)的后繼節(jié)點(diǎn)/*int Shownum(Node * result)/ 遞歸顯示從初始狀態(tài)到達(dá)目

38、標(biāo)狀態(tài)的移動(dòng)方法if(result = NULL)return 0;elseint n = Shownum(result->parent);for(int i = 0; i < 3; i+)printf("n");for(int j = 0; j < 3; j+)if(result->numi*3+j != 0) printf(" %d ",result->numi*3+j);else printf(" "); printf("n");return n+1;*/void qf(int

39、init9,int target9)Lstack Open = (Stack *) malloc(sizeof(Stack);Open->next = NULL;Lstack Closed = (Stack *) malloc(sizeof(Stack);Closed->next = NULL;Node * org = (Node *) malloc(sizeof(Node);Node * p;org->parent = NULL;/初始狀態(tài)節(jié)點(diǎn)org->f =1;org->g =1;int count=0;/ org->step =1;Node * goa

40、l = (Node *) malloc(sizeof(Node); / 目標(biāo)狀態(tài)節(jié) 點(diǎn)Node * result;set_num(org,init);set_num(goal,target);float speed = 1000;/speed 搜索速度 / char c;double now;now=(double)clock();/ printf(" 請(qǐng)輸入搜索速度(速度越高越無(wú)法保證結(jié)果是最優(yōu)解):");/ scanf("%f",&speed);/while(c = getchar() != 10);/printf("搜索中， 請(qǐng)耐

41、心等待( 如果您覺(jué)得時(shí)間太久請(qǐng)重新執(zhí)行程序并輸入更快的速度 , 默認(rèn)值為 )n");Putinto(org,&Open);result = Process(&org, &goal, &Open, &Closed, speed); /進(jìn)行剩余的操作 print(result)for (p=result; p!= NULL; p= p->parent)print(p);printf("-A-n");/ printf(" 搜索 g:%f",p->g);count+;printf(" 搜索所

42、用時(shí)間 :%fms, 得出路徑所需節(jié) 點(diǎn) %d",(double)clock()-now,count);printf("n");printf("Press Enter key to exit!");/ while(c = getchar() != 10);int exist(QNode *node, int temp);int bfs(int init,int target)int temp9;int find = 0;double now=0;int step=1,count=1;QNode *front , *rear, *new_node

43、, *p;/ printf("輸入初始狀態(tài):n");/ input(init);/ printf("輸入目標(biāo)狀態(tài):n");/ input(target);if (!cansolve(init, target)printf(" 不能實(shí)現(xiàn) n");return 0;now=(double)clock();front = (QNode *)malloc(sizeof(QNode);set_num(front, init);front->parent = NULL;front->next = NULL;rear = front;w

44、hile (front != NULL && !find)if (isequal(front, target)find = 1;break;/*get_num(front, temp);if (move_up(temp)if(equal(temp,target)new_node= (QNode *)malloc(sizeof(QNode);set_num(new_node, temp);new_node->parent = front;new_node->next = NULL;rear->next = new_node;rear = new_node;*/g

45、et_num(front, temp);if (move_up(temp) && !exist(front, temp)new_node= (QNode *)malloc(sizeof(QNode);set_num(new_node, temp);new_node->parent = front;new_node->next = NULL;rear->next = new_node;rear = new_node;step+;get_num(front, temp);if (move_left(temp) && !exist(front, te

46、mp)new_node= (QNode *)malloc(sizeof(QNode);set_num(new_node, temp);new_node->parent = front;new_node->next = NULL;rear->next = new_node;rear = new_node;step+;get_num(front, temp);if (move_down(temp) && !exist(front, temp) new_node= (QNode *)malloc(sizeof(QNode);set_num(new_node, tem

47、p);new_node->parent = front;new_node->next = NULL;rear->next = new_node;rear = new_node;step+;get_num(front, temp);if (move_right(temp) && !exist(front, temp)new_node= (QNode *)malloc(sizeof(QNode);set_num(new_node, temp);new_node->parent = front;new_node->next = NULL;rear->

48、;next = new_node;rear = new_node;step+; front=front->next; count+;if (find) count=0;for (p = front; p != NULL; p = p->parent) print(p);printf("-A-n");count+;printf(" 共花費(fèi)時(shí)間.4fms,得出最優(yōu)解共需d個(gè)節(jié) 點(diǎn) ,n",(double)clock()-now/*/CLOCKS_PER_SEC*/,count);int cansolve(int num1, int num2)in

49、t i, j;int sum1 = 0, sum2 = 0;for (i = 0; i < 9; i+)for (j = 0; j < i; j+)if (num1j > num1i && num1i != 0) +sum1;if (num2j > num2i && num2i != 0) +sum2;if (sum1 % 2 = sum2 % 2) return 1;else return 0;int equal(int num1,int num2)for(int i=0;i<9;i+)if(num1i!=num2i)return 0;return 1;void input(int num)int i = 0,j = 0,flag = 0;char c;while(i < 9)while(c = getchar() != 10)if(c = ' ')if(flag