algorithm - 以最快的方式解决轨道路径的最佳算法是什么？

Question

有趣的问题。

假设我们有一条赛道，赛车需要从 A 点开到 B 点而不偏离赛道。轨道将是一个带有节点的网格。哪种最佳算法最适合此以找到最快的路径并且可能还包括加速？

到目前为止，A* 算法似乎是最好的。但是，您将如何在最快路径中包含加速？ https://en.wikipedia.org/wiki/A *_search_algorithm

欢迎提出任何建议:)

Answer 1

首先，如果您的路线的网格是连续的，则不可能找到准确的最快路径。但是，您可以使其离散并使用 A* 获得非常好的近似值。

A* 是解决此问题的好方法，但对于较大的轨道它可能会变慢，除非您将问题分解为几个较小的寻路问题。如果您想将加速和减速作为您的汽车在每一步可能采取的 Action ，那么实现这一点的一种方法是将汽车的当前速度作为状态定义的一部分。由于 A* 适用于离散状态空间，因此您还需要离散化加速度/速度。