启发式寻路算法

启发式寻路算法

启发函数 (Heuristic Function)

盲目搜索会浪费很多时间和空间, 所以我们在路径搜索时, 会首先选择最有希望的节点, 这种搜索称之为 "启发式搜索 (Heuristic Search)"

如何来界定"最有希望"? 我们需要通过 启发函数 (Heuristic Function) 计算得到.

对于网格地图来说, 如果只能四方向(上下左右)移动, 曼哈顿距离(Manhattan distance) 是最合适的启发函数.

function Manhattan(node) =
    dx = abs(node.x - goal.x)
    dy = abs(node.y - goal.y)
    // 在最简单的情况下, D 可以取 1, 返回值即 dx + dy
    return D * (dx + dy)

如果网格地图可以八方向(包括斜对角)移动, 使用切比雪夫距离(Chebyshev distance) 作为启发函数比较合适.

function Chebyshev(node) =
    dx = abs(node.x - goal.x)
    dy = abs(node.y - goal.y)
    // max(dx, dy) 保证了斜对角的距离计算
    return D * max(dx, dy)

如果地图中允许任意方向移动, 不太建议使用网格 (Grid) 来描述地图, 可以考虑使用路点 (Way Points) 或者导航网格 (Navigation Meshes), 此时使用欧式距离(Euclidean distance) 来作为启发函数比较合适.

function heuristic(node) =
    dx = abs(node.x - goal.x)
    dy = abs(node.y - goal.y)
    // 在最简单的情况下, D 可以取 1, 返回值即 sqrt(dx * dx + dy * dy)
    return D * sqrt(dx * dx + dy * dy)

欧式距离因为有一个 sqrt() 运算, 计算开销会增大, 所以可以使用 Octile 距离 来优化(不知道怎么翻译), Octile 的核心思想就是假定只能做 45 度角转弯.

function heuristic(node) =
    dx = abs(node.x - goal.x)
    dy = abs(node.y - goal.y)
    k = sqrt(2) - 1
    return max(dx, dy) + k * min(dx, dy)

下图是一个启发函数的简单示意

Dijkstra

Dijkstra 算法 是由计算机大牛 Dijkstra 在1956年提出来的, 它是一个"精确"的寻路算法, 能保证发现节点之间的最短路径, 本质是一个 广度优先搜索 .

  • g(n): 从起始点到当前点 n 的开销, 在网格地图中一般就是步长.
  • 将起始点 S 加入 open-list.
  • 从当前的 open-list 中选取 g(n) 最优(最小)的节点 n, 加入 closed-list
  • 遍历 n 的后继节点 ns
  • 如果 ns 是新节点, 加入 open-list
  • 如果 ns 已经在 open-list 中, 并且当前 h(ns) 更优, 则更新 ns 并修改 parent
  • 迭代, 直到找打目标节点 D, 回溯得到路径

Dijkstra 算法的效率并不高, 时间复杂度为 O(n^2), 但是它保证了寻路结果是最短距离.

Best-First-Search

Best-first Search 最佳优先搜索, 简称为 BFS.

BFS 根据启发式函数的推断, 每次迭代最优的节点, 直到寻找到目标节点. 一个简单的算法流程如下:

  • h(n) 代表从当前点 n 到目标点 S 的估算开销, 即启发函数.
  • 将起始点 S 加入 open-list.
  • 从当前的 open-list 中选取 h(n) 最优(最小)的节点 n, 加入 closed-list
  • 遍历 n 的后继节点 ns
  • 如果 ns 是新节点, 加入 open-list
  • 如果 ns 已经在 open-list 中, 并且当前 h(ns) 更优, 则更新 ns 并修改 parent
  • 迭代, 直到找打目标节点 D, 回溯得到路径

如果不使用 open-list, 直接每次都寻找 n 的后继节点中最优的节点, BFS 则退化为贪心最佳优先搜索 (Greedy BFS).

不管是 BFS 还是 Greedy-BFS, 本质上都还是寻找 局部最优 , 虽然效率会比 Dijkstra 高很多, 但最终得到的解并不一定是全局最优(最短距离), 在地图中有障碍物时尤为明显.

A-Star

