接着上一章的问题我们继续讲

Dijkstra 算法

宽度优先搜索算法，解决了起始顶点到目标顶点路径规划问题，但不是最优以及合适的，因为它的边没有权值（比如距离），路径无法进行估算比较最优解。为何权值这么重要，因为真实环境中，2个顶点之间的路线并非一直都是直线，需要绕过障碍物才能达到目的地，比如森林，湖水，高山，都需要绕过而行，并非直接穿过。

比如我采用宽度优先算法，遇到如下情况，他会直接穿过障碍物（绿色部分 ），明显这个不是我们想要的结果:

解决痛点:

寻找图中一个顶点到另一个顶点的最短以及最小带权路径是非常重要的提炼过程。为每个顶点之间的边增加一个权值，用来跟踪所选路径的消耗成本，如果位置的新路径比先前的最佳路径更好，我们将添加它，规划到新的路线中。

Dijkstra 算法基于宽度优先算法进行改进，把当前看起来最短的边加入最短路径树中 ，利用贪心算法计算并最终能够产生最优结果的算法。具体步骤如下:

1、每个顶点都包含一个预估值cost(起点到当前顶点的距离)，每条边都有权值v ，初始时，只有起始顶点的预估值cost为0，其他顶点的预估值d都为无穷大 ∞。

2、查找cost值最小的顶点A，放入path队列

3、循环A的直接子顶点，获取子顶点当前cost值命名为current_cost，并计算新路径new_cost，new_cost=父节点A的cost+v(父节点到当前节点的边权值),如果new_cost

4、重复2，3直至没有顶点可以访问.

我们看下图例:

我们看下面的代码(js)：

frontier = new PriorityQueue();

frontier.put(start, 0)

came_from = new Array();

came_from[start] = 0;



while(frontier.length>0){

    current = frontier.get()



   if current == goal:

      break



       for(next in graph.neighbors(current)){

           var notInVisited = visited.indexOf(next)==-1;

           //没有访问过

        if(notInVisited ) {

            //离目标的距离 ，距离越近优先级越高

             priority = heuristic(goal, next);

             frontier.put(next, priority);

             came_from[next] = current;

          }

       }

}



function heuristic(a, b){

    //离目标的距离

   return abs(a.x - b.x) + abs(a.y - b.y)

}

缺点:

1.路径不是最短路径，只能是较优

如何在搜索尽量少的顶点同时保证最短路径？我们来看A*算法。

A*算法

从上面算法的演进，我们逐渐找到了最短路径和搜索顶点最少数量的两种方案，Dijkstra 算法和 贪婪最佳优先搜索。那么我们有没有可能汲取两种算法的优势，令寻路搜索算法即便快速又高效？

答案是可以的，A*算法正是这么做了，它吸取了Dijkstra 算法中的cost_so_far，为每个边长设置权值，不停的计算每个顶点到起始顶点的距离，以获得最短路线，同时也汲取贪婪最佳优先搜索算法中不断向目标前进优势，并持续计算每个顶点到目标顶点的距离，以引导搜索队列不断想目标逼近，从而搜索更少的顶点，保持寻路的高效。

解决痛点:

A*算法的优先队列排序方式基于F值:

F=cost(顶点到起始顶点的距离 )+heuristic(顶点到目标顶点的距离 )

我们来看下算法(js)：

var frontier = new PriorityQueue();

frontier.put(start);

path = new Array();

cost_so_far = new Array();

path[start] = 0;

cost_so_far[start] = 0



while(frontier.length>0){

    current = frontier.get()



   if current == goal:

      break



       for(next in graph.neighbors(current)){

           var notInVisited = visited.indexOf(next)==-1;

           var new_cost = cost_so_far[current] + graph.cost(current, next);

           //没有访问过而且路径更近

        if(notInVisited ||  new_cost < cost_so_far[next]) {

              cost_so_far[next] = new_cost

              //队列优先级= new_cost(顶点到起始顶点的距离 )+heuristic(顶点到目标顶点的距离 )

            priority = new_cost + heuristic(goal, next)

            frontier.put(next, priority)

            path[next] = current

          }

       }

}



function heuristic(a, b){

    //离目标的距离

   return abs(a.x - b.x) + abs(a.y - b.y)

}
 

以下分别是Dijkstra算法，贪心算法，以及A*算法的寻路雷达图，其中格子有数字标识已经被搜索了，可以对比下三种效率:

B*算法

B*算法是一种比A*算法更高效的算法， 适用于游戏中怪物的自动寻路，其效率远远超过A*算法，经过测试，效率是普通A*算法的几十上百倍。B*算法不想介绍了，自己去google下吧，

通过以上算法不断的演进，我们可以看出每一种算法的局限，以及延伸出的新算法中出现的解决方式，希望方便你的理解。

说明：

文章多出突破引用一下文章，代码也是。原文写的很棒，有兴趣，可以移步原文查看，或者google搜索:A*algorithm

引用文章:http://www.redblobgames.com/pathfinding/a-star/introduction.html