(这不完全是我遇到的问题，但它是同构的，我认为这种解释对其他人来说是最容易理解的。)
假设我在 n 维空间中有一组点。例如使用 3 个维度:
A : [1,2,3]
B : [4,5,6]
C : [7,8,9]
我还有一组描述这个空间中可能运动的向量:
V1 : [+1,0,-1]
V2 : [+2,0,0]
现在，给定一个点 dest，我需要找到一个起点 p 和一组向量 moves dest 以最有效的方式。效率被定义为“最少的移动次数”，不一定是“最小线性距离”:如果移动集，则允许选择比其他候选者更远离dest的p这样你就可以用更少的 Action 到达那里。 moves 中的向量必须是可用向量的严格子集；您不能多次使用同一个向量，除非它在输入集中出现多次。
我的输入包含大约 100 个起点和大约 10 个向量，我的维数是大约 20。起点和可用矢量将在应用程序的生命周期内固定，但我会为很多很多不同的目的地 点寻找路径。我想优化速度，而不是内存。算法失败是可以接受的(找不到到达目的地的可能路径)。
使用已接受的解决方案进行更新
我采用了与下面标记为“已接受”的解决方案非常相似的解决方案。我遍历所有点和向量并构建所有可到达点的列表以及到达它们的路线。我将此列表转换为 <dest、p+vectors> 的散列，为每个目标点选择最短的向量集。 (还有一些针对哈希大小的优化，这与此处无关。)后续的 dest 查找在恒定时间内发生。
最佳答案
实际上，考虑到您有大约 10 个向量，对于给定的目标 点，您可以只计算向量子集中的 1024 个“目标” --例如，每个可到达的空间，以及有关到达那里的一组 Action 的信息。这可能是“慢”或“快”，具体取决于上下文(如果在 GPU 等并行计算设备上实现，速度快得离谱)。
有了到达那里的所有集合，您可以更快地计算路径，然后您可以选择以最少的移动到达dest的点，从这些点的子集中选择这是您的查询或进一步的查询。
(感谢 Strilanc)
关于找到到达给定点的最有效 Action 的算法，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/2111934/