使用 A* 为火星探测器寻找可接受的启发式算法

Finding Admissible Heuristics for Martian Rover using A*

我正在尝试解决有关 AI 的问题。我有一个 "robot" 从 A 点到 B 点应该尽可能快和便宜。这个漫游者不能爬到高于 10 个单位的高度,而且他的路线成本受地形类型的影响。我需要你的帮助,因为我需要找到一个可接受的启发式方法来解决我的问题。我已经尝试过欧几里得距离,但这还不够。你能帮帮我吗?

我建议您查看 this page 以获得启发式的一些想法。它们并不都适用于您的情况,因为我不相信您有网格地图?但你至少可以看看。

此外,我建议尝试考虑在不同类型的地形中可能产生的各种成本。例如,如果您知道每种可能的地形类型的最小成本为 2,则可以安全地将欧几里得距离乘以 2。如果最常见的地形类型的成本为 2,但也有一些类型对于成本较低的地形,如果开始乘以 2,您将失去找到最佳解决方案的保证,但在实践中您仍然可以更快地找到解决方案。

对我来说,这个问题听起来像是家庭作业(如果我错了请纠正我),这使得很难给出一个单一的答案。我想家庭作业的重点甚至是研究一下并尝试一些不同的东西,看看它们是如何工作的(或不工作),这可以提高你对算法工作原理的理解。所以,真的,只是尝试一些东西。