八數(shù)碼問(wèn)題C語(yǔ)言A星算法詳細(xì)實(shí)驗(yàn)報(bào)告含代碼

1、一、實(shí)驗(yàn)內(nèi)容和要求八數(shù)碼問(wèn)題：在3X3的方格棋盤上，擺放著1到8這八個(gè)數(shù)碼，有1個(gè) 方格是空的，其初始狀態(tài)如圖1所示，要求對(duì)空格執(zhí)行空格左移、空格右 移、空格上移和空格下移這四個(gè)操作使得棋盤從初始狀態(tài)到目標(biāo)狀態(tài)。例如：283164705（a）初始狀態(tài)圖1八數(shù)碼問(wèn)題示意圖請(qǐng)任選一種盲目搜索算法（廣度優(yōu)先搜索或深度優(yōu)先搜索）或任選一 種啟發(fā)式搜索方法（全局擇優(yōu)搜索，加權(quán)狀態(tài)圖搜索，A算法或A*算法） 編程求解八數(shù)碼問(wèn)題（初始狀態(tài)任選）。選擇一個(gè)初始狀態(tài)，畫出搜索樹(shù)， 填寫相應(yīng)的OPEN表和CLOSED表，給出解路徑，對(duì)實(shí)驗(yàn)結(jié)果進(jìn)行分析總結(jié), 得出結(jié)論。二、實(shí)驗(yàn)?zāi)康? .熟悉人工智能系統(tǒng)中的問(wèn)題求解

2、過(guò)程；2 .熟悉狀態(tài)空間的盲目搜索和啟發(fā)式搜索算法的應(yīng)用；3 .熟悉對(duì)八數(shù)碼問(wèn)題的建模、求解及編程語(yǔ)言的應(yīng)用。三、實(shí)驗(yàn)算法A*算法是一種常用的啟發(fā)式搜索算法。在A*算法中，一個(gè)結(jié)點(diǎn)位置的好壞用估價(jià)函數(shù)來(lái)對(duì)它進(jìn)行評(píng)估。A*算法的 估價(jià)函數(shù)可表示為:f' (n) = g' (n) + h，(n)這里，f'(n)是估價(jià)函數(shù)，g' (n)是起點(diǎn)到終點(diǎn)的最短路徑值(也稱為最小 耗費(fèi)或最小代價(jià))，h' (n)是n到目標(biāo)的最短路經(jīng)的啟發(fā)值。由于這個(gè)f' (n) 其實(shí)是無(wú)法預(yù)先知道的，所以實(shí)際上使用的是下面的估價(jià)函數(shù)：f (n) = g(n) + h(n)其中g(shù)

3、(n)是從初始結(jié)點(diǎn)到節(jié)點(diǎn)n的實(shí)際代價(jià)，h(n)是從結(jié)點(diǎn)n到目標(biāo)結(jié)點(diǎn) 的最佳路徑的估計(jì)代價(jià)。在這里主要是h(n)體現(xiàn)了搜索的啟發(fā)信息，因?yàn)?g(n)是已知的。用f (n)作為f' (n)的近似，也就是用g(n)代替g' (n), h(n) 代替h' (n)。這樣必須滿足兩個(gè)條件：(1) g(n)>=g (n)(大多數(shù)情況下都 是滿足的，可以不用考慮)，且f必須保持單調(diào)遞增。(2) h必須小于等于 實(shí)際的從當(dāng)前節(jié)點(diǎn)到達(dá)目標(biāo)節(jié)點(diǎn)的最小耗費(fèi)h(n)*h'(n)。第二點(diǎn)特別的 重要。可以證明應(yīng)用這樣的估價(jià)函數(shù)是可以找到最短路徑的。*算法的步驟A*算法基本上與廣度優(yōu)先

4、算法相同，但是在擴(kuò)展出一個(gè)結(jié)點(diǎn)后，要計(jì)算它 的估價(jià)函數(shù)，并根據(jù)估價(jià)函數(shù)對(duì)待擴(kuò)展的結(jié)點(diǎn)排序，從而保證每次擴(kuò)展的 結(jié)點(diǎn)都是估價(jià)函數(shù)最小的結(jié)點(diǎn)。A*算法的步驟如下：1)建立一個(gè)隊(duì)列，計(jì)算初始結(jié)點(diǎn)的估價(jià)函數(shù)f,并將初始結(jié)點(diǎn)入隊(duì)，設(shè)置隊(duì)列頭和尾指針。2）取出隊(duì)列頭（隊(duì)列頭指針?biāo)福┑慕Y(jié)點(diǎn)，如果該結(jié)點(diǎn)是目標(biāo)結(jié)點(diǎn)，則 輸出路徑，程序結(jié)束。否則對(duì)結(jié)點(diǎn)進(jìn)行擴(kuò)展。3）檢查擴(kuò)展出的新結(jié)點(diǎn)是否與隊(duì)列中的結(jié)點(diǎn)重復(fù)，若與不能再擴(kuò)展的結(jié) 點(diǎn)重復(fù)（位于隊(duì)列頭指針之前），則將它拋棄；若新結(jié)點(diǎn)與待擴(kuò)展的結(jié)點(diǎn) 重復(fù)（位于隊(duì)列頭指針之后），則比較兩個(gè)結(jié)點(diǎn)的估價(jià)函數(shù)中g(shù)的大小， 保留較小g值的結(jié)點(diǎn)。跳至第五步。4）如果擴(kuò)展出的新結(jié)點(diǎn)與

