前面提到过迪杰斯特拉算法，它的原理简述如下：
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*的代码实现，最后附运算效果：
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