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

Question

有趣的问题。

考虑我们有一条赛道，其中的汽车需要从 A 点开始到 B 点而不偏离赛道。轨道将是一个带有节点的网格。什么最好的算法适合这个找到最快的路径并且可能还包括加速？

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

欢迎任何建议:)

标签： algorithmequation-solving

Answer 1

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

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