Astar算法实现象棋中马的寻路问题

1. 环境与配置

   编程语言：C语言
   操作系统：Ubuntu 20.10
   编译器：vs code

2. 具体分析

   • 问题说明：给定任意大小棋盘，以及任意初始位置和目标位置，以象棋中马的行动规则，计算从初始位置到目标位置所需的最短步数。
   • Astar算法作为启发式搜索的重要算法，不同于深度优先、宽度优先等盲目搜索算法，通过对open表中各个节点估价函数的计算并排序（不同图搜索算法的根本区别），从而逐步靠近目标值。估价函数f(x) = g(x) + h(x)，g(x)为当前节点已消耗的代价，h(x)为当前节点到达目标剩余的代价，一般用h*(x)估计值进行估计h(x)。具体算法内容可自行百度。
   • 在该问题中，g(x)为节点x走到当前位置的最短步数，h(x)为节点x当前位置与目标位置的的距离
   • open表和close表可使用双向链表构建
     

3. 算法实现

#include 
#include 
#include //定义双向链表
typedef struct Node{int y;int x;int step; // g(x)，当前步数int distance; // h(x)，剩余距离struct Node *next;struct Node *last;
}node;int map_x, map_y; // 地图大小
node *open, *close; //open表和close表//回收表中的资源
int recycle(node *list){node *remain;list = list->next;while(list->next != NULL){remain = list->next;free(list);list = remain;}return 0;
}//将res插入表中des的后方
int in_list(node *des, node *res){res->last = des;res->next = des->next;des->next->last = res;des->next = res;return 0;
}//将res移出原有位置
int out_list(node *res){res->last->next = res->next;res->next->last = res->last;res->last = NULL;res->next = NULL;return 0;
}//将res插入open表，并排序！
int in_open_list(node *res, node *open){node *cur = open->next;if(cur->next == NULL)in_list(cur->last, res);while(cur->next != NULL){if(res->distance + res->step < cur->distance + cur->step){in_list(cur->last, res);return 0;}else if(cur->next->next == NULL){in_list(cur, res);return 0;}cur = cur->next;}
}//判断节点合法性，并插入节点
int insert_node(node n, node des, int add_x, int add_y){int x = n.x + add_x;int y = n.y + add_y;int dst = (int)sqrt(pow(x - des.x, 2) + pow(y - des.y, 2));if(x > 0 && x <= map_x && y > 0 && y <= map_y){node *cur;node *new = (node *)malloc(sizeof(struct Node));*new = (node){.x = x, .y = y, .step = n.step + 1, .distance = dst};//判断close表中是否存在相同位置的节点cur = close->next;while(cur->next != NULL){if(cur->x == new->x && cur->y == new->y){if(cur->step + cur->distance > new->step + new->distance){out_list(cur);in_open_list(new, open);free(cur);return 1;}else{free(new);return 0;}}cur = cur->next;}//判断open表中是否存在相同位置的节点cur = open->next;while(cur->next != NULL){if(cur->x == new->x && cur->y == new->y){if(cur->step + cur->distance > new->step + new->distance){out_list(cur);in_open_list(new, open);free(cur);return 1;}else{free(new);return 0;}}cur = cur->next;}in_open_list(new, open);return 1;}return 0;
}int Astar(node *loc, node *des){//创建表头表尾node open_head = {.next = NULL, .last = NULL};node open_tail = {.next = NULL, .last = NULL};node close_head = {.next = NULL, .last = NULL};node close_tail = {.next = NULL, .last = NULL};//连接open表、close表open = &open_head;open->next = &open_tail;open_tail.last = &open_head;close = &close_head;close->next = &close_tail;close_tail.last = &close_head;in_list(open, loc);while(open->next->next != NULL){node *n = open->next;out_list(open->next);in_list(close, n);//当前节点为所求if(n->x == des->x && n->y == des->y){free(des);recycle(open);recycle(close);return n->step;}//马儿🏇跳八方，该函数后两个参数确定棋子的运动规则insert_node(*n, *des, 2, 1);insert_node(*n, *des, 2,-1);insert_node(*n, *des, 1,-2); insert_node(*n, *des,-1,-2); insert_node(*n, *des,-2,-1); insert_node(*n, *des,-2, 1); insert_node(*n, *des,-1, 2); insert_node(*n, *des, 1, 2);     }free(des);recycle(close);return -1;
}int main(int argc, char const *argv[])
{int loc_x, loc_y;int des_x, des_y;int step = -1;int dst = 0;node *loc, *des;printf("please input the length and width of chessboard: ");scanf("%d %d", &map_x, &map_y);printf("please input the location of the chess: ");scanf("%d %d", &loc_x, &loc_y);printf("please input the destination of the chess: ");scanf("%d %d", &des_x, &des_y);dst = (int)sqrt(pow(loc_x - des_x, 2) + pow(loc_y - des_y, 2));loc = (node *)malloc(sizeof(node));des = (node *)malloc(sizeof(node));*loc = (node){.x = loc_x, .y = loc_y, .step = 0, .distance = dst};*des = (node){.x = des_x, .y = des_y};if((step = Astar(loc, des)) != -1){printf("the least step is : %d\n", step);}else{fprintf(stderr, "no route founded!\n");}return 0;
}

4. 简单说明：

   • 函数的编译命令为：gcc test.c -o test -lm ，由于使用了math头文件，因此需要-lm参数去链接头文件
   • 函数in_open_list在插入节点n时，会根据估价函数进行排序操作，这也是Astar算法的核心
   • 回收资源时要格外注意：
     • 重复节点，在函数insert_node中判断完估价函数大小后，较差的节点会从表中移除，并释放内存
     • 在找到目标节点或无访问路径时，未释放的内存包括open表，close表，des节点(loc节点在开始时已加入open表中，可跟随open表一同释放内存)。open表和close表可使用recycle函数释放内存。
   • 按照提示，先后输入地图大小，初始位置，目标位置，各参量用空白符号隔开。没有做专门的输入判断。

5. 在写程序时遇到的一些问题

   在处理链表时，新创建的节点一定要使用malloc函数申请内存，而不要直接使用struct结构创建
   接下来进行详细说明

   #include 
   #include typedef struct Node{int y;int x;int step; // g(x)int distance; // h(x)struct Node *next;struct Node *last;
   }node;int main(int argc, char const *argv[])
   {for(int i = 0;i < 3;i++)ma();printf("---------------\n");ba();
   }
   

   函数ma()和ba()的不同定义，以及相应结果如下：

   1. ma()函数：

      • 直接构造struct结构

      void ma(){node n = {.x = 1, .y = 1};printf("%p\n", &n);
      }
      

      main函数中的ma函数输出结果为：

      0x7fffffffdd50
      0x7fffffffdd50
      0x7fffffffdd50
      

      几次调用ma()函数创建的node结构的地址相同

      2. 使用malloc函数构造，不使用free函数释放内存

      void ma(){node *m = (node *)malloc(sizeof(struct Node));printf("%p\n", m);
      }
      

      main函数中的ma函数输出结果为：

      0x5555555592a0
      0x5555555596e0
      0x555555559710
      

      几次调用ma()函数创将的node结构地址不同

      3. 使用malloc函数构造，使用free函数释放内存

      void ma(){node *m = (node *)malloc(sizeof(struct Node));printf("%p\n", m);free(m);
      }
      

      main函数中的ma函数输出结果为：

      0x5555555592a0
      0x5555555592a0
      0x5555555592a0
      

      几次调用ma()函数创建的node结构的地址相同

   2. ba()函数

      • 直接构造struct结构

      void ba(){for(int i = 0;i < 3;i++){node n;printf("%p\n", &n);}
      }
      

      main函数中的ba函数输出结果为：

      0x7fffffffdd50
      0x7fffffffdd50
      0x7fffffffdd50
      

      2. 使用malloc函数构造，不使用free函数释放内存

         void ba(){for(int i = 0;i < 3;i++){node *m = (node *)malloc(sizeof(struct Node));printf("%p\n", m);}
         }
         

         main函数中的ba函数输出结果为：

          	0x5555555592a00x5555555596e00x555555559710
         

         几次调用ba()函数创将的node结构地址不同

         3. 使用malloc函数构造，使用free函数释放内存

         void ba(){for(int i = 0;i < 3;i++){node *m = (node *)malloc(sizeof(struct Node));printf("%p\n", m);free(m);}
         }
         

         main函数中的ba函数输出结果为：

         0x5555555592a0
         0x5555555592a0
         0x5555555592a0
         

         几次调用ba()函数创建的node结构的地址相同

块变量作为auto变量，在块外一般被回收，重新调用函数时分配的内存依旧是同一块内存，这就带来了问题
使用struct构造变量，节点插入链表后退出函数。重新调用函数，申请的依旧是同一块内存，本次创建的节点地址和上一次完全相同，处理的依旧是同一个节点。

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！