人工智能(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,把no放在一个叫OPEI的列表上。2）生成一个列表CLOSE，它的初始值为空。3）如果OPE表为空，则失败退出。4）选择OPE上的第一个节点，把它从OPE中移入CLPSEP称该节点为n。5）如果n是目标节点，顺着G中，从n到no的指针找到一条路径，获得解决方 案，成功退出（该指针定义了一个搜索树，在第 7步建立）。2 / 116）扩展节点n,生成其后继结点集M在G中, n的祖先不能在M中。在G中安 置M勺成员，使他们成为n的后

3、继。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、保 存了后面的搜索结果，但是可能需要指数级的计算代价。实验步骤算法流程图程序代码#include #include #include using namespace std;const int ROW = 3;/行数const int COL = 3;/列数const int MAXDISTANCE = 10000;最/ 多可以有的表的数目const int MAXNUM = 10000;typedef struct _Nodeint digitROWCOL;int dist; / 一个表和目的表的距离int dep; / t 深度int index; / 节点的位置 Node;Node sr

5、c, dest;/ 父节表 目的表vector node_v; / 存储节点bool isEmptyOfOPEN() /open 表是否为空for (int i = 0; i node_v.size(); i+) if (node_vi.dist != MAXNUM)return false;return true;bool isEqual(int index, int digitCOL) / 判断这个最优的节点是否和目 的节点一样for (int i = 0; i ROW; i+)for (int j = 0; j COL; j+) if (node_vindex.digitij != di

6、gitij)return false;return true;ostream& operator(ostream& os, Node& node)for (int i = 0; i ROW; i+) for (int j = 0; j COL; j+)os node.digitij ;os endl;return os;void PrintSteps(int index, vector& rstep_v)/ 输出每一个遍历的 节点 深度遍历rstep_v.push_back(node_vindex);index = node_vindex.index;while (index != 0)rst

7、ep_v.push_back(node_vindex);index = node_vindex.index;for (int i = rstep_v.size() - 1; i = 0; i-)/输/ 出每一步的探索过程cout Step rstep_v.size() - i endl rstep_vi endl;void Swap(int& a, int& b)int t;t = a;a = b;b = t;void Assign(Node& node, int index)for (int i = 0; i ROW; i+)for (int j = 0; j COL; j+)node.di

8、gitij = node_vindex.digitij;int GetMinNode() / 找到最小的节点的位置 即最优节点 int dist = MAXNUM;int loc; / the location of minimize nodefor (int i = 0; i node_v.size(); i+) if (node_vi.dist = MAXNUM) continue;else if (node_vi.dist + node_vi.dep) dist) loc = i;dist = node_vi.dist + node_vi.dep;return loc;bool isEx

9、pandable(Node& node)for (int i = 0; i node_v.size(); i+) if (isEqual(i, node.digit)return false;return true;int Distance(Node& node, int digitCOL) int distance = 0;bool flag = false;for(int i = 0; i ROW; i+)for (int j = 0; j COL; j+)for (int k = for (int l =0; k ROW; k+) 0; l COL; l+) if (node.digit

10、ij = digitkl) distance += abs(i - k) + abs(jflag = true; break;elseflag = false; if (flag) break;return distance;int MinDistance(int a, int b) return (a b ? a : b);void ProcessNode(int index)int x, y;bool flag;for (int i = 0; i ROW; i+) for (int j = 0; j 0)Swap(node_up.digitxy, node_up.digitx - 1y);

11、if (isExpandable(node_up)dist_up = Distance(node_up, dest.digit); node_up.index = index; node_up.dist = dist_up;node_up.dep = node_vindex.dep + 1; node_v.push_back(node_up);Node node_down;Assig n(no de_dow n, in dex); 向下扩展的节点int dist_down = MAXDISTANCE;if (x 0)Swap(node_left.digitxy, node_left.digit

12、xy - 1);if (isExpandable(node_left)dist_left = Distance(node_left, dest.digit); node_left.index = index;node_left.dist = dist_left;node_left.dep = node_vindex.dep + 1;node_v.push_back(node_left);Node node_right;Assig n(no de_right, i ndex);/ 向右扩展的节点 int dist_right = MAXDISTANCE;if (y 2)Swap(node_rig

13、ht.digitxy, node_right.digitxy + 1); if (isExpandable(node_right)dist_right = Distance(node_right, dest.digit); node_right.index = index;node_right.dist = dist_right;node_right.dep = node_vindex.dep + 1; node_v.push_back(node_right);node_vindex.dist = MAXNUM;int main() / 主函数int number;cout Input sou

14、rce: endl;for (i nt i = 0; i ROW; i+)/输入初始的表 for (int j = 0; j number;src.digitij = number;src.index = 0;src.dep = 1;cout Input destination: endl;/ 输入目的表 for (int m = 0; m ROW; m+)for (int n = 0; n number;dest.digitmn = number;n ode_v.push_back(src);/在容器的尾部加一个数据cout Search. en dl;clock_t start = clo

15、ck();while (1)if (isEmptyOfOPEN()cout Ca nnt solve this stateme nt! en dl; retur n -1;elseint loc; / the location of the minimize node 最优节点的位置 loc = GetMi nN ode();if(isEqual(loc, dest.digit)vector rstep_v;cout Source: en dl;cout src en dl;Prin tSteps(loc, rstep_v);cout Successful! en dl;cout Using (clock() - start) / CLOCKS_PER_SEC sec on ds. en dl;break;elseProcessNode(loc);return 0;程序运行效果图2831