人工智能(A星算法).doc

。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数码为例实际求解A*算法2. 画出A*算法求解框图3. 分析估价函数对搜索算法的影响4. 分析A*算法的特点实验分析1. A*算法基本步骤1）生成一个只包含开始节点n0的搜索图G，把n0放在一个叫OPEN的列表上。2）生成一个列表CLOSED，它的初始值为空。3）如果OPEN表为空，则失败退出。4）选择OPEN上的第一个节点，把它从OPEN中移入CLPSED，称该节点为n。5）如果n是目标节点，顺着G中，从n到n0的指针找到一条路径，获得解决方案，成功退出（该指针定义了一个搜索树，在第7步建立）。6）扩展节点n，生成其后继结点集M，在G中，n的祖先不能在M中。在G中安置M的成员，使他们成为n的后继。7）从M的每一个不在G中的成员建立一个指向n的指针（例如，既不在OPEN中，也不在CLOSED中）。把M1的这些成员加到OPEN中。对M的每一个已在OPEN中或CLOSED中的成员m，如果到目前为止找到的到达m的最好路径通过n，就把它的指针指向n。对已在CLOSED中的M的每一个成员，重定向它在G中的每一个后继，以使它们顺着到目前为止发现的最好路径指向它们的祖先。8）按递增f*值，重排OPEN（相同最小f*值可根据搜索树中的最深节点来解决）。9）返回第3步。在第7步中，如果搜索过程发现一条路径到达一个节点的代价比现存的路径代价低，就要重定向指向该节点的指针。已经在CLOSED中的节点子孙的重定向保存了后面的搜索结果，但是可能需要指数级的计算代价。实验步骤算法流程图开始读入棋局初始状态是否可解否o是o初始状态加入open表在open表中找到评价值最小的节点，作为当前结点是目标节点是o否o扩展新状态，把不重复的新状态加入open表中当前结点从open表移除结束输出结果程序代码#include #include #include using namespace std;const int ROW = 3;/行数const int COL = 3;/列数const int MAXDISTANCE = 10000;/最多可以有的表的数目const int MAXNUM = 10000;typedef struct _Node int digitROWCOL; int dist; /一个表和目的表的距离 int dep; / t深度 int index; /节点的位置 Node;Node src, 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 != digitij) 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) rstep_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.digitij = node_vindex.digitij;int GetMinNode() /找到最小的节点的位置 即最优节点 int dist = MAXNUM; int loc; / the location of minimize node for (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 isExpandable(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 = 0; k ROW; k+) for (int l = 0; l COL; l+) if (node.digitij = digitkl) distance += abs(i - k) + abs(j - l); flag = true; break; else flag = 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); 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; Assign(node_down, index);/向下扩展的节点 int dist_down = MAXDISTANCE; if (x 0) Swap(node_left.digitxy, node_left.digitxy - 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; Assign(node_right, index);/向右扩展的节点 int dist_right = MAXDISTANCE; if (y 2) Swap(node_right.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 source: endl; for (int 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; node_v.push_back(src);/在容器的尾部加一个数据 cout Search. endl; clock_t start = clock(); while (1) if (isEmptyOfOPEN() cout Cannt solve this statement! endl; return -1; else int loc; / the location of the minimize node最优节点的位置 loc = GetMinNode(); if(isEqual(loc, dest.digit) vector rstep_v; cout Source: endl; cout src endl; PrintSteps(loc, rstep_v); cout Successful! endl; cout Using (clock() - start) / CLOCKS_PER_SEC seconds. endl; break; else ProcessNode(loc); return 0;