人工智能A星算法

1、A*算法實驗報告實驗?zāi)康?熟悉和掌握啟發(fā)式搜索的定義、估價函數(shù)和算法過程2.學(xué)會利用A*算法求解N數(shù)碼難題3.理解求解流程和搜索順序?qū)嶒炘鞟*算法是一種有序搜索算法，其特點在于對估價函數(shù)的定義上。對于一般的有序搜索，總是選擇f值最小的節(jié)點作為擴展節(jié)點。因此，f是根據(jù)需要找到一 條最小代價路徑的觀點來估算節(jié)點的， 所以，可考慮每個節(jié)點n的估價函數(shù)值為 兩個分量：從起始節(jié)點到節(jié)點 n的代價以及從節(jié)點n到達(dá)目標(biāo)節(jié)點的代價。實驗條件1. Window NT/xp/7及以上的操作系統(tǒng)2.內(nèi)存在512M以上3. CPU在奔騰II以上實驗內(nèi)容1.分別以8數(shù)碼和15數(shù)碼為例實際求解A*算法2.畫出A*算法求

2、解框圖3.分析估價函數(shù)對搜索算法的影響4.分析A*算法的特點實驗分析1. A*算法基本步驟1)2)生成一個只包含開始節(jié)點no的搜索圖G,把no放在一個叫OPEI的列表上。 生成一個列表CLOSE，它的初始值為空。3)如果OPE表為空，則失敗退出。4)選擇OPE上的第一個節(jié)點，把它從OPE中移入CLPSED稱該節(jié)點為n。5)如果n是目標(biāo)節(jié)點，順著G中，從n到n。的指針找到一條路徑，獲得解決方案，成功退出(該指針定義了一個搜索樹，在第 7步建立)。6) 擴展節(jié)點n，生成其后繼結(jié)點集M在G，n的祖先不能在M中。在G中安置M的成員，使他們成為n的后繼。7）從M勺每一個不在G中的成員建立一個指向n的指針

3、（例如，既不在OPE中,也不在CLOSED）。把M的這些成員加到OPE中。對M勺每一個已在OPE中或CLOSE中的成員m如果到目前為止找到的到達(dá) m勺最好路徑通過n,就把它的指針指向n。對已在CLOSE中的M勺每一個成員，重定向它在G中的每一個后繼，以使它們順著到目前為止發(fā)現(xiàn)的最好路徑指向它們的祖先。8）按遞增f *值，重排OPEN相同最小f*值可根據(jù)搜索樹中的最深節(jié)點來解決）。9）返回第3步。在第7步中，如果搜索過程發(fā)現(xiàn)一條路徑到達(dá)一個節(jié)點的代價比現(xiàn)存的路徑 代價低，就要重定向指向該節(jié)點的指針。已經(jīng)在CLOSE中的節(jié)點子孫的重定向保 存了后面的搜索結(jié)果，但是可能需要指數(shù)級的計算代價。實驗步驟

4、算法流程圖#in elude <vector>using n ames pace std;const int ROW = 3;/ 行數(shù)const int COL = 3;/ 列數(shù)con st int MAXDISTANCE = 10000;/ 最多可以有的表的數(shù)目 con st int MAXNUM = 10000;一個表和目的表的距離 深度節(jié)點的位置typ edef struct _Node int digitROWCOL; int dist; / int dep; / t int in dex; / Node;Node src, dest;/ 父節(jié)表目的表vectorvNode

5、> no de_v; /存儲節(jié)點bool isE mp tyOfO PEN() /o pen表是否為空for (int i = 0; i < no de_v.size(); i+) if (n ode_vi.dist != MAXNUM)return false;return true;判斷這個最優(yōu)的節(jié)bool isEqual(i nt in dex, i nt digitCOL) /點是否和目的節(jié)點一樣for (i nt i = 0; i < ROW; i+)for (i nt j = 0; j < COL; j+) if (n ode_vi ndex.digi ti

6、j != digitij) return false;return true;ostream& op erator<<(ostream& os, Node& node) for (i nt i = 0; i < ROW; i+) for (i nt j = 0; j < COL; j+)os << no de.digitij << ''os << en dl;return os;輸出每一輸出每一步的void Prin tSte ps(i nt in dex, vector<Node>

7、& rstep_v)/個遍歷的節(jié)點 深度遍歷rstep_v. push_back( no de_vi ndex);in dex = no de_vi ndex.i ndex;while (in dex != 0)rstep_v .pu sh_back (no de_vi ndex);in dex = no de_vi ndex.i ndex; "for (i nt i = rstep_v.size() - 1; i >= 0; i-)/探索過程cout << "Ste p ” << rstep_v.size() - i<<

