[数据结构与算法]寻路算法笔记

宽度优先算法
从根节点开始，沿着树型的宽度（遍历树）遍历的每一个节点，继续遍历子节点，直到找到需要的节点为止。
广度优先算法

FloodFill算法

A * 算法

原理

A*（A-Star)算法是一种静态路网中求解最短路径最有效的直接搜索方法，也是许多其他问题的常用启发式算法。注意——是最有效的直接搜索算法，之后涌现了很多预处理算法（如ALT，CH，HL等等），在线查询效率是A算法的数千甚至上万倍。
*
公式表示为： f(n)=g(n)+h*(n),

其中， f*(n) 是从初始状态经由状态n到目标状态的最小代价估计，

g*(n) 是在状态空间中从初始状态到状态n的最小代价，

h*(n) 是从状态n到目标状态的路径的最小估计代价。

（对于路径搜索问题，状态就是图中的节点，代价就是距离）

真实h(n)的选取：

保证找到最短路径（最优解的）条件，关键在于估价函数f(n)的选取（或者说h(n)的选取）。

以h(n)表达状态n到目标状态估计的距离，那么h(n)的选取大致有如下三种情况：

1. 如果h(n)< h*(n)，这种情况下，搜索的点数多，搜索范围大，效率低。但能得到最优解。

2. 如果h(n)=h*(n)，此时的搜索效率是最高的。

3. 如果 h(n)>h*(n)，搜索的点数少，搜索范围小，效率高，但不能保证得到最优解。

距离估计与实际值越接近，估价函数取得就越好

例如对于几何路网来说，可以取两节点间曼哈顿距离做为距离估计，即

f =g(n) + (abs(dx - nx) + abs(dy - ny))

public void calculate(double[,] points)
{
  var distanceArray = new double[points.Length, points.Length];
 
  for (int i = 0; i < points.Length; i++)
    for (int j = 0; j < points.Length; j++)
      distanceArray[i, j] = Distance(points[i, 0], points[i, 1], points[j, 0], points[j, 1]);     
 
}
 
public static double Distance(double x1, double y1, double x2, double y2)
=>  Math.Sqrt(((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2)));   

这样估价函数f(n)在g(n)一定的情况下，会或多或少的受距离估计值h(n)的制约，节点距目标点近，h值小，f值相对就小，能保证最短路的搜索向终点的方向进行。明显优于Dijkstra算法的毫无方向的向四周搜索。

算法实现（路径搜索）

创建两个表，OPEN表保存所有已生成而未考察的节点，CLOSED表中记录已访问过的节点。

while(OPEN!=NULL)
{
    //从OPEN表中取f(n)最小的节点n;
    if(n节点==目标节点)
        break;
    for(当前节点n的每个子节点X)
    {
        计算f(X);
        if(XinOPEN)
            if(新的f(X)<OPEN中的f(X))
            {
                把n设置为X的父亲;
                更新OPEN表中的f(n);
            }
        if(XinCLOSE)
            continue;
        if(Xnotinboth)
        {
            //把n设置为X的父亲;
            //求f(X);
            //并将X插入OPEN表中;
            //还没有排序
        }
    }
    //endfor
    //将n节点插入CLOSE表中;
    //按照f(n)将OPEN表中的节点排序;
    //实际上是比较OPEN表内节点f的大小，从最小路径的节点向下进行。
}//endwhile(OPEN!=NULL)

戴克斯特拉算法

NavMesh