题目2：隐式图的搜索问题（A*算法解决八数码）代码实现

从起点 开始，把它加入到一个由方格组成的open list(开放列表) 中，这个open list像是一个购物清单。Open list里的格子是可能会是沿途经过的，也有可能不经过。因此可以将其看成一个待检查的列表。查看与相邻的8个方格 ，把其中可走的 (walkable) 或可到达的(reachable) 方格加入到open list中。并把起点 设置为这些方格的父节点 (parent node) 。然后把 起点 从open list中移除，加入到close list(封闭列表) 中，close list中的每个方格都是不需要再关注的。

需要从open list中选一个与起点相邻的方格。但是到底选择哪个方格好呢？选F值（F(n) = G + H 。G代表的是从初始位置A沿着已生成的路径到指定待检测格子的移动开销。H指定待测格子到目标节点B的估计移动开销。H采用的是传统的曼哈顿距离（Manhattan Distance），也就是横纵向走的距离之和，并且忽略沿途的障碍。）最小的那个。

比较open list中节点的F值后，发现起点右侧节点的F=40，值最小。选作当前处理节点，并将这个点从Open List删除，移到Close List中。

对这个节点周围的8个格子进行判断，若是不可通过（比如墙，水，或是其他非法地形）或已经在Close List中，则忽略。否则执行以下步骤：

（1）若当前处理节点的相邻格子已经在Open List中，则检查这条路径是否更优，即计算经由当前处理节点到达那个方格是否具有更小的 G值。如果没有，不做任何操作。相反，如果G值更小，则把那个方格的父节点设为当前处理节点 ( 我们选中的方格 ) ，然后重新计算那个方格的 F 值和 G 值。（2）若当前处理节点的相邻格子不在Open List中，那么把它加入，并将它的父节点设置为该节点。

算法思想：

定义open表和close表，其中open表是用来存储待查验的节点，而close表是用来存储已查验过的节点（不需要再关注的节点）

把开始节点加入open表；

将开始节点拓展的子节点加入open表，将开始节点加入到close表；

将open表中的节点的耗散值也就是f进行从小到大的排序，此时open表中的第一个节点的耗散值最小，对open表中的第一个节点进行判断，如果这个节点是目标节点，则算法结束，无需进行以下步骤；反之，如果这个节点不是目标节点，则将这个节点进行扩展，再进行下一步；

判断n的可扩展节点（相邻节点）m，情况一：如果m在open表中，则说明初始节点到m节点出现了两条路径，此时需要判断这两条路径的耗散值的大小如果是新路径的耗散值小，则需要更改m节点的父节点，并将open表中的原的m节点加入close表，将现在的m节点加入open表，如果是新路径的耗散值大，则不需要进行任何操作；情况二：如果m在close表中，则说明初始节点该节点到m节点有两条路径，如果是新路径的耗散值大，则不需要进行任何操作如果是新路径的耗散值小，需要将更改m节点的父节点，并将m节点从close表中取出，并放入open表中；情况三：m节点既不在open表中也不在close表中，直接将m节点加入到open表中即可；

重复第4步，（算法结束的两种情况，其一，当前节点就是目标节点，即找到
了最优解；其二，open表为空，既无法找到到目标节点的路径，即无解。）

代码实现

