八數(shù)碼問題課程設(shè)計(jì)報(bào)告(共27頁)

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

2、析和任務(wù)定義1.1問題分析由題目知給出一個(gè)初始狀態(tài)和一個(gè)目標(biāo)狀態(tài)，找出一種從初始轉(zhuǎn)變成目標(biāo)狀態(tài)的移動(dòng)步驟。所謂問題的一個(gè)狀態(tài)就是棋子在棋盤上的一種擺法。解八數(shù)碼問題實(shí)際上就是找出從初始狀態(tài)到達(dá)目標(biāo)狀態(tài)所經(jīng)過的一系列中間過渡狀態(tài)。要求分別采用廣度優(yōu)先搜索和啟發(fā)式搜索兩種方法對(duì)八數(shù)碼問題進(jìn)行求解。且棋盤通過空格的上、下、右四種操作來改變狀態(tài)。所以需要解決的問題為每個(gè)狀態(tài)的表示和每個(gè)狀態(tài)變化的操作，設(shè)計(jì)出適合相應(yīng)搜索的數(shù)據(jù)結(jié)構(gòu)，完成相應(yīng)算法思想。1.2任務(wù)定義(1)完成棋盤狀態(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開始逐層的對(duì)其進(jìn)行擴(kuò)展，并考察其其是否為目的節(jié)點(diǎn)，若不是將其放入待考察隊(duì)列中，在第n層節(jié)點(diǎn)沒有完全進(jìn)行考察并擴(kuò)展完成前，不對(duì)第n+1層進(jìn)行擴(kuò)展。隊(duì)列中節(jié)點(diǎn)總是按照先后順序進(jìn)行排列，先進(jìn)的排在前面，后進(jìn)的排在后面。由此可知我們可以通過隊(duì)列的思想完成搜索，其具體搜索過程如下。1)初始化頭結(jié)點(diǎn)front，front=real;2)若front=null,問題無解,程序結(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) 棋盤狀態(tài)的表示因?yàn)槊恳粋€(gè)棋盤狀態(tài)是靜止且確定的所以采取一個(gè)一維數(shù)組便可將其狀態(tài)表示出來，數(shù)組按照下標(biāo)順序從左至右從上至下依次對(duì)應(yīng)?？崭窨捎闪銇肀硎?。圖二此狀態(tài)可表示為int num9=2,5,4,3,0,7,1,8,6。2) 搜索結(jié)構(gòu)設(shè)計(jì) 根據(jù)算法要求，需要對(duì)棋盤不斷的進(jìn)行動(dòng)態(tài)擴(kuò)展，且盲目搜索產(chǎn)生的數(shù)據(jù)巨大，所以不能采用靜態(tài)鏈表或數(shù)組存儲(chǔ)，因此選擇采用動(dòng)態(tài)鏈表來存儲(chǔ)搜索過程中的每一個(gè)狀態(tài)。因?yàn)樗阉魇歉鶕?jù)一種狀態(tài)對(duì)其進(jìn)行擴(kuò)展，直至達(dá)到目的狀態(tài)，由于要返回一個(gè)最優(yōu)路徑因此需要確定擴(kuò)展關(guān)系，我選擇用一個(gè)*parent來記

