前面提到过迪杰斯特拉算法,它的原理简述如下:
1.将所有的点放在B集合。(起点距离为0,其他点为无穷大)
2.从B集合找出距离最小的点,取走并放在A集合。
3.根据A集合的新加入的点,对B集合中的邻点进行距离更新。然后转到2。
4.直至终点加入到A集合表示找到,或B集合无最小值全部为无穷大,表示无法找到。
(B集合可以理解为所有待确认的点,其中有的已赋值,有的未赋值,也可以理解为已赋值的为集合B,未赋值的不属于任何集合。建议前者,这样不需要加入队列这一步骤,只对邻点赋值即可)
可知Dijkstra算法总是先找到实际距离最小的点,即使它离终点很远或根本不连通,直至终点从B集合中优先弹出。
而A*算法是一种启发式算法,算法依赖启发函数h(n),原理与Dijkstra算法步骤类似,区别是
1.引入了f(n)=g(n)+h(n)的概念,从B集合中找出的不是实际距离最小,而是估算距离最小的点。
2.终点的实际距离被赋值即表示找到,并不需要终点被优先队列弹出。
3.A*花费时间少,但不一定找到的是最优解,Dijkstra保证找到最优解,但花费时间长。
g(n)是起点到当前点的实际距离,h(n)是当前点到终点的估计距离。f(n)为两者的和。这相当于在Dijkstra的寻路算法中加入了导航功能。
这使得A*算法会更高效,导向性更强。而h(n)决定了算法的导向性高低。
h(n)=0时,表示无导向性,等同于Dijkstra算法。h(n)越大则导向性越强,寻路完成花费的时间越少。
h(n)启发函数常用的有:1.曼哈顿距离(适用四方向移动);2.对角线距离(八方向移动);3.欧几里得距离(任意方向移动);
并不是所有的寻路都适用A*算法,更多在启发函数容易建立时考虑使用(避障类),对于有向图不好建立启发函数则不适用A*。
A*的代码实现,最后附运算效果:
![](https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif)
while (openList.Count > 0)//openList大于0则一直循环 { int fn = -1; string minSt = ""; ///从OpenList中找出f(n)最小的点 foreach (string s in openList) { int i = Convert.ToInt16(s.Split('_')[0]); int j = Convert.ToInt16(s.Split('_')[1]); int gn = gnList[s];//实际距离 int hn = isA ? times * (Math.Abs(i - endi) + Math.Abs(j - endj)) : 0;//估算距离,启发函数 if (fn == -1 || fn > (gn + hn)) { fn = gn + hn; minSt = s;//找出最小的点 } } openList.Remove(minSt); closeList.Add(minSt);//将找到的点放入CloseList中 if (!isA && closeList.Contains(end)) { break; } foreach (var s in linkList[minSt])//将刚才的点的邻点加入到OpenList中并赋值,若已在,则更新该点的值 { int i = Convert.ToInt16(s.Split('_')[0]); int j = Convert.ToInt16(s.Split('_')[1]); if (!closeList.Contains(s) && !openList.Contains(s) && panel[i, j] != 0) { openList.Add(s); prest[s] = minSt; gnList[s] = gnList[minSt] + panel[i, j]; } else if (openList.Contains(s)) { if (gnList[s] > gnList[minSt] + panel[i, j]) { prest[s] = minSt; gnList[s] = gnList[minSt] + panel[i, j]; } } } if (isA && openList.Contains(end))//如果终点已经加入到OpenList中,则算法结束 { prest[end] = minSt; break; } } result.Add(end); while (prest.ContainsKey(result[0]))//一直向前溯源,获得起点到终点的路径 { result.Insert(0, prest[result[0]]); }View Code
下图中黑色表示障碍,红色表示寻路结果,蓝色表示搜寻经过的点。从2到4.
dijkstra
A*算法
加大h(n)后的A*算法
标签:C#,gnList,代码,minSt,距离,openList,算法,集合 From: https://www.cnblogs.com/cfsl/p/17000598.html