#include <iostream> #include <time.h> using namespace std;/* 定义结构体 */ struct EightNum { //存储八数码int status[9];//存储走的是第几步(层数)int G;//存储不在位的格数(作为我们的启发式函数）int H;//存储估价函数的值int F;//存储0数码的位置int Zero;//存储操作符（1左2右3上4下）int step;//父指针EightNum* Parent; };#define MAXLISTSIZE 10000 #define MAXSTEPSIZE 100 //声明最终状态 int FinalStatus[9]; //定义OPEN表和CLOSE表,open和close是表中最后一个内容的下一位序号 EightNum OPEN[MAXLISTSIZE]; EightNum CLOSE[MAXLISTSIZE]; int open = 0; int close = 0;EightNum* Node;/* 计算不在位的字格数H 返回 H */ int CountH(int* status) {int H = 0;int i;for (i = 0; i <= 8; i++){if (FinalStatus[i] != status[i]){H++;}}return H; }/* 判断新生成的节点是否已经存在于OPEN表或CLOSE表中 返回 表征是否存在于OPEN或CLOSE的值，值为0 均不在，值>0 只在OPEN表，值<0 只在CLOSE表，|值|-1表示所在列表中的位置 */ int Exist(EightNum* N) {int i, j;//计算不在位的字格数，如果为0，则证明给函数的节点在表中已存在int H = 0;int status[9];Node = new EightNum;Node = N;for (i = 0; i <= 8; i++){status[i] = Node->status[i];}//判断是否在OPEN表for (i = 0; i <= open - 1; i++){for (j = 0; j <= 8; j++){if (status[j] != OPEN[i].status[j]){H++;}}//H=0证明在表中找到该节点if (H == 0){//如果在OPEN表中，返回i（节点在OPEN的位置）+ 1（在OPEN找到该节点）return i + 1;}//扫描完一个节点后重置HH = 0;}//判断是否在CLOSE表for (i = 0; i <= close - 1; i++){for (j = 0; j <= 8; j++){if (status[j] != CLOSE[i].status[j]){H++;}}//H=0证明在表中找到该节点if (H == 0){//如果在CLOSE表中，返回-i（i为节点在CLOSE的位置）- 1（在CLOSE找到该节点）return (-i) - 1;}//扫描完一个节点后重置HH = 0;}return 0; }/* 初始化节点 返回 初始化后的节点Node */ EightNum* EightNumInit(int status[10], int zero, int g, EightNum* parent, int step) {int i;Node = new EightNum;for (i = 0; i <= 8; i++){Node->status[i] = status[i];}Node->Zero = zero;Node->G = g;Node->H = CountH(Node->status);Node->F = Node->G + Node->H;Node->Parent = parent;Node->step = step;return Node; }/* 左移后的变化 返回 左移后的状态 */ int* Left(int* s, int z) {int temp, i;static int status[9];for (i = 0; i <= 8; i++){status[i] = s[i];}//左移则是下标减1，需要与前一个位置进行值的交换temp = status[z - 1];status[z - 1] = 0;status[z] = temp;return status; }/* 右移后的变化 返回 右移后的状态 */ int* Right(int* s, int z) {int temp, i;static int status[9];for (i = 0; i <= 8; i++){status[i] = s[i];}temp = status[z + 1];status[z + 1] = 0;status[z] = temp;return status; }/* 上移后的变化 返回 上移后的状态 */ int* Up(int* s, int z) {int temp, i;static int status[9];for (i = 0; i <= 8; i++){status[i] = s[i];}temp = status[z - 3];status[z - 3] = 0;status[z] = temp;return status; }/* 下移后的变化 返回 下移后的状态 */ int* Down(int* s, int z) {int temp, i;static int status[9];for (i = 0; i <= 8; i++){status[i] = s[i];}temp = status[z + 3];status[z + 3] = 0;status[z] = temp;return status; }/* 判断子节点是否在OPEN或CLOSE中，并进行对应的操作 返回值 NULL */ void ExistAndOperate(EightNum* N) {int i;//定义表示新生成节点是否在OPEN表或CLOSE表中, 值为0 均不在，值>0 只在OPEN表，值<0 只在CLOSE表int inList;Node = new EightNum;Node = N;//如果是第一步的节点，直接加入OPEN中，返回if (Node->G == 1){OPEN[open] = *Node;open++;return;}//判断新节点是否在OPEN或CLOSE中inList = Exist(Node);//如果均不在两个表中，将节点加入OPEN表中if (inList == 0){//将拓展出的新结点加入到OPEN表中OPEN[open] = *Node;open++;}//如果在OPEN中，说明从初始节点到该节点找到了不同路径，保留耗散值短的那条路径else if (inList > 0){//如果表内节点F值大于新节点F值，用新节点代替表内节点if (OPEN[inList - 1].F > Node->F){OPEN[inList - 1] = *Node;}}//如果在CLOSE中，说明初始节点到该节点有两条路径，如果新找到的路径耗散值大，什么都不做，如果较小，将其从CLOSE中取出放入OPEN中 else if (inList < 0){inList = -inList;//如果较小if (CLOSE[inList - 1].F > Node->F){//将其取出放入OPENOPEN[open] = *Node;open++;}//将其在CLOSE中释放for (i = inList - 1; i <= close - 1; i++){CLOSE[i] = CLOSE[i + 1];}close--;} }/* 寻找最佳路径函数 返回 最后的节点Node */ EightNum* Search() {int* status;int i, j;EightNum* Temp;//一直循环知道找到解结束while (1){Temp = new EightNum;//用冒泡排序给OPEN表里面的节点按耗散值进行排序for (i = open - 1; i > 0; i--){for (j = 0; j < i; j++){//从小到大进行排序if (OPEN[j].F > OPEN[j + 1].F){//交换值*Temp = OPEN[j + 1];OPEN[j + 1] = OPEN[j];OPEN[j] = *Temp;}}}Node = new EightNum;//从OPEN表中取出第一个元素（F值最小）*Node = OPEN[0];//判断该节点是否是目标节点，若是，则不在位的格数为0，算法结束，若不是，则将该结点进行扩展if (!CountH(Node->status)){break;}Temp = Node;//将扩展过的节点放入CLOSE CLOSE[close] = *Node;close++;//将扩展的节点从OPEN中释放for (i = 0; i <= open - 1; i++){//相当于是出栈OPEN[i] = OPEN[i + 1];}open--;//如果能左移，则进行左移创造新结点，下标为0，3，6则不能进行左移if ((Temp->Zero) % 3 >= 1){//创造新结点Node = new EightNum;//得到新的状态status = Left(Temp->status, Temp->Zero);//初始化新结点Node = EightNumInit(status, Temp->Zero - 1, (Temp->G) + 1, Temp, 1);//判断子节点是否在OPEN或CLOSE中，并进行对应的操作ExistAndOperate(Node);}//如果能右移，则进行右移创造新结点 ，下标为2，5，8则不能if ((Temp->Zero) % 3 <= 1){ //创造新结点Node = new EightNum;//得到新的状态status = Right(Temp->status, Temp->Zero);//初始化新结点Node = EightNumInit(status, Temp->Zero + 1, (Temp->G) + 1, Temp, 2);//判断子节点是否在OPEN或CLOSE中，并进行对应的操作ExistAndOperate(Node);}//如果能上移，则进行上移创造新结点 ，下标为0，1，2则不可以if (Temp->Zero >= 3){Node = new EightNum;//得到新的状态status = Up(Temp->status, Temp->Zero);//初始化新结点Node = EightNumInit(status, Temp->Zero - 3, (Temp->G) + 1, Temp, 3);//判断子节点是否在OPEN或CLOSE中，并进行对应的操作ExistAndOperate(Node);}//如果能下移，则进行下移创造新结点 ，下标为6，7，8则不可以if (Temp->Zero <= 5){Node = new EightNum; //创造新结点status = Down(Temp->status, Temp->Zero); //得到新的状态Node = EightNumInit(status, Temp->Zero + 3, (Temp->G) + 1, Temp, 4); //初始化新结点ExistAndOperate(Node); //判断子节点是否在OPEN或CLOSE中，并进行对应的操作}//如果open=0， 证明算法失败， 没有解if (open == 0)return NULL;}return Node; }/* 展示具体步骤 返回 NULL */ void ShowStep(EightNum* Node) {int STEP[MAXSTEPSIZE];int STATUS[MAXSTEPSIZE][9];int step = 0;int i, j;int totalStep = Node->G;while (Node){STEP[step] = Node->step;for (i = 0; i <= 8; i++){STATUS[step][i] = Node->status[i];}step++;Node = Node->Parent;}cout << "----------------------" << endl;cout << "总步数：" << totalStep << endl;cout << "----------------------" << endl;for (i = step - 1; i >= 0; i--){if (STEP[i] == 1)cout << "向左走一步" << endl;else if (STEP[i] == 2)cout << "向右走一步" << endl;else if (STEP[i] == 3)cout << "向上走一步" << endl;else if (STEP[i] == 4)cout << "向下走一步" << endl;else if (STEP[i] == 0)cout << "开始：" << endl;for (j = 0; j <= 8; j++){cout << STATUS[i][j] << " ";//换行输出if (j == 2 || j == 5 || j == 8)cout << endl;}cout << "----------------------" << endl;} } /* 主函数 */ int main() {int fstatus[9];int i, beginTime, endTime;EightNum* FNode;EightNum* EndNode;//输入初始状态cout << "请输入初始状态：" << endl;for (i = 0; i <= 8; i++){cin >> fstatus[i];}cout << endl;//输入最终状态cout << "请输入最终状态：" << endl;for (i = 0; i <= 8; i++){cin >> FinalStatus[i];}beginTime = clock();//判断0数码的位置for (i = 0; i <= 8; i++){if (fstatus[i] == 0)break;}//获得初始节点FNode = EightNumInit(fstatus, i, 0, NULL, 0);//将初始节点放入OPEN中OPEN[open] = *FNode;open++;//寻找最佳路径EndNode = Search();if (!EndNode)cout << "无解" << endl;elseShowStep(EndNode); //展示步骤endTime = clock();cout << "Run Time:" << endTime - beginTime << "ms" << endl;return 0; }

总结

以上是生活随笔为你收集整理的题目2：隐式图的搜索问题（A*算法解决八数码）代码实现的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。