差分启发式

# Red Blob Games：微分启发 来源：https://www.redblobgames.com/blog/2026-08-08-differential-heuristics/ 博客文章：2026年8月8日2005年，谷歌展示了Google Maps，你可以拖动地图，而不用像MapQuest等那样重新加载页面。这个功能吸引了所有人的注意。但真正引起*我*注意的，是他们在2007年添加的一个功能：你可以拖动路线上的起点/终点（https://www.searchenginejournal.com/new-google-maps-drag-and-drop-feature/5243/）\[1\]，在你拖动时它会重新计算最短路径。这意味着他们在拥有数百万条道路的整个世界地图上实现了*快速*A\*寻路（https://en.wikipedia.org/wiki/A*_search_algorithm）\[2\]。他们是怎么做到的？ 我已经学习过A\*和常见的优化方法，但Google Maps使用的优化是我没学过的。我开始阅读论文。对几乎所有这些论文，我的反应都是：“除非你的地图非常大，否则这种复杂度不值得。”然而，有一种技术相对简单，我想进一步探索。 更好的启发函数可以减少A\*探索的地图区域 2014年，我写了我那篇A\*寻路的交互式指南（https://www.redblobgames.com/pathfinding/a-star/introduction.html）。我列了一个想要涵盖的其他主题的清单，包括图、启发函数、优化、数据结构等等。其中一个主题就是我在2007年学到的优化方法：*微分启发*（虽然这个名称是后来才有的）。 我在2015年尝试写一篇教程，但找不到我喜欢的解释。我又在2016、2018、2019、2022、2024年再次尝试。最终我意识到，我需要*停止*尝试写教程。虽然我理解这个算法，但我对它的理解还*不足以*能教给别人。 我需要更好地理解它。于是我切换到学习和实验模式。我学到了很多。我经历了一些起起落落。我意识到还有更多东西要学。在这个过程中，我找到了一个更满意的解释，并再次重写了这个页面。 1. 我以前把启发函数显示为很多数字。我改用了两个箭头。一个是启发函数建议的方向，另一个是正确方向。当它们一致时，启发函数会让A\*运行得更快。箭头展示启发函数的失配。 2. 我添加了可视化，展示该优化有效的区域，并配合一个交互式图表，让我可以移动各个点来观察这些区域如何变化。可视化改进后的区域。 这是我关于微分启发的新页面（https://www.redblobgames.com/pathfinding/heuristics/differential.html）。我是十多年前开始的，所以里面还残留着一些旧文本和代码。我认为还有很多改进空间，但这是我第一个认为“已发布”的版本。