A-Star 俗称 A , 是应用最广的寻路算法, 在很多场景下都适用. A 兼顾了 Dijkstra 的准确度和 BFS 的效率.

  • f(n) = g(n) + h(n) , g(n) 和 h(n) 的定义同上
  • 当 g(n) 退化为 0, 只计算 h(n) 时, A* 即退化为 BFS.
  • 当 h(n) 退化为 0, 只计算 g(n) 时, A* 即退化为 Dijkstra 算法.
  • 将起始点 S 加入 open-list.
  • 从当前的 open-list 中选取 f(n) 最优(最小)的节点 n, 加入 close-list
  • 遍历 n 的后继节点 ns
  • 如果 ns 是新节点, 加入 open-list
  • 如果 ns 已经在 open-list 中, 并且当前 f(ns) 更优, 则更新 ns 并修改 parent
  • 迭代, 直到找打目标节点 D.

A 算法在从起始点到目标点的过程中, *尝试平衡 g(n) 和 h(n), 目的是找到最小(最优)的 f(n).

A-Star 算法衍生

如果在每一步迭代扩展中, 都去除掉质量比较差的节点, 即选取有限数量的后继节点, 这样减少了空间开销, 并提高了时间效率. 但是缺点可能会丢弃潜在的最佳方案. 这就是 集束搜索(Beam Search), 本质上还是局部最优的贪心算法.

当距离起点越近, 快速前行更重要; 当距离目标点越近, 到达目标更重要. 基于这个原则, 可以引入权重因子, A 可以演进为选取 f(n) = g(n) + w(n) h(n) 最优的点, w(n) 表示在点 n 的权重. w(n) 随着当距离目标点越近而减小. 这是 动态加权 A (Dynamic Weighting A).

当从出发点和目标点同时开始做双向搜索, 可以利用并行计算能力, 更快的获得计算结果, 这是 双向搜索 (Bidirectional Search). 此时, 向前搜索 f(n) = g(start, n) + h(n, goal), 向后搜索 f(m) = g(m, goal) + h(start, m), 所以双向搜索最终可以归结为选取 g(start, n) + h(m, n) + g(m, goal) 最优的一对点(m, n).

A 在静态地图中表现很棒, 但是在动态环境中(例如随机的障碍物), 却不太合适, 一个基于 A 算法的 D 算法(D-Star, Dynamic A) 能很好的适应这样的动态环境. D 算法中, 没有 g(n), f(n) 退化为 h(n), 但是每一步 h(n) 的计算有所不同: *h(n) = h(n-1) + h(n-1, n), c(n-1, n) 表示节点 n-1 到节点 n 的开销.

示例代码

下面是来自 PathFinding.js 的一份 JS 示例代码:

// A* 寻路
AStarFinder.prototype.findPath = function(startX, startY, endX, endY, grid) {
    // heap 做容器(有序)
    var openList = new Heap(function(nodeA, nodeB) {
            return nodeA.f - nodeB.f;
        }),
        startNode = grid.getNodeAt(startX, startY),
        endNode = grid.getNodeAt(endX, endY),
        heuristic = this.heuristic,
        diagonalMovement = this.diagonalMovement,
        weight = this.weight,
        abs = Math.abs, SQRT2 = Math.SQRT2,
        node, neighbors, neighbor, i, l, x, y, ng;

    // 分别代表 g(n) 和 f(n)
    startNode.g = 0;
    startNode.f = 0;

    // 从起始点开始
    openList.push(startNode);
    startNode.opened = true;

    // while the open list is not empty
    while (!openList.empty()) {
        // 找到当前队列中最小 f(n)
        node = openList.pop();

        // closed 标签表明已经计算过
        node.closed = true;

        // 结束, 并回溯最佳路线
        if (node === endNode) {
            return Util.backtrace(endNode);
        }

        // 邻居节点(四方向或者八方向有区别的)
        neighbors = grid.getNeighbors(node, diagonalMovement);
        for (i = 0, l = neighbors.length; i < l; ++i) {
            neighbor = neighbors[i];
            // 已经结算过的就忽略了
            if (neighbor.closed) {
                continue;
            }
            x = neighbor.x;
            y = neighbor.y;

            // g(n), 实际距离, 实际上是 Euclidean distance
            ng = node.g + ((x - node.x === 0 || y - node.y === 0) ? 1 : SQRT2);

            // 两种情况需要计算:
            // 1. 这是一个新的节点
            // 2. 这个节点当前计算的 g(n) 更优
            if (!neighbor.opened || ng < neighbor.g) {

                neighbor.g = ng;
                // h = 权重 * 启发函数的计算结果
                neighbor.h = neighbor.h || weight * heuristic(abs(x - endX), abs(y - endY));
                neighbor.f = neighbor.g + neighbor.h;

                // 到父节点的链接, 方便结果回溯
                neighbor.parent = node;

                // 更新到结果集
                if (!neighbor.opened) {
                    openList.push(neighbor);
                    neighbor.opened = true;
                } else {
                    // the neighbor can be reached with smaller cost.
                    // Since its f value has been updated, we have to
                    // update its position in the open list
                    openList.updateItem(neighbor);
                }
            }
        } // end for each neighbor
    } // end while not open list empty

    // 没找大, 失败
    return [];
};


