算法与计算机科学theory.stanford.edu编辑精选
A* 寻路算法入门
Introduction to A* (1997)
2014 — 2018，它一次次回到首页
黑点是上首页（≥ 50 分）的那次投稿，空心点是没冲上去的投稿，点越大分数越高。
导读
这是 Amit Patel 于 1997 年写下的 A* 寻路算法入门教程，通过大量可视化图解对比 A* 与 Dijkstra、贪心搜索等算法的差异，讲解启发式函数的作用。文章多年来持续更新，是游戏开发领域最经典的寻路算法参考资料之一。
为什么经久不衰：它把抽象的图搜索算法讲得直观易懂，配上可视化图示，二十多年来一直是无数开发者学习 A* 的起点，至今仍是该主题最好的入门材料。
HN 评论精选
作者的讲解直观形象，是作者编程成长路上的关键学习材料，影响深远
对我来说，在一个游戏世界里实现 A* 是我理解软件如何运作的编程里程碑之一。Amit 的文章当时就在线上，确实帮助我理清了这些问题，它们最大的优点就是讲解非常直观形象。很高兴看到这些文章仍然在线、持续更新，毫无疑问还在帮助其他人。可以说 Amit 的这些工作是我后来能成为全职独立游戏开发者的原因之一。
DizzyDoo查看英文原文
For me, figuring out how to implement A* on a world was one of those programming milestones along the way of me grokking how software is put together. In fact, I see there's a Stack Overflow question from me still online with an implementation I wrote in Python eight years ago (https://stackoverflow.com/questions/4159331/python-speed-up-an-a-star-pathfinding-algorithm), and I have sometimes wondered how many people have then used that old snippet as a reference. Amit's articles were online then, and definitely helped me think through these problems, and their main strength is just how visual the explanations all are. I'm pleased to see they're still online, being updated, and no doubt benefitting others, I know that personally Amit's effort was one of a number of things that has allowed me to be a full-time indie game developer all these years later.
作者自述文章写于 1997 年，正在用交互式图解重制相关内容
（作者）这些笔记大部分是我在 1997 年做游戏时写的，没想到它会成为我最受欢迎的网页之一。这些图虽然色彩丰富但我不太满意，所以现在正在制作新的交互式图解，从广度优先搜索开始。我还计划重新组织整体结构和导航，一次做一个页面，欢迎反馈！
amitp查看英文原文
(author here) I wrote most of these notes in 1997 while working on a game. Little did I realize that it'd be one of my most popular web pages. The diagrams are colorful but I don't like them (http://simblob.blogspot.com/2013/12/diagrams-on-my-pathfinding-pages.html) so I'm now making new interactive diagrams, starting with breadth first search (http://www.redblobgames.com/pathfinding/tower-defense/). While writing that page, I realized that I need to explain graphs (http://www.redblobgames.com/pathfinding/grids/graphs.html) (many game developers don't know graph theory) and suggest optimizations for grids (http://www.redblobgames.com/pathfinding/grids/algorithms.html) (a common use case, with interesting variants of A* like Jump Point Search). I'm also unhappy with the overall structure and navigation so I have a rough plan for how to organize the new pages (https://twitter.com/redblobgames/status/410182845777195008/photo/1). I'm taking it one page at a time instead of trying to do it all at once. Feedback appreciated!
文章排版出色，动手实现才能体会优先队列与算法性能的关系
一篇很棒的讲解……可惜很少有讲理论的网站能有这样好的排版和留白。大学时我们学过 Dijkstra 算法和优先队列，但直到我自己动手实现时才意识到优先队列对算法性能有多重要，真希望这两个概念当时能放在一起教。现在有了交互式可视化工具，这些概念应该更容易讲解了。
danso查看英文原文
A great walkthrough...I've read this before and still remember how the article was laid out...it's unfortunately rare for "theory" websites to have decent typography and whitespace that doesn't hinder reading. In my comsci classes, I'm pretty sure we talked about Dijkstra's algorithm...and I'm pretty sure we talked about priority queues. But not until I recently tried implementing the algorithm on my own (just for a fun six-degrees-of-separation network graph) did I realize how important having a priority queue was...I wish the two concepts had been taught in tandem and shown how they relate to algorithm performance (though yes, I do realize, according to Wikipedia, that Dijkstra's original algorithm did not have a min-priority queue). It'd be fun to go to a college com sci class now and see if these concepts are much better explained now that we have the ability to show them easily via interactive means (I'm sure many here have seen this wonderful site: http://qiao.github.io/PathFinding.js/visual/)...It's not only that they can be seen and interacted with, but it's conceivably much easier for the average com sci student to attempt to build an interactive visualization to demonstrate these concepts....A bit harder when you're working with only C/C++
建议视场景改用 Theta* 算法，可获得更短的任意角度路径
取决于你的应用场景，如果你对 A* 感兴趣，也可以考虑用 Theta*。它实现起来难度差不多，但在不需要沿图的边移动时能提供短得多的路径。
kamek查看英文原文
Depending on your application, if you're interested in A* you may be interested in using Theta* instead. It's not much more difficult to implement but provides much shorter paths if one does not need to remain on the edges in the graph. Take a look at the explanation and figures here: http://aigamedev.com/open/tutorials/theta-star-any-angle-paths/ for more information.
历次讨论
同类还值得读
位运算技巧集
Bit Twiddling Hacks
斯坦福页面上的经典位运算技巧合集，收录了 popcount、前导/尾随零、位反转、交换、舍入等大量技巧，并附有解释和性能讨论。
算法与计算机科学上首页 8 次 · 2011–2024graphics.stanford.edu编辑精选如何不按平均评分排序
How Not To Sort By Average Rating
经典文章解释了为什么按平均评分排序不可靠：只有少量评价的条目（比如仅一条五星）会轻易排到最前，而评价数量的差异被忽略。
算法与计算机科学上首页 7 次 · 2009–2024evanmiller.org编辑精选数据结构可视化
Data Structure Visualizations
旧金山大学 David Galles 教授制作的数据结构与算法交互式可视化网站，涵盖 B 树、红黑树、排序、图算法等，可逐步操作观察其运行过程。
算法与计算机科学上首页 6 次 · 2011–2021cs.usfca.edu编辑精选1996 年以来的计算机科学最佳论文奖
Best Paper Awards in Computer Science since 1996
Jeff Huang 维护的一个汇总页面，收录了自 1996 年以来计算机科学各主要会议的“最佳论文奖”获奖名单，并按年份和会议整理，方便读者一站式浏览历届获奖论文。
算法与计算机科学上首页 6 次 · 2010–2018jeffhuang.com编辑精选算法（Jeff Erickson）
Algorithms, by Jeff Erickson
伊利诺伊大学 Jeff Erickson 教授的算法课教材，免费在线开放。
算法与计算机科学上首页 5 次 · 2018–2022jeffe.cs.illinois.edu编辑精选