人工智能(A星算法)

1、A*算法实验报告 实验目的 1熟悉和掌握启发式搜索的定义、估价函数和算法过程 2. 学会利用A*算法求解N数码难题 3. 理解求解流程和搜索顺序 实验原理 A*算法是一种有序搜索算法，其特点在于对估价函数的定义上。对于一般的 有序搜索，总是选择f值最小的节点作为扩展节点。因此，f是根据需要找到一 条最小代价路径的观点来估算节点的， 所以，可考虑每个节点n的估价函数值为 两个分量：从起始节点到节点n的代价以及从节点n到达目标节点的代价。 实验条件 1. Window NT/xp/7及以上的操作系统 2. 内存在512M以上 3. CPU在奔腾II以上 实验内容 1. 分别以8数码和15数码为例实

2、际求解A*算法 2. 画出A*算法求解框图 3. 分析估价函数对搜索算法的影响 4. 分析A*算法的特点 实验分析 1. A*算法基本步骤 1）生成一个只包含开始节点n。的搜索图G,把n放在一个叫OPEI的列表上。 2）生成一个列表CLOSE，它的初始值为空。 3）如果OPE表为空，则失败退出。 4）选择OPE上的第一个节点，把它从OPE中移入CLPSEP称该节点为n。 5）如果n是目标节点，顺着G中，从n到no的指针找到一条路径，获得解决方 案，成功退出（该指针定义了一个搜索树，在第 7步建立）。 2 6）扩展节点n,生成其后继结点集M在G中, n的祖先不能在M中。在G中安 置M勺成员，使他

3、们成为n的后继。 7）从M勺每一个不在G中的成员建立一个指向n的指针（例如，既不在OPE中, 也不在CLOSED）。把M的这些成员加到OPE中。对M勺每一个已在OPE中或 CLOSE中的成员m如果到目前为止找到的到达 m勺最好路径通过n,就把它 的指针指向n。对已在CLOSE中的M勺每一个成员，重定向它在G中的每一个 后继，以使它们顺着到目前为止发现的最好路径指向它们的祖先。 8）按递增f*值，重排OPEN相同最小f*值可根据搜索树中的最深节点来解决）。 9）返回第3步。 在第7步中，如果搜索过程发现一条路径到达一个节点的代价比现存的路径 代价低，就要重定向指向该节点的指针。已经在CLOSE中

4、的节点子孙的重定向保 存了后面的搜索结果，但是可能需要指数级的计算代价。 实验步骤 算法流程图 14 程序代码 #in elude #i nclude #in elude using n amespace std; const int ROW = 3;/ 行数 const int COL = 3;/ 列数 con st int MAXDISTANCE = 10000;/ 最多可以有的表的数目 con st int MAXNUM = 10000; typedef struct _Node int digitROWCOL; int dist; /一个表和目的表的距离 int dep; / t 深度

5、 int in dex; /节点的位置 Node; Node src, dest;/ 父节表目的表 vector no de_v; /存储节点 bool isEmptyOfOPEN() /ope n表是否为空 for (int i = 0; i no de_v.size(); i+) if (n ode_vi.dist != MAXNUM) return false; return true; 判断这个最优的节 bool isEqual(i nt in dex, i nt digitCOL) / 点是否和目的节点一样 for (i nt i = 0; i ROW; i+) for (i nt

6、j = 0; j COL; j+) if (n ode_vi ndex.digi tij != digitij)return false; return true; ostream i ROW; i+) for (i nt j = 0; j COL; j+) os no de.digitij ; os en dl; return os; 输出每一 输出每一步的 void Prin tSteps(i nt in dex, vector in dex = no de_vi ndex.i ndex; while (in dex != 0) rstep_v.push_back( no de_vi nd

7、ex); in dex = no de_vi ndex.i ndex; _ for (int i = rstep_v.size() - 1; i = 0; i-) 探索过程一 cout Step rstep_v.size() - i endl rstep_vi en dl; void Swap(i nt t = a; a = b; b = t; void Assig n(N ode i ROW; i+) for (i nt j = 0; j COL; j+) no de.digitij = no de_vi ndex.digitij; 即最优节点 _ int GetMi nNode() / 找

8、到最小的节点的位置 int dist = MAXNUM; int loc; / the locati on of mi ni mize node for (int 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.dep) dist) loc = i; dist = no de_vi.dist + no de_vi.dep; 一 一 return loc; bool isExpa ndable(Node i no de_v.size()

9、; i+) if (isEqual(i, no de.digit) return false; return true; int Dista nce(Node 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 = digitkl) dista nee += abs(i - k) + abs(j - l); flag = true; break; els

10、e flag = false; if (flag) break; retur n 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 0) Swap (no de_up.digitxy, no de_up.digitx - 1y); if (isExpa ndable (no de_up) _ dist_up = Dist

11、a nce( no de_up, dest.digit); no de_up.i ndex = in dex; no de_up.dist = dist_up; no de_up.dep = no de_vi ndex.dep + 1; no de_v.push_back( no de_up); Node no de_dow n; Assig n(no de_dow n, i ndex);/向下扩展的节点 int dist_dow n 二 MAXDISTANCE; if (x 0) Swap( node_left.digitxy, node_left.digitxy - 1); if (isE

12、xpa ndable (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.dep = no de_vi ndex.dep + 1; no de_v.push_back( no de_left); 一一 一 Node no de_right; Assig n(no de_right, i ndex);/向右扩展的节点 int dist_right = MAXDISTANCE; if (y 2)

13、 Swap (no de_right.digitxy, no de_right.digitxy + 1); if (isExpa ndable (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.dep = no de_vi ndex.dep + 1; no de_v.push_back( no de_right); 一一 一 node_v in dex.dist = MA

14、XNUM; int mai n() / 主函数 int nu mber; cout I nput source: en dl; for (i nt i = 0; i ROW; i+)/输入初始的表 for (i nt j = 0; j nu mber; src.digitij = nu mber; src.i ndex = 0; src.dep = 1; cout In put dest in atio n: en dl;输入目的表 for (i nt m = 0; m ROW; m+) for (i nt n 二 0; n nu mber; dest.digitm n = nu mber;

15、n ode_v.push_back(src);在容器的尾部加一个数据 cout Search. en dl; clock_t start = clock(); while (1) if (isEmptyOfOPEN() cout Ca nnt solve this stateme nt! en dl; return -1; else 卄 int loc; / the locati on of the mi ni mize node最优节点的 位置 loc = GetMi nN ode(); if(isEqual(loc, dest.digit) vector rstep_v; cout Sou

16、rce: en dl; cout src en dl; Prin tSteps(loc, rstep_v); cout Successful! en dl; cout Usi ng (clock() - start) / CLOCKS_PER_SEC sec on ds. en dl; break; else ProcessNode(loc); return 0; 程序运行效果图 2 8 3 1 6 4 7 5 （初始状态） 1 2 3 8 0 4 7 6 5 （结束状态） r :C0DE(C + 4)A 星鸽法DebugA. MF：CODE(C+ )A星賞法D亡bugA.* 严* Step 2 2 0 3 1 8 7 G 5 HF:COOE(C + + )A 星算法D 訪 ugA. 3 4 5 286 t s 1 o 7 Step 5 1 2 3 8 0 4 7 6 5 Successful! Using 0