// Dijkstra 弱化 A* 的 h(n) = 0
function DijkstraFinder(opt) {
    AStarFinder.call(this, opt);
    this.heuristic = function(dx, dy) {
        return 0;
    };
}
DijkstraFinder.prototype = new AStarFinder();
DijkstraFinder.prototype.constructor = DijkstraFinder;


// BFS 强化 A* 的 h(n), 相当于弱化 g(n)
function BestFirstFinder(opt) {
    AStarFinder.call(this, opt);
    var orig = this.heuristic;
    this.heuristic = function(dx, dy) {
        return orig(dx, dy) * 1000000;
    };
}
BestFirstFinder.prototype = new AStarFinder();
BestFirstFinder.prototype.constructor = BestFirstFinder;

无障碍寻路对比

默认使用曼哈顿距离来做启发函数.

无障碍 BFS

无障碍 Dijkstra

无障碍 A*

典型障碍寻路对比

默认使用曼哈顿距离来做启发函数.

有障碍 BFS

有障碍 Dijkstra

有障碍 A*

启发函数寻路对比

以 A 算法为例, 除了 *曼哈顿距离 之外, 其他的启发函数会增加一些计算开销.

A* Manhattan Heuristic

A* Chebyshev Heuristic

A* Euclidean Heuristic

A* Octile Heuristic

参考文章与代码

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏xingoo, 一个梦想做发明家的程序员

Spark MLlib中的OneHot哑变量实践

在机器学习中,线性回归和逻辑回归算是最基础入门的算法,很多书籍都把他们作为第一个入门算法进行介绍。除了本身的公式之外,逻辑回归和线性回归还有一些必须要了解的内...

32510
来自专栏SeanCheney的专栏

Numpy和MatplotlibPython科学计算——Numpy线性代数模块(linalg)随机模块(random)Python的可视化包 – Matplotlib2D图表3D图表图像显示

Python科学计算——Numpy Numpy(Numerical Python extensions)是一个第三方的Python包,用于科学计算。这个库的前身...

5764
来自专栏技术随笔

[RNN] Simple LSTM代码实现 & BPTT理论推导

4574
来自专栏懒人开发

(8.2)James Stewart Calculus 5th Edition:Area of a Surface of Revolution

1383
来自专栏码云1024

游戏中的人物是如何寻路的?

49013
来自专栏null的专栏

机器学习算法实现解析——word2vec源码解析

在阅读本文之前,建议首先阅读“简单易学的机器学习算法——word2vec的算法原理”(目前还没发布),掌握如下的几个概念: 什么是统计语言模型 神经概率语言模型...

6407
来自专栏AILearning

【Scikit-Learn 中文文档】双聚类 - 无监督学习 - 用户指南 | ApacheCN

2.4. 双聚类 Biclustering 可以使用 sklearn.cluster.bicluster 模块。 Biclustering 算法对数据矩阵的...

3509
来自专栏大数据风控

Python中的交叉分析pivot_table

交叉分析 通常用于分析两个或两个以上,分组变量之间的关系,以交叉表形式进行变量间关系的对比分析; 从数据的不同维度,综合进行分组细分,进一步了解数据的构成、分...

2798
来自专栏码云1024

a-start寻路算法

在英雄联盟之中,当你和你的队友都苦苦修炼到十八级的时候,仍然与敌方阵营不分胜负,就在你刚买好装备已经神装的时候,你看见信息框中一条队友的消息:“大龙集合”,这个...

2862
来自专栏机器学习和数学

[编程经验] SciPy之图像处理小结

Python中可以处理图像的module有很多个,比如Opencv,Matplotlib, Numpy, PIL以及今天要分享的SciPy。其他几个后续都会总结...

7577

扫码关注云+社区