5、錄此關(guān)系。此時(shí)存儲(chǔ)結(jié)構(gòu)可由此圖表示圖三當(dāng)擴(kuò)展至目的狀態(tài)時(shí)可通過parent指針找到路徑。由此我們可以設(shè)置節(jié)點(diǎn)類型為typedef struct Node struct Node *parent; int num9; Node *next;QNode； 2.2啟發(fā)式搜索（1）啟發(fā)式搜索的思想介紹搜索算法可分為兩大類：無信息的搜索算法和有信息的搜索算法。無信息的搜索又稱盲目搜索，盲目搜索不考慮節(jié)點(diǎn)好壞，而對(duì)于八數(shù)碼問題的解決過程是有跡可循的，我們通過是否接近目標(biāo)狀態(tài)來判斷節(jié)點(diǎn)的好壞，因此可以通過啟發(fā)式搜索中的A*算法來解決這個(gè)問題。簡(jiǎn)單來說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é)合起來對(duì)節(jié)點(diǎn)進(jìn)行評(píng)價(jià)：f(n)=g(n)+h(n)。由此設(shè)計(jì)如下(1) 把起始節(jié)點(diǎn)放到OPEN表中，并計(jì)算節(jié)點(diǎn)S的(2) 如果OPEN是空表，則失敗退出，無解；(3) 從OPEN表中選擇一個(gè)值最小的節(jié)點(diǎn)。如果有幾個(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)；(4) 把節(jié)點(diǎn)從 OPEN 表中移出，并把它放入 CLOSED 的已擴(kuò)展節(jié)點(diǎn)表中;如果是個(gè)目標(biāo)節(jié)點(diǎn)，則成功退出，求得一個(gè)解；(5

7、) 擴(kuò)展節(jié)點(diǎn)，生成其全部后繼節(jié)點(diǎn)。對(duì)于的每一個(gè)后繼節(jié)點(diǎn)：計(jì)算；如果 既不在OPEN表中，又不在CLOCED表中，則用估價(jià)函數(shù)把它添入OPEN表中。從加一指向其父節(jié)點(diǎn)的指針，以便一旦找到目標(biāo)節(jié)點(diǎn)時(shí)記住一個(gè)解答路徑；如果已在OPEN表或CLOSED表中，則比較剛剛對(duì)計(jì)算過的和前面計(jì)算過的該節(jié)點(diǎn)在表中的值。如果新的較小，則(I)以此新值取代舊值。(II)從指向，而不是指向他的父節(jié)點(diǎn)。(III)如果節(jié)點(diǎn)在CLOSED表中，則把它移回OPEN表中。轉(zhuǎn)向（2）。流程圖如下圖四(2) 數(shù)據(jù)結(jié)構(gòu)的選擇和概要設(shè)計(jì) 由于搜索特點(diǎn)，采用的基礎(chǔ)存儲(chǔ)結(jié)構(gòu)和廣度優(yōu)先搜索相同，不同之處為啟發(fā)式搜索使用兩條鏈表，所以設(shè)計(jì)一個(gè)

8、表結(jié)構(gòu)，用來聲明兩條鏈表。 節(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);int move_right(int num);以上移為例，

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

10、狀態(tài)數(shù)組targetIf(問題可解)While(隊(duì)頭指針非空時(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 while End 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)是否屬于OPEN表或CLOSED表，是則返回節(jié)點(diǎn)地址，否則返回空地址。void Putinto(Node * suc,Lstack * list)

11、把節(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或CLOSED表并作出相應(yīng)的處理。int Canspread(Node suc, int n)判斷空格可否向該方向移動(dòng)，表示空格向上向下向左向右移。v

12、oid 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 speed)總執(zhí)行函數(shù)。void qf(int init9,int target9)啟發(fā)式搜索總函數(shù)。（2）搜索過程偽碼輸入：初

13、始狀態(tài)，目標(biāo)狀態(tài)輸出：從初始狀態(tài)到目標(biāo)狀態(tài)的一系列過程算法描述：Begin：讀入初始狀態(tài)和目標(biāo)狀態(tài)，并計(jì)算初始狀態(tài)評(píng)價(jià)函數(shù)值f；根據(jù)初始狀態(tài)和目標(biāo)狀態(tài)，判斷問題是否可解；If(問題可解)把初始狀態(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)空格位置來擴(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表中移

14、至Close表；End whileEnd if輸出結(jié)果；End4、 上機(jī)調(diào)試過程4.1遇到的問題和分析（1）本次課程設(shè)計(jì)過程是兩種搜索方式分開開發(fā)，因此在綜合在一起的時(shí)候兩種方式的代碼合在一起略顯雜糅，程序可讀性較差。（2）在做啟發(fā)式搜索時(shí)，發(fā)現(xiàn)效率并未達(dá)到預(yù)期，查閱資料得知h值取得不好，沒有完全切合搜索規(guī)律，h值應(yīng)為每個(gè)方格到其正確位置的路徑之和，而我僅統(tǒng)計(jì)的是錯(cuò)位之和同時(shí)發(fā)現(xiàn)若h值取得越大其搜索速度越快單難以保證得出的是最優(yōu)解。因此我設(shè)計(jì)了一個(gè)系數(shù)1000來進(jìn)行加速。（3）在設(shè)計(jì)廣度優(yōu)先搜索時(shí)指針操作出現(xiàn)失誤，導(dǎo)致進(jìn)度一度停滯，后放棄改為數(shù)組操作才完成程序4.2時(shí)空效率分析（1） 廣度優(yōu)先

15、搜索是一種十分浪費(fèi)空間的搜索方法，有時(shí)會(huì)陷入死循環(huán)。同時(shí)在時(shí)間效率上廣度優(yōu)先搜索效率不穩(wěn)定，若搜索深度過大則時(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é)省空間效率。5、 測(cè)試結(jié)果及其分析圖五圖六圖七圖八圖九圖十圖十一圖十二圖十 （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)目標(biāo)狀態(tài)4ms6109ms6初始狀態(tài)目標(biāo)狀態(tài)無解0無解無解無解初始狀態(tài)目標(biāo)狀態(tài)4399ms15196ms15初始狀態(tài)目標(biāo)狀態(tài)48ms9128ms9初始狀態(tài)目標(biāo)狀態(tài)12537

16、ms16300ms28初始狀態(tài)目標(biāo)狀態(tài)112ms11347ms25表一 （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)劣的考察使其在時(shí)間上展現(xiàn)出較大優(yōu)勢(shì)。但啟發(fā)式搜索可能無法獲取最優(yōu)解。6、 用戶使用說明在輸入八數(shù)碼狀態(tài)時(shí)將八數(shù)碼上數(shù)字從上至下從左至右，依次輸入其中空格用0代替，且每個(gè)數(shù)字用空格隔開。7、 參考文獻(xiàn)1 錢瑩基于廣度優(yōu)先的八數(shù)碼問題解決方案電腦學(xué)習(xí)，2008:45-462 張鴻人工智能中求解八數(shù)碼問題算法與實(shí)現(xiàn)軟件導(dǎo)刊，2009:62-648

