寻路算法可视化工具 所有算法均以图搜索的形式实现,即,将不再考虑已经访问过的地点。 不知情的(不使用启发式)搜索算法: 广度优先 深度优先搜索 统一成本搜索(Dijkstra) 明智的(使用启发式)搜索算法: 贪婪的最佳优先搜索 A *-搜索 这里使用的启发式是L距离,即abs(x_cell-x_goal)+ abs(y_cell-y_goal)。 可以很容易地看出,这种启发式满足以下三角形不等式: 启发式(cell)<=成本(cell,cell')+启发式(cell'), 其中cell'是cell的邻居,而cost(cell,cell')是从cell到cell'的成本(始终为1)。 因此,试探法是“一致的”,这是A * -Graph-Search最优的要求,即始终找到最短的求解路径(如果存在求解路径)。