A*寻路算法的探寻与改良(三)

第三部分:这部分内容基于树、查找算法等对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),进行改造如下:
 1 //A*中的启发式函数,用于求指定位置和终点之间的曼哈顿距离
 2 int manhatten(int i, int j)
 3 {
 4     int a= (abs(AsceneryList[1].node.i - i) + abs(AsceneryList[1].node.j - j));
 5     if (a==0)
 6     {
 7         FLAG = 1;
 8     }
 9
10     return a*10;
11 }

代码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)都和开启列表有关,分别对应着开启列表的添加元素,最小值出队列,删除元素和搜索,我们这里再处理他们,改为下面这样的函数:
 1 //把一个元素插入开启列表中/////////
 2 void putInOpenList(struct baseNode inList)
 3 {
 4     ++openListCount;
 5
 6     OpenList[openListCount - 1] = inList;
 7     for (int i = openListCount - 1; i >0; i=(i-1)/2)
 8     {
 9         if (OpenList[i].f<OpenList[(i-1)/2].f)
10         {
11             OpenList[i]=OpenList[(i - 1) / 2];
12             OpenList[(i - 1) / 2] = inList;
13         }
14         else
15         {
16             break;
17         }
18     }
19 }
20
21 //取出开启列表中最小的数
22 struct baseNode readTopOpenList()
23 {
24     return OpenList[0];
25 }
26
27 //把开启列表中的当前节点删除
28 void outOpenList()
29 {
30     --openListCount;
31
32     OpenList[0]=OpenList[openListCount];
33     struct baseNode temp;
34
35     for (int i = 0,p=02*i+1<openListCount;i=p)
36     {
37         if (2*i+2>openListCount-1)
38         {
39             p = 2 * i + 1;
40         }
41         else
42         {
43             if (OpenList[2 * i + 1].f<OpenList[2 * i + 2].f)
44             {
45                 p = 2 * i + 1;
46             }
47             else
48             {
49                 p = 2 * i + 2;
50             }
51         }
52
53         if (OpenList[p].f<OpenList[i].f)
54         {
55             temp=OpenList[p];
56             OpenList[p]=OpenList[i];
57             OpenList[i] = temp;
58         }
59         else
60         {
61             break;
62         }
63     }
64 }
65
66 //删除开启列表中指定的元素,重构最小二叉堆
67 //(注:这个可以用很多方法实现,示例并非最优)
68 void outOpenList2(struct baseNode iter)
69 {
70     int number=openListCount-1;
71     struct baseNode openlist2[MAX_number*MAX_number];
72     for (int i = 0; i < openListCount; ++i)
73     {
74         if (OpenList[i].i==iter.i&&OpenList[i].j==iter.j)
75         {
76             continue;
77         }
78         openlist2[i]=OpenList[i];
79     }
80
81     openListCount = 0;
82     for (int i = 0; i < number; ++i)
83     {
84         putInOpenList(openlist2[i]);
85     }
86 }

代码3.2.2.1——优化开启列表

 3.3.3 优化关闭列表

 
       关闭列表中的元素是只进不出的,因此这里用简单的排序+折半查找优化效率,注意:对于关闭列表中的排序,应该用唯一值做key方便折半查找,这里,唯一key被设置成为格子的i坐标乘地图边的最大值加上格子的j坐标:
 1 //把一个元素加入关闭列表中
 2 void putInCloseList(struct baseNode temp)
 3 {
 4     CloseList[closeListCount] = temp;
 5
 6     struct baseNode iter;
 7     for (int i = closeListCount; i>0; --i)
 8     {
 9         if ((CloseList[i].i*MAX_number+CloseList[i].j+1)<(CloseList[i-1].i*MAX_number + CloseList[i-1].j + 1))
10         {
11             iter = CloseList[i];
12             CloseList[i]=CloseList[i - 1];
13             CloseList[i - 1] = iter;
14         }
15         else
16         {
17             break;
18         }
19     }
20     ++closeListCount;
21 }
22
23 //查看指定的temp在不在关闭列表中的函数
24 int isInCloseList(struct baseNode temp)
25 {
26     int low = 0, high = closeListCount - 1, mid = (low + high) / 2;
27
28     for (; low<=high; mid = (low + high) / 2)
29     {
30         if ((CloseList[mid].i*MAX_number + CloseList[mid].j + 1)==(temp.i*MAX_number + temp.j + 1))
31         {
32             return 1;
33         }
34         else if((CloseList[mid].i*MAX_number + CloseList[mid].j + 1) > (temp.i*MAX_number + temp.j + 1))
35         {
36             high = mid - 1;
37         }
38         else
39         {
40             low = mid + 1;
41         }
42     }
43     return 0;
44 }

代码3.3.3.1——优化关闭列表

      这里要说明一下思路,我们为了使关闭列表方便查找,使用了插入新元素时排序关闭列表的方式,排序依赖的值应该类似主码,是格子唯一的标记,格子存储在二维数组中,唯一标记显然是格子的坐标,不过坐标是两个值,我们不想弄一个结构体储存格子的key,所以就采用哈希表的思路把格子的横纵坐标转换为一个唯一值,那就是一个格子在二维列表的次序(这个格子在二维列表中是第几个格子)。这样所有的函数就优化完了。

 

原文链接:,转发请注明来源!

发表评论

要发表评论,您必须先登录