5、隊(duì)列中的結(jié)點(diǎn)不重復(fù)，則按照它的估價(jià)函數(shù)f 大小將它插入隊(duì)列中的頭結(jié)點(diǎn)后待擴(kuò)展結(jié)點(diǎn)的適當(dāng)位置，使它們按從小到 大的順序排列，最后更新隊(duì)列尾指針。5）如果隊(duì)列頭的結(jié)點(diǎn)還可以擴(kuò)展，直接返回第二步。否則將隊(duì)列頭指針 指向下一結(jié)點(diǎn)，再返回第二步。四、程序框圖開(kāi)始五、實(shí)驗(yàn)結(jié)果及分析輸入初始狀態(tài)：2 8 3目標(biāo)狀態(tài)：12 3送定 CAUsersMinuxkADktop隊(duì)工百蹴 demo2.exe髓JAW陵2H31G47MS輸入目標(biāo)狀態(tài)1238 H 4765初始狀態(tài)，2 8 316 47 0SSWD 1Process exited with return ualuc H Pi*ese any kgy to c

6、ontinue .CLOSE00 10 1 50 15 70 15 7 60 1 5 7 6 9運(yùn)行結(jié)果屏幕打印OPEN 表與 CLOSE 表:OPEN12 3 4234562346723468923489102 3 4 8 11 12 132 3 4 8 12 13 14 150 1 5 7 6 9 113 4 8 12 13 14 15 16 170 1 5 7 6 9 11 24 8 12 13 14 15 16 17 18 19114 8 12 13 14 15 16 17 19 2011188 12 13 14 15 16 17 19 21 22111812 13 14 15 16

7、1719212223111812 13 14 15 16 17192122242511184 8 2312 13 14 15 16 17192122242611184 8 23 24發(fā)現(xiàn)26為目標(biāo)節(jié)點(diǎn)搜索樹(shù):24注釋：每個(gè)方格中最上面兩個(gè)數(shù) 字分別為編號(hào)與啟發(fā)值，下O 1 832-8 4 231-六、結(jié)論對(duì)于八數(shù)碼問(wèn)題，BFS算法最慢，A*算法較快。八數(shù)碼問(wèn)題的一個(gè)狀態(tài) 實(shí)際上是09的一個(gè)排列，對(duì)于任意給定的初始狀態(tài)和目標(biāo)，不一定有解， 也就是說(shuō)從初始狀態(tài)不一定能到達(dá)目標(biāo)狀態(tài)。因?yàn)榕帕杏衅媾帕泻团寂帕?兩類，從奇排列不能轉(zhuǎn)化成偶排列。如果一個(gè)數(shù)字08的隨機(jī)排列0,用 F(X)表示數(shù)字X前面比它

8、小的數(shù)的個(gè)數(shù)，全部數(shù)字的F(X)之和為Y=£ (F(X),如果Y為奇數(shù)則稱原數(shù)字的排列是奇排列，如果Y為偶數(shù)則稱原 數(shù)字的排列是偶排列。因此，可以在運(yùn)行程序前檢查初始狀態(tài)和目標(biāo)狀態(tài) 的排序的奇偶行是否相同，相同則問(wèn)題可解，應(yīng)當(dāng)能搜索到路徑。否則無(wú) 解。七、源程序及注釋#include <iostream>#include <ctime>ttinclude <vector>usingnamespacestd;constintROW 二3;constintCOL 二3;constintMAXDISTANCE = 10000;constintMAXNUM

9、 = 10000；int abs(int a)if (a>0) return a;else return -a;typedef struct _Nodeint digitROWCOL;int dist; ist != MAXNUM)return false;return true;igitLi j !=bool isEqual(int index, int digitlCOL) digiti j)return false;return true;)ostream& operator<<(ostream& os, Node& node) for (int

10、 i = 0; i < ROW; i+) for (int j = 0; j < COL; j+)os << ij j ；os << endl;)return os;)void PrintSteps(int index, vector<Node>& rstep_v) ndex;while (index != 0) (node_vindex);index = node_vindex. index;)for (int i = () - 1; i >= 0; i)cout << "Step << () -

11、 i<< endl << rstep-vLi << endl;void Swap(int& a, int& b) igitiLj;)int GetMinNode() ist = MAXNUM) continue;else if (node_vi. dist + node_vLi. dep) < dist) loc = i;dist = node_vi. dist + node_vi. dep;)return loc;)bool isExpandable(Node& node) igit iLj= 0) x 二i; y = j;f

12、lag = true;break;)else flag = false;if(flag)break;Node node_up; ep + 1;(node_up);)Node node_down; ep + 1;(node_down);)Node node_left;ep + 1;(node_left);)Node node_right; ep + 1;(node_right);)node_vindex. dist = MAXNUM;)int main () int number;cout << 輸入初始狀態(tài)： << endl;for (int i = 0; i <

13、 ROW; i+)for (int j = 0; j < COL; j+) cin >> number;Li jj = number;)=0;=1;cout « 輸入目標(biāo)狀態(tài) endl;for (int m = 0; m < ROW; m+)for (int n = 0; n < COL; n+) cin >> number;nJ nJ = number;)(src);while (1) if (isEmptyOfOPENQ) cout <<找不到解! << endl;return -1;else (int loc; / the location of the minimize nodeloc = GetMinNode