了解A *搜索 [英] Understanding A* search

问题描述

我很难理解如何将A *搜索应用于实时穿越迷宫的机器人.我了解A *的工作原理，但仅在预先计算"的意义上(即，如果您要在尝试穿越迷宫之前先确定整个路径).

I am having some trouble understanding how A* search could be applied to a robot traversing a maze in real time. I understand how A* works but only in "pre-computed" sense (i.e. if you were to work out the whole path before attempting to traverse the maze).

在迷宫的每个步骤中，您将如何使用它来回答下一步"?还是我错过了什么?非常感谢！

How would you use it to give an answer to "where to next" at every step of the maze? Or am I missing something? Thanks a lot!

推荐答案

通常，机器人会尽最大可能绘制迷宫，然后运行寻路算法并遵循最终的最佳路径.如果以后发现迷宫发生变化，则机器人将从其当前位置重新运行A *.

Generally the robot will map out the maze as best it can, then run the pathfinding algorithm and follow the resulting best path. If changes to the maze are later detected, the robot will rerun A* from its current position.

A *有一种更改，称为 D * -lite ，当对迷宫进行细微更改时，它能够重用以前的搜索以加快将来的搜索速度.这是火星漫游者使用的算法.

There is an alteration to A*, called D*-lite, that is able to reuse past searches to speed up future searches when small changes to the maze are made. This is the algorithm the Mars Rovers use.

这篇关于了解A *搜索的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！