17、、 附錄#include "stdio.h"#include <stdlib.h>#include <time.h>#include <math.h>#include<process.h>typedef struct Node struct 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;St

18、ack,* 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);int 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

19、init9, int target9);Node * Minf(Lstack * Open);Node * Belong(Node * suc,Lstack * list);void Putinto(Node * suc,Lstack * list);int Equal(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 go

20、al, int i);void Spreadchild(Node * child,int n);int BelongProgram(Lnode * suc ,Lstack * Open ,Lstack * Closed ,Node goal ,float speed);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("輸入

21、初始狀態(tài):n"); input(init); printf("輸入目標(biāo)狀態(tài):n"); input(target);if(cansolve(init,target) printf("使用廣度優(yōu)先進(jìn)行搜索:n");bfs(init,target); printf("使用啟發(fā)式進(jìn)行搜索:n");qf(init,target); else printf("無解"); getchar(); system("cls"); goto l; Node * Minf(Lstack * Open)/選取O

22、PEN表上f值最小的節(jié)點(diǎn)，返回該節(jié)點(diǎn)地址Lstack temp = (*Open)->next,min = (*Open)->next,minp = (*Open);Node * minx; while(temp->next != NULL)if(temp->next ->npoint->f) < (min->npoint->f)min = temp->next;minp = temp;temp = temp->next;minx = min->npoint;temp = minp->next; minp->n

23、ext = minp->next->next;free(temp);return minx;int Equal(Node * suc,Node * goal)/判斷節(jié)點(diǎn)是否相等，相等，不相等for(int i = 0; i < 9; i + )if(suc->numi != goal->numi)return 0; return 1;Node * Belong(Node * suc,Lstack * list)/判斷節(jié)點(diǎn)是否屬于OPEN表或CLOSED表，是則返回節(jié)點(diǎn)地址，否則返回空地址Lstack temp = (*list) -> next ;if(te

24、mp = NULL)return NULL;while(temp != NULL)if(Equal(suc,temp->npoint)return temp -> npoint;temp = temp->next;return NULL;void Putinto(Node * suc,Lstack * list)/把節(jié)點(diǎn)放入OPEN 或CLOSED 表中 Stack * temp;temp =(Stack *) malloc(sizeof(Stack);temp->npoint = suc;temp->next = (*list)->next;(*list)

25、->next = temp;/計(jì)算f值部分-開始/double Fvalue(Node suc, Node goal, float speed)/計(jì)算f值double Distance(Node,Node,int);double h = 0;for(int i = 1; i <= 8; i+)h = h + Distance(suc, goal, i);return h*speed + suc.g; /f = h + g;(speed值增加時(shí)搜索過程以找到目標(biāo)為優(yōu)先因此可能不會(huì)返回最優(yōu)解) double Distance(Node suc, Node goal, int i)/計(jì)算

26、方格的錯(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 - h2%3);/計(jì)算f值部分-結(jié)束/擴(kuò)展后繼節(jié)點(diǎn)部分的函數(shù)-開始/int BelongProgram(Lnode * suc ,Lstack * Open ,Lstack * Closed ,Node goal ,float speed)/判斷子節(jié)點(diǎn)是否屬于OPEN或CLOSED表并作出相應(yīng)的處理Node * temp = NU

27、LL;int flag = 0;if(Belong(*suc,Open) != NULL) | (Belong(*suc,Closed) != NULL)if(Belong(*suc,Open) != NULL) temp = Belong(*suc,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;elseP

28、utinto(* suc, Open);(*suc)->f = Fvalue(*suc, goal, speed);return flag; int Canspread(Node suc, int n)/判斷空格可否向該方向移動(dòng)，表示空格向上向下向左向右移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

29、;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表示方向，表示空格向上向下向左向右移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=

30、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->numi = temp;child->numloc = 0;int Spread(Lnode * suc, Lstack * Open, Lstack * Closed, Node goal, float speed)/擴(kuò)展后繼節(jié)點(diǎn)總函數(shù)int i;Node * child;for(i = 0; i < 4; i+)if(Canspread(*suc, i+

31、1) /判斷某個(gè)方向上的子節(jié)點(diǎn)可否擴(kuò)展child = (Node *) malloc(sizeof(Node); /擴(kuò)展子節(jié)點(diǎn) child->g = (*suc)->g +1; /算子節(jié)點(diǎn)的g值 child->parent = (*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)是否屬于OPEN或CLOSED表并作出相應(yīng)的處理free(child);/step+;return 1;/擴(kuò)展后

32、繼節(jié)點(diǎn)部分的函數(shù)-結(jié)束/Node * Process(Lnode * org, Lnode * goal, Lstack * Open, Lstack * Closed, float speed)/總執(zhí)行函數(shù)while(1)if(*Open)->next = NULL)return NULL; /判斷OPEN表是否為空，為空則失敗退出 Node * minf = Minf(Open); /從OPEN表中取出f值最小的節(jié)點(diǎn)Putinto(minf, Closed); /將節(jié)點(diǎn)放入CLOSED表中 if(Equal(minf, *goal)return minf; /如果當(dāng)前節(jié)點(diǎn)是目標(biāo)節(jié)點(diǎn)，

33、則成功退出 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á)目標(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)prin

34、tf(" %d ",result->numi*3+j);else printf(" ");printf("n");return n+1;*/void qf(int 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(si

35、zeof(Node);Node * p;org->parent = NULL; /初始狀態(tài)節(jié)點(diǎn)org->f =1;org->g =1;int count=0; /org->step =1; Node * goal = (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)輸入搜索速

36、度(速度越高越無法保證結(jié)果是最優(yōu)解):");/ scanf("%f",&speed);/ while(c = getchar() != 10);/ printf("搜索中，請(qǐng)耐心等待(如果您覺得時(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=

37、 p->parent) print(p);printf("-n");/ printf("搜索g:%f",p->g);count+; printf("搜索所用時(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(

38、int init,int target) int temp9; int find = 0;double now=0;int step=1,count=1; QNode *front , *rear, *new_node, *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(); fro

39、nt = (QNode *)malloc(sizeof(QNode); set_num(front, init); front->parent = NULL; front->next = NULL; rear = front; while (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(QNo

40、de); set_num(new_node, temp); new_node->parent = front; new_node->next = NULL; rear->next = new_node; rear = new_node;*/ get_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_

41、node->next = NULL; rear->next = new_node; rear = new_node;step+; get_num(front, temp); if (move_left(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 = ne

42、w_node;step+; get_num(front, temp); if (move_down(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_right(temp)

43、&& !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+; front=front->next; count+; if (find) count=0; for (p = front; p != NULL; p = p->parent) print

44、(p);printf("-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) int 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

45、 (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 >= 0)flag = 0;else if(c >= '0' && c <= '8')if(flag = 0)numi = (c-'0');flag = 1;for(j =0; j < i; j+)if(numj = numi)flag = -2; i+;/else if(fl