图形演算–寻路算法

前言

寻路算法大致可以分为「深度优先搜索（Depth-First Search，DFS）、广度优先搜索（Breath-First Search，BFS）和最佳优先搜索（Best-First Search，BestFS）三大类。

对于最佳优先搜索部份，较为熟悉的是A*寻路算法。

图形描述

图形是由节点（node）与线（edge）组成的。比如，下面包含六个节点与十条线组成的简单图形：

深度优先搜索

深度优先搜索（DFS），就是一直搜索距当前节点最近的没有被访问过的最近临节点的一种方法

这种方法可以采用「递归搜索」完成：

dfs(g, node) {
  if (g[node].v !=0) return;   // 如果已访问过，不再访问
  trace("%d=>", node);        // 打印出没有被访问过的节点
  g[node].v = 1;              //   设为已访问
  let neighbors = g[node].n;  // 取出相邻节点
  for (let i in neighbors) {  // 访问每个临界点
    dfs(g, neighbors[i]);     //   继续访问其他临节点
  }
}

结果如下：

广度优先搜索

虽然深度优先搜索可以搜索整个图形，但是很可能绕了很久才找到目标（比如路径太长），会消耗很长时间。而「广度优先搜索」（BFS）就可以解决耗时问题。

广度优先搜索是从一个节点开始，搜索每个相邻节点和相邻节点下面的相邻节点，优先访问深度最浅的节点。

广度优先搜索，采用「先进先出」（First-in First-Out，FIFO）的方式来管理所有节点，因此通常在「广度优先搜索」里会有个队列（queue）结构，以下是广度优先搜索的算法：

dequeue(a) {
  return a.shift();
}
bfs(g, q) {
  if (q.length == 0) return;
  var node = dequeue(q);
  if (g[node].v == 0)
    g[node].v = 1;
  else
    return;
  trace("%d=>", node);
  var neighbors = g[node].n; //取出相邻节点。
  for (var i in neighbors) {
    var n = neighbors[i];
    if (!g[n].visited)
      q.push(n);             //将没有访问过的相邻节点放入队列
  }
  bfs(g, q);
}

最佳优先搜索

但是，深度搜寻一直在没有目标的搜索，而广度搜寻会消耗太多內存，效率较低，无法很快的找到目标点。

如果知道哪些点距离目标点最近的话，那就能采用「最佳优先搜索（Best-First Search）。

最佳优先搜索方法与广度优先搜寻类似，但是并不使用用队列（queue），而是采用一种根据优先程度排序的结构，每次都取出最好的那个节点继续搜索。

但是，一般节点的好坏很难知道，单纯采用距离最近往往会过度简化问题，这也是是最佳优先搜索比较麻烦的地方。

通常情况，只要符合$h(x) \leq d(x,y) + h(y)$，就不用考虑太多，常用A*算法来进行快速搜索，这种方法比广度优先搜索快很多，因为A*算法不会搜索所有节点，而是有系统的朝着整体较好的方向搜索，这种方法在游戏领域里常被用在NPC（非玩家角色）寻找上，是寻路算法中较强大算法之一。这里不再赘述。

code enjoy! 🤪🤪🤪

作者：indeex

链接：https://indeex.cc

著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。