8、endl << rstep_vi << en dl; "void Swap (i nt& a, int& b) int t;t = a;a = b;b = t;void Assig n(N ode& no de, int in dex) for (i nt i = 0; i < ROW; i+)for (i nt j = 0; j < COL; j+)no de.digitij = no de_vi ndex.digitij; int GetMi nNode() /找到最小的節(jié)點的位置即最優(yōu)節(jié)點int dist = MAXN

9、UM;int loc; / the locati on of mi ni mize nodefor (i nt i = 0; i < no de_v.size(); i+)if (n ode_vi.dist = MAXNUM)con ti nue;else if (no de_vi.dist + no de_vi.de p) < dist) loc = i;dist = no de_vi.dist + no de_vi.de p;return loc;bool isEx pan dable(Node& no de)for (int i = 0; i < no de_v

10、.size(); i+) if (isEqual(i, no de.digit) return false;return true;int Dista nce(Node & node, i nt digitCOL) int dista nee = 0;bool flag = false;for(i nt i = 0; i < ROW; i+)for (i nt j = 0; j < COL; j+)for (i nt k = 0; k < ROW; k+) for (i nt l = 0; l < COL; l+) if (no de.digitij = dig

11、itkl) dista nee += abs(i - k) + abs(j - l); flag = true;break;elseflag = false;if (flag)break;retu rn dista nee;int Min Dista nce(i nt a, int b) return (a < b ? a : b);void ProcessNode(i nt in dex)int x, y;bool flag;for (i nt i = 0; i < ROW; i+) for (i nt j = 0; j < COL; j+) if (n ode_vi nd

12、ex.digi tij = 0)"x =i; y = j;flag = true;break;else flag = false;if(flag)break;Node node_up;Assig n(node_up, in dex);/向上擴展的節(jié)點int dist_ up 二 MAXDISTANCE;if (x > 0)Swap(node_up .digitxy, node_up .digitx - 1y); if (isEx pan dable (node_up)dist_ up 二 Dista nce( node_up, dest.digit); node_up .i n

13、dex = in dex;node_up .dist = dist_ up;node_up .de p 二 no de_vi ndex.de p + 1;no de_v .p ush_back( node_up); 一一 "Node no de_dow n;Assig n(no de_dow n, i ndex);/向下擴展的節(jié)點int dist_dow n 二 MAXDISTANCE;if (x < 2)Swa p(no de_dow n.digitxy, no de_dow n. digitx + 1y); if (isEx pan dable (no de_dow n)d

14、ist_dow n 二 Dista nce(no de_dow n, dest.digit);no de_dow n.i ndex = in dex;no de_dow n. dist = dist_dow n;no de_dow n.dep 二 no de_vi ndex.de p + 1;no de_v .p ush_back( no de_dow n); 一一 "Node no de_left;Assig n(no de_left, i ndex);/向左擴展的節(jié)點int dist_left = MAXDISTANCE;if (y > 0)Swa p(n ode_left

15、.digitxy, node_left.digitxy - 1); if (isEx pan dable (no de_left)dist_left = Dista nce( no de_left, dest.digit); no de_left.i ndex = in dex;no de_left.dist = dist_left;no de_left.de p 二 no de_vi ndex.de p + 1;no de_v .p ush_back( no de_left);Node no de_right;Assig n(no de_right, i ndex);/向右擴展的節(jié)點int

16、dist_right = MAXDISTANCE;if (y < 2)Swap(no de_right.digitxy, no de_right.digitxy + 1); if (isEx pan dable (no de_right)dist_right = Dista nce(no de_right, dest.digit);no de_right.i ndex = in dex;no de_right.dist = dist_right;no de_right.de p 二 no de_vi ndex.de p + 1;no de_v .p ush_back( no de_rig

17、ht);node_v in dex.dist = MAXNUM;int mai n() /主函數(shù)int nu mber;輸入初始的表cout << "Input source:" << en dl; for (i nt i = 0; i < ROW; i+)/ for (i nt j = 0; j < COL; j+) cin » nu mber; src.digitij = nu mber;src.i ndex = 0;src.de p 二 1;輸入目的表cout << "Input dest in at

18、i on:" << en dl;/for (i nt m = 0; m < ROW; m+)for (i nt n 二 0; n < COL; n+) cin » nu mber;dest.digitm n二 nu mber;n ode_v. push_back(src);/在容器的尾部加一個數(shù)據(jù)cout << "Search." << en dl;clock_t start = clock();while (1)if (isE mp tyOfO PEN()cout << "Ca nn't solve this stateme nt!" << en dl;return -1;else最優(yōu)節(jié)點的int loc; / the locatio n of the mini mize node位置loc = GetMi nN ode();if(isEqual(loc, dest.digit)vector<Node> rstep_v;cout << "Source:" << en dl;cout << src << en dl;Prin tSte ps(loc, r