Google Maps 十年磨一剑：A* 算法优化揭秘
Differential Heuristics
2007 年，Google Maps 实现了拖拽起点终点实时重算最短路径的功能，这背后是惊人的 A* 寻路优化。我花了十年时间研究这一技术，从最初阅读论文觉得过于复杂，到后来反复尝试撰写教程却因理解不够深入而屡屡受挫。最终，我意识到必须先彻底搞懂再教别人。通过切换为学习和实验模式，我重新设计了可视化方案，用箭头直观展示启发式函数的方向匹配，并制作了交互式图表来演示优化区域。这篇关于 Differential Heuristics 的新页面，是我十年探索的结晶，旨在让复杂的算法优化变得直观易懂。
我最终意识到，我需要停止试图撰写教程，因为虽然我理解了这个算法，但还不足以教会别人。
- plomme
一如既往，Red Blob 的文章写得非常棒。它彻底颠覆了我对 Google Maps 寻路机制的高层假设。回想起算法课的内容，我曾以为 Google Maps 之所以这么快，是因为最短路径查找具有“最优子结构”。也就是说，从 A 到 C 经过 B 的最短路径，同时也包含了从 A 到 B 以及从 B 到 C 的最短路径；因此，对于任意给定路径的大部分路段，你可以通过一些预计算的“中点”路径来规划路线。但读完这篇文章，我的认知被推翻了：地标（landmarks）其实是位于目标点之后，而不是在路线的中间！这真是一个非常有用的工具。
- simonw
五天前这里讨论过：https://news.ycombinator.com/item?id=49079995
（不过说实话，这项成果实在太酷了，值得再来一次讨论，上次那篇只有 40 条评论。）
- inigyou
文章和演示都很棒。不过我对颜色有点困惑——至少有一次，文中提到蓝色方块是因为地标而不需要检查的，但实际上它们是绿色的，而蓝色的方块是本来就没被检查的。我可不是色盲。
你很多地图都是由几个连接点串联起来的房间组成的。你有没有考虑过先在整个房间图上进行寻路，然后再在每个房间内单独寻路？你甚至可以从一个门到另一个门预计算房间内所有路径，虽然你可能并不需要这么做，但你确实需要预计算它们的代价。这大概和在每个房间放一个地标所带来的寻路成本差不多。