A*寻路算法的探寻与改良（三）
by:田宇轩
第三分：这部分内容基于树、查找算法等对A*算法的执行效率进行了改良，想了解细化后的A*算法和变种A*算法内容的朋友们可以跳过这部分并阅读稍后更新的其他内容
3.1 回顾
你可以点击这里回顾文章的第二部分。
在我的上一篇文章中，我们探讨了如何用编程实现A*算法，并给出了C语言的算法实现，这一章内容中我们主要研究如何提高A*算法的执行效率。抛开时间复杂度的复杂计算，我们大概可以知道，函数对数据的操作次数越少，达成目的越快，算法的效率也就越高。沿着这个思路，我们可以先从研究函数对存储结构做的操作频率和具体内容改造它们，使A*更高效。如果前两部分只是初学者的新手教程，那么从本章开始，我们进入了更难的部分。
3.2 分析A*函数的中代价高的操作
在A*中，我们把起点放入iter，然后就重复for循环，可见for循环中重复执行的函数对于A*算法性能的影响是非常重要的，我们就从这个Astar里的最外层for循环开始看，一个函数一个函数地分析出哪个部分可以如何提高A*算法的效率。
（一）首先我们分析的就是这个for循环的循环条件，这个循环的条件在每一次循环发生的时候都会进行判定。最外层的for循环里，我们只判定这么两项内容：
（1）开启列表是否为空。开启列表如果是空的，这就代表我们没有待处理的格子了，已经无路可走，因此开启列表一旦为空，A*算法也就不用执行了。但是看过上一篇文章的朋友应该记得，我们用一个有全局作用域的变量openListCount（引用代码内容用基佬紫色，下同）来记录开启列表里格子的个数，因此，这个判定就只是判定openListCount这个参数是否为0，这种判定很简单，因此不用优化。
（2）终点是否在关闭列表中。一旦终点在关闭列表之中，就说明我们已经找到了最优路径，并且把路径的最有一个格子——终点也进行了父节点标记的操作，这一操作之后，A*也不必继续下去了。回顾上一篇文章，我们是在关闭列表中逐一匹配里面格子的坐标是否和终点坐标相等，这其实是很麻烦的方法。那么，怎么检测终点是否在关闭列表中呢，这里有一个更好的思路：我们都知道起点是唯一一个G值为0的格子（起点距离自己的距离为0），相应的，终点也是唯一一个H值为0的格子。在求曼哈顿距离时，如果发现一个格子的H值为0，那么毫无疑问，这个格子就是终点。我们可以用一个标记（类似process_control.h里面的参数flag一样）来使主循环停止而不用一一匹配新格子与关闭列表。
（二）主循环分析完了，我们来看看迭代器进入循环体内部发生的事情。之后首先发生的事情，是一个查找操作，开启列表中F值最小的（之一）会被找出来并设为当前格。然后是一个把当前格放入关闭列表的操作。先分析这两步操作：
（1）查找开启列表中的最小值。之前这一步操作中我们用的是冒泡排序的一层循环，把它们中最小的数（之一）沉到底，但是这种查找方法显然并不快，开启列表是在稍后的迭代操作中一步一步建立起来的，因此我们每次把东西加入开启列表可以按照最小二叉堆的添加操作做，这样数组的最后一个元素自然就是开启列表中最大的元素（之一）了。
（2）往开启列表中插入新的元素。开启列表是最小二叉堆，因此插入元素要根据最小二叉堆的性质。
（3）删除开启列表中最小的元素。开启列表是最小二叉堆，因此删除元素要根据最小二叉堆的性质。
（4）删除开启列表中指定的元素。开启列表中元素的f值可能会随着重新计算NewG的值而改变，因此我们会先删除指定的元素。这个过程可以有很多种方式实现，这里，我的例子选择完全重新排序开启列表，其实不是很有效率。
（5）把当前元素加入关闭列表，用方便查找的方式构建关闭列表使其易于查找。
（6）搜索关闭列表，配合关闭列表结构提高效率。
因此，我们可以总结出7条可以优化的操作（函数）：
（1）void putInOpenList(struct baseNode inList),把一个元素插入开启列表中。开启列表主要是插入删除，因此用最小二叉堆就好了，每次都出队列最小的数字，改进后要求格子按照最小二叉堆的性质进行插入操作。
（2）struct baseNode readTopOpenList()，取出开启列表中最小的数字。改进后这个函数根据最小二叉堆的性质直接获取列表顶部格子即可。
（3）void putInCloseList(struct baseNode temp)，当前点加入到关闭列表中。关闭列表只有插入和搜索操作，为了方便检索，可以按照二叉排序树、AVL树或者红黑树的性质做一个关闭列表的操作（然而我并不会红黑树，（逃（哔站粉用于标记吐槽和没什么卵用的内心独白，下同），等我学完红黑树就回来补完这个~QwQ），这里，为了简单（其实只是自己水平有限），做一个方便查找的普通排序列表配合折半查找好了。
（4）void outOpenList(struct baseNode iter），把开启列表中的当前节点删除。既然开启列表是最小二叉堆，删除也要按照这个性质来。
（5）void outopenlist2(struct baseNode iter), 重新排序最小二叉堆，并删除指定的点。
（6）int isInCloseList(struct baseNode temp)，查看指定的temp在不在关闭列表中的函数，用折半查找提高效率就好了。
（7）int manhatten(int i, int j)，求曼哈顿函数的值，当值为零，赶紧立一个flag，让主循环停止。
OpenList和CloseList的存储结构也随着新设计的数据结构改变就好，明确了这些重点，剩下的活只要实现这些函数，然后把函数覆盖原来的函数（位于func.h中）就好。
3.3 实现7条优化
下面的内容就是这些函数的具体实现。
3.3.1 优化终点在不在关闭列表的判定
首先，我们对比较简单的（7）int manhatten(int i, int j)，进行改造如下：
//A*中的启发式函数，用于求指定位置和终点之间的曼哈顿距离
int manhatten(int i, int j)
{
int a= (abs(AsceneryList[].node.i - i) + abs(AsceneryList[].node.j - j));
if (a==)
{
FLAG = ;
} return a*;
}
代码3.3.1.1——改造后的manhatten
这里，我们在data.h里定义一个全局变量，int FLAG=0;,这个FLAG初值为0，每当Astar执行中发现某个格子曼哈顿距离为0,相应地，就把这个FLAG的值改为1，然后Astar内最外层for循环判定条件发现FLAG等于1，就意味着终点已经在关闭列表内，可以松口气了（以前是遍历关闭列表找终点在不在里面，这显然是一步优化）。但是相应地，改变Astar最外层for语句为for (; openListCount != 0 && FLAG==0;)。
同时别忘了每次执行Astar前都重置FLAG值为1，只需在Astar函数内开始加上一句FLAG=0;。
3.3.2 优化开启列表
函数（1）（2）（4）（5）都和开启列表有关，分别对应着开启列表的添加元素，最小值出队列，删除元素和搜索，我们这里再处理他们，改为下面这样的函数：
//把一个元素插入开启列表中/////////
void putInOpenList(struct baseNode inList)
{
++openListCount; OpenList[openListCount - ] = inList;
for (int i = openListCount - ; i >; i=(i-)/)
{
if (OpenList[i].f<OpenList[(i-)/].f)
{
OpenList[i]=OpenList[(i - ) / ];
OpenList[(i - ) / ] = inList;
}
else
{
break;
}
}
} //取出开启列表中最小的数
struct baseNode readTopOpenList()
{
return OpenList[];
} //把开启列表中的当前节点删除
void outOpenList()
{
--openListCount; OpenList[]=OpenList[openListCount];
struct baseNode temp; for (int i = ,p=; *i+<openListCount;i=p)
{
if (*i+>openListCount-)
{
p = * i + ;
}
else
{
if (OpenList[ * i + ].f<OpenList[ * i + ].f)
{
p = * i + ;
}
else
{
p = * i + ;
}
} if (OpenList[p].f<OpenList[i].f)
{
temp=OpenList[p];
OpenList[p]=OpenList[i];
OpenList[i] = temp;
}
else
{
break;
}
}
} //删除开启列表中指定的元素，重构最小二叉堆
//（注：这个可以用很多方法实现，示例并非最优）
void outOpenList2(struct baseNode iter)
{
int number=openListCount-;
struct baseNode openlist2[MAX_number*MAX_number];
for (int i = ; i < openListCount; ++i)
{
if (OpenList[i].i==iter.i&&OpenList[i].j==iter.j)
{
continue;
}
openlist2[i]=OpenList[i];
} openListCount = ;
for (int i = ; i < number; ++i)
{
putInOpenList(openlist2[i]);
}
}
代码3.2.2.1——优化开启列表
3.3.3 优化关闭列表
关闭列表中的元素是只进不出的，因此这里用简单的排序+折半查找优化效率，注意：对于关闭列表中的排序，应该用唯一值做key方便折半查找，这里，唯一key被设置成为格子的i坐标乘地图边的最大值加上格子的j坐标：
//把一个元素加入关闭列表中
void putInCloseList(struct baseNode temp)
{
CloseList[closeListCount] = temp; struct baseNode iter;
for (int i = closeListCount; i>; --i)
{
if ((CloseList[i].i*MAX_number+CloseList[i].j+)<(CloseList[i-].i*MAX_number + CloseList[i-].j + ))
{
iter = CloseList[i];
CloseList[i]=CloseList[i - ];
CloseList[i - ] = iter;
}
else
{
break;
}
}
++closeListCount;
} //查看指定的temp在不在关闭列表中的函数
int isInCloseList(struct baseNode temp)
{
int low = , high = closeListCount - , mid = (low + high) / ; for (; low<=high; mid = (low + high) / )
{
if ((CloseList[mid].i*MAX_number + CloseList[mid].j + )==(temp.i*MAX_number + temp.j + ))
{
return ;
}
else if((CloseList[mid].i*MAX_number + CloseList[mid].j + ) > (temp.i*MAX_number + temp.j + ))
{
high = mid - ;
}
else
{
low = mid + ;
}
}
return ;
}
代码3.3.3.1——优化关闭列表
这里要说明一下思路，我们为了使关闭列表方便查找，使用了插入新元素时排序关闭列表的方式，排序依赖的值应该类似主码，是格子唯一的标记，格子存储在二维数组中，唯一标记显然是格子的坐标，不过坐标是两个值，我们不想弄一个结构体储存格子的key，所以就采用哈希表的思路把格子的横纵坐标转换为一个唯一值，那就是一个格子在二维列表的次序（这个格子在二维列表中是第几个格子）。
3.3 回顾
这样所有的函数就优化完了，这组优化只改动了func.h和data.h，现在我们把改进后的这两个文件重新贴在下方（默认折叠），如果大家在自己按照这种思路写A*遇到困难，可以参考以下内容：
#pragma once #define MAX_number 5 //一个比较基础的结构体，用于和地图联动
struct baseNode
{
int i;
int j;
int weigt; int f;
int g;
int h; struct baseNode *father;
}; //定义了一个全局变量用来存储二维矩阵地图
struct baseNode map[MAX_number][MAX_number]; //用于记录景点的数组元素
struct scenerySpotsList
{
struct baseNode node;
char placeName[];
}; //邻居列表，用于记录每个当前点的所有邻居
struct baseNode Neibo[]; //记录景点，起点和终点的数组
struct scenerySpotsList AsceneryList[MAX_number*MAX_number]; //开启列表，用于A*算法
struct baseNode OpenList[MAX_number*MAX_number]; //关闭列表，用于A*算法
struct baseNode CloseList[MAX_number*MAX_number]; //用于记录现在的景点个数，第1个景点记录在AsceneryList【2】里，AsceneryList【0】和AsceneryList【1】分别用来记录起点和终点
int sceneryCount = ; //用于记录开启列表中元素的个数
int openListCount = ; //用于记录关闭列表中元素的个数
int closeListCount = ; //用于记录邻居的个数
int neibNum = ; //用来储存整理后的路径
struct baseNode Astack[MAX_number*MAX_number]; //用来记录路径经过的点的个数
int AstackCount = ; //用于记录关闭列表里是否有终点
int FLAG = ;
data.h
#pragma once #include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include "data_define.h" //设定地图的函数
void inputmap()
{
printf("目前地图大小为%d * %d。\n",MAX_number,MAX_number);
printf("请通过输入整数的形式填充地图，0代表地形不可通过，\n其他正整数代表权值，权值越大，地形越不方便通过\n\n"); for (int i = ; i <MAX_number; ++i)
{
for (int j = ; j < MAX_number; ++j)
{
scanf("%d", &map[i][j].weigt); map[i][j].i = i;
map[i][j].j = j;
}
printf("第%d行输入完毕,共%d行\n\n",i+,MAX_number);
}
} //设定校园景点的函数
void setView()
{
for (; ; )
{
int inputI = ;
int inputJ = ;
char inputS[]; printf("请输入景点的名称，输入done结束景点录入\n");
scanf("%s", inputS); if (strcmp(inputS,"done")==)
{
printf("结束输入:\n");
break;
}
else
{
strcpy(AsceneryList[sceneryCount].placeName,inputS); printf("地图坐标从【1，1】开始\n");
printf("请输入景点的横坐标:\n");
scanf("%d", &inputI);
AsceneryList[sceneryCount].node.i = inputI-; printf("请输入景点的纵坐标:\n");
scanf("%d", &inputJ);
AsceneryList[sceneryCount].node.j = inputJ-; printf("成功输入一个景点:\n");
++sceneryCount;
}
}
} //设定起点和终点的函数
void setRoad()
{
printf("你可以进行以下操作\n");
printf("1.寻找一个景点\n");
printf("2.手动设定起点终点坐标\n"); int user_input = ;
scanf("%d",&user_input); if (user_input==)
{
int i = ; char inputS[];
printf("请输入想查找的景点的名称:\n这个景点将作为起点\n");
scanf("%s", inputS); for (; i < sceneryCount; ++i)
{
if (strcmp(AsceneryList[i].placeName, inputS) == )
{
AsceneryList[].node.i = AsceneryList[i].node.i;
AsceneryList[].node.j = AsceneryList[i].node.j; i = ;
printf("成功把%s设置为起点\n",inputS);
break;
}
}
if (i != )
{
printf("找不到这个景点\n");
} int j = ; char inputM[];
printf("请输入想查找的景点的名称:\n这个景点将作为终点\n");
scanf("%s", inputM); for (; j < sceneryCount; ++j)
{
if (strcmp(AsceneryList[j].placeName, inputM) == )
{
AsceneryList[].node.i = AsceneryList[j].node.i;
AsceneryList[].node.j = AsceneryList[j].node.j; j = ;
printf("成功把%s设置为终点\n",inputM);
break;
}
}
if (j!=)
{
printf("找不到这个景点\n");
}
}
else if(user_input==)
{
int i = , j = , p = , q = ; printf("地图坐标从【1，1】开始\n");
printf("请输入起点的横坐标:\n");
scanf("%d", &i);
printf("请输入起点的纵坐标:\n");
scanf("%d", &j); AsceneryList[].node.i = i - ;
AsceneryList[].node.j = j - ; printf("请输入终点的横坐标:\n");
scanf("%d", &p);
printf("请输入终点的纵坐标:\n");
scanf("%d", &q); AsceneryList[].node.i = p - ;
AsceneryList[].node.j = q - ;
}
else
{
printf("输入错误\n");
}
} //以下函数都是A*算法的一部分/////////////////////////// //把一个元素插入开启列表中，使开启列表符合最小二叉堆的性质/////////
void putInOpenList(struct baseNode inList)
{
++openListCount; OpenList[openListCount - ] = inList;
for (int i = openListCount - ; i >; i=(i-)/)
{
if (OpenList[i].f<OpenList[(i-)/].f)
{
OpenList[i]=OpenList[(i - ) / ];
OpenList[(i - ) / ] = inList;
}
else
{
break;
}
}
} //取出开启列表（最小二叉堆）中最小的数
struct baseNode readTopOpenList()
{
return OpenList[];
} //把一个元素加入关闭列表中，使关闭列表有序
void putInCloseList(struct baseNode temp)
{
CloseList[closeListCount] = temp; struct baseNode iter;
for (int i = closeListCount; i>; --i)
{
if ((CloseList[i].i*MAX_number+CloseList[i].j+)<(CloseList[i-].i*MAX_number + CloseList[i-].j + ))
{
iter = CloseList[i];
CloseList[i]=CloseList[i - ];
CloseList[i - ] = iter;
}
else
{
break;
}
}
++closeListCount;
} //把开启列表中的当前节点删除，使其符合最小二叉堆的性质
void outOpenList()
{
--openListCount; OpenList[]=OpenList[openListCount];
struct baseNode temp; for (int i = ,p=; *i+<openListCount;i=p)
{
if (*i+>openListCount-)
{
p = * i + ;
}
else
{
if (OpenList[ * i + ].f<OpenList[ * i + ].f)
{
p = * i + ;
}
else
{
p = * i + ;
}
} if (OpenList[p].f<OpenList[i].f)
{
temp=OpenList[p];
OpenList[p]=OpenList[i];
OpenList[i] = temp;
}
else
{
break;
}
}
} //删除开启列表中指定的元素，重构最小二叉堆
//（注：这个可以用很多方法实现，示例并非最优）
void outOpenList2(struct baseNode iter)
{
int number=openListCount-;
struct baseNode openlist2[MAX_number*MAX_number];
for (int i = ; i < openListCount; ++i)
{
if (OpenList[i].i==iter.i&&OpenList[i].j==iter.j)
{
continue;
}
openlist2[i]=OpenList[i];
} openListCount = ;
for (int i = ; i < number; ++i)
{
putInOpenList(openlist2[i]);
}
} //对于一路上的每个点，分析它的最多八个邻居，并加入邻居列表
void addNeibo(struct baseNode iter)
{
neibNum = ; for (int i = iter.i - ; i <= iter.i + ; ++i)
{
for (int j = iter.j - ; j <= iter.j + ; ++j)
{
if (i >= && i <= MAX_number - && j >= && j <= MAX_number - )
{
if (i == iter.i&&j == iter.j)
{
}
else
{
map[i][j].h = manhatten(i, j); Neibo[neibNum] = map[i][j];
++neibNum;
}
}
}
}
} //查看临近格是否在开启列表中的函数
int isInOpenList(struct baseNode neibo)
{
for (int i = ; i < openListCount - ; ++i)
{
if (OpenList[i].i == neibo.i&&OpenList[i].j == neibo.j)
{
return ;
}
}
return ;
} //查看指定的temp在不在关闭列表中的函数，使用了折半查找
int isInCloseList(struct baseNode temp)
{
int low = , high = closeListCount - , mid = (low + high) / ; for (; low<=high; mid = (low + high) / )
{
if ((CloseList[mid].i*MAX_number + CloseList[mid].j + )==(temp.i*MAX_number + temp.j + ))
{
return ;
}
else if((CloseList[mid].i*MAX_number + CloseList[mid].j + ) > (temp.i*MAX_number + temp.j + ))
{
high = mid - ;
}
else
{
low = mid + ;
}
}
return ;
} //A*中的启发式函数，用于求指定位置和终点之间的曼哈顿距离
int manhatten(int i, int j)
{
int a= (abs(AsceneryList[].node.i - i) + abs(AsceneryList[].node.j - j));
if (a==)
{
FLAG = ;
} return a*;
} //求当前点与父亲节点的距离
int increment(struct baseNode this)
{
if ((abs(this.father->i-this.i)==) && (abs(this.father->j - this.j) == ))
{
return *this.weigt;
}
else if ((this.father->i - this.i) == && (this.father->j - this.j) == )
{
return ;
}
else
{
return *this.weigt;
}
} //求出用当前点作为父节点时这个点的G值
int NewG(struct baseNode this,struct baseNode father)
{
if (abs(father.i - this.i) == && abs(father.j - this.j) == )
{
return father.g+;
}
else if (abs(father.i - this.i) == && abs(father.j - this.j) == )
{
return father.g;
}
else
{
return father.g+;
}
} //把A*算法的节点按倒序整理到Astack里面
void arrange(struct baseNode iter)
{
AstackCount = ;
for (; ; iter=map[iter.father->i][iter.father->j])
{
Astack[AstackCount] = iter;
++AstackCount;
if (iter.i == AsceneryList[].node.i&&iter.j == AsceneryList[].node.j)
{
break;
}
}
} //打印出A*算法的路径矩阵
printAstar()
{
printf("A为最佳路径，Q为不经过区域\n\n");
int boole = ; for (int i = ; i < MAX_number; ++i)
{
for (int j = ; j < MAX_number; ++j)
{
for (int w=; w<AstackCount; ++w)
{
if (Astack[w].i==i&&Astack[w].j==j)
{
boole = ;
break;
}
} if (boole==)
{
printf("A ");
boole = ;
}
else
{
printf("Q ");
}
}
printf("\n");
}
} //Astar的本体
void Astar()
{
//FLAG用于判断终点是否在关闭列表
FLAG=;
//每次执行A*算法，都初始化开启/关闭列表
openListCount = ;
closeListCount = ; //创建一个迭代器,每次都等于f值最小的节点
struct baseNode iter; //让这个迭代器的初值为起点
iter.i = AsceneryList[].node.i;
iter.j = AsceneryList[].node.j;
iter.weigt = map[AsceneryList[].node.i][AsceneryList[].node.j].weigt; //起点的没有父节点，且为唯一G值为0的点
iter.g = ;
iter.h = manhatten(iter.i,iter.j);
iter.f = iter.g + iter.h; //创建终点
struct baseNode ender; ender.i = AsceneryList[].node.i;
ender.j = AsceneryList[].node.j; //把起点放入开启列表
putInOpenList(iter); //当开启列表为空或者终点在关闭列表中，结束寻径
for (; openListCount != && FLAG==;)
{
//取出开启列表中f值最小的节点（之一），并设为iter（当前点）
iter = readTopOpenList(); //把最小点从开启列表中删除
outOpenList(); //把当前点记录在关闭列表中
putInCloseList(iter); //把当前点的邻居加入邻居列表
addNeibo(iter); //对于每个邻居，分三种情况进行操作
for (int i = ; i < neibNum; ++i)
{
//如果这个邻居节点不可通过，或者这个邻居节点在关闭列表中，略过它
if (Neibo[i].weigt== || isInCloseList(Neibo[i]))
{
}
//如果这个邻居节点已经在开启列表中
else if(isInOpenList(Neibo[i]))
{
if (NewG(Neibo[i],iter)<Neibo[i].g)
{
map[Neibo[i].i][Neibo[i].j].father = &map[iter.i][iter.j];
map[Neibo[i].i][Neibo[i].j].g = map[iter.i][iter.j].g + increment(Neibo[i]);
map[Neibo[i].i][Neibo[i].j].f = map[Neibo[i].i][Neibo[i].j].g + map[Neibo[i].i][Neibo[i].j].h; outOpenList2(Neibo[i]);
putInOpenList(Neibo[i]);
}
}
//如果这个邻居节点不在开启列表中
else
{
map[Neibo[i].i][Neibo[i].j].father= Neibo[i].father = &map[iter.i][iter.j];
map[Neibo[i].i][Neibo[i].j].g = map[iter.i][iter.j].g + increment(Neibo[i]);
map[Neibo[i].i][Neibo[i].j].f = map[Neibo[i].i][Neibo[i].j].g + map[Neibo[i].i][Neibo[i].j].h; Neibo[i] = map[Neibo[i].i][Neibo[i].j];
putInOpenList(Neibo[i]);
}
}
} arrange(map[ender.i][ender.j]);
printAstar();
}
func.h
在下一章里，我们将尝试用其他的方式存储地图并且用新的方式写启发函数，敬请期待。