算法找到最有效的移动到达给定的点
（这不完全是我的问题，但它是同构的，我认为这个解释对其他人来说是最容易理解的。）
假设我在n维空间中有一组点。 例如使用3个维度：
A : [1,2,3]
B : [4,5,6]
C : [7,8,9]
我也有一组向量来描述这个空间中的可能运动：
V1 : [+1,0,-1]
V2 : [+2,0,0]
现在，给定一个点dest，我需要找到一个起始点p和一组向量移动，这将使我以最有效的方式运行到dest。 效率被定义为“最少的移动次数”，不一定是“最小线性距离”：如果移动设置使得你可以以更少的移动到达那里，那么可以选择比其他候选者更远的目标。 移动中的向量必须是可用向量的严格子集; 除非输入集中出现多次，否则不能多次使用同一个向量。
我的输入包含约100个起点和约10个向量，并且我的维数为〜20。 起始点和可用向量将在应用程序的整个生命周期中进行修复，但我将为许多不同的目标点寻找路径。 我想优化速度，而不是记忆。 算法失败是可以接受的（找不到可能的路径到dest）。
更新w /可接受的解决方案
我采用了一种与下面标记为“接受”非常相似的解决方案。 我迭代所有的点和向量，并用到达它们的路线构建所有可到达点的列表。 我将这个列表转换为<dest，p + vectors>的散列，为每个目标点选择最短的向量集合。 （散列大小也有一些优化，这在这里不重要。）后续的目标查找在不变的时间内发生。
实际上，考虑到你有大约10个矢量，对于一个给定的目标点，你可以只从矢量的子集计算1024个“目标” - 例如每个可到达的空间，以及有关哪组移动到达的信息。 根据上下文，这可能是“缓慢”或“快速”（如果在像GPU这样的并行计算设备上实现，则速度非常快）。
拥有所有到达目标的集合，您可以更快地计算路径，然后您可以选择从最少移动到达目标的点，从您的查询或更远的子集中进行选择。
（感谢Strilanc）
我相信你将能够对A *（aka A star）路径寻找算法进行广泛的应用。 没有理由不能在第N空间完成。 如果你能描述每一步行动的成本，那么它就能确定最理想的路径。
http://en.wikipedia.org/wiki/A*_search_algorithm
所以你想找到你的一组矢量的一个子集，使得这个子集合成一个给定的值。 在1维中，这被称为子集和问题，并且是NP-Complete。
幸运的是，你只有10个向量，所以你的问题大小实际上是相当小和易于处理的。 首先尝试所有2 ^ 10移动组合，为每个起点和选择最好的一个。 然后从那里寻找简单的优化。
一些简单的优化可能会起作用：
上一篇: Algorithm to find most efficient moves to arrive at a given point
下一篇: Code Golf: Quickly Build List of Keywords from Text, Including # of Instances