用于找到到达给定点的最有效移动的算法

Question

(这不是我所遇到的问题,但它是同构的,我认为这种解释对其他人来说是最容易理解的.)

假设我在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.效率定义为"最少的动作",不一定是"至少直线距离":它允许选择一个p进一步的从DEST比其他候选人,如果此举集是这样,你可以在更少的移动那里.移动中的向量必须是可用向量的严格子集; 除非在输入集中出现多次,否则不能多次使用同一个向量.

我的输入包含~100个起点和~10个矢量,我的维数是~20.起点和可用矢量将在应用程序的生命周期内得到修复,但我会找到许多不同目标点的路径.我想优化速度,而不是内存.算法失败(找不到dest的可能路径)是可以接受的.

更新w/Accepted Solution

我采用的解决方案非常类似于下面标记为"已接受"的解决方案.我遍历所有点和向量,并构建一个包含所有可到达点的列表以及到达它们的路径.我将此列表转换为< dest,p + vectors > 的哈希值,为每个目标点选择最短的向量集.(对于散列大小也有一点优化,这在这里不相关.)后续的dest查找在恒定时间内发生.

Answer 1

实际上,考虑到您有大约10个向量,对于给定的目标点,您可以仅计算向量子集中的1024个"目标" - 例如每个可到达的空间,以及有关哪组移动到达那里的信息.根据上下文,这可能是"慢"或"快"(如果在像GPU这样的并行计算设备上实现,则会非常快).

拥有所有到达那里的集合,您可以更快地计算路径,然后您可以选择从最少的移动到达目标的点,从您的查询或更进一步的子集中进行选择.

(感谢Strilanc)

Answer 2

我相信你能够广泛应用A*(又名A星)路径寻找算法.没有理由不能在第N个空间完成.如果您可以描述每次行动的成本,那么它就是最佳路径.

http://en.wikipedia.org/wiki/A*_search_algorithm

Answer 3

因此,您希望找到您的向量集的子集,以便子集求和到给定值.在1维中,这称为子集和问题,并且是NP-Complete.

幸运的是,你只有~10个向量,所以你的问题大小实际上非常小而易于处理.首先尝试为每个起点尝试所有2 ^ 10个移动组合并选择最佳的一个.然后从那里寻找简单的优化.

一些可能有效的简单优化:

• 优先搜索包含指向正确方向的向量的子集.
• 会合的中间人.使用哈希表来存储使用移动集的前半部分的子集可到达的所有点,并查看是否可以使用从结尾开始的移动集的后半部分来命中任何点.
• 倒退.您只有一个端点,因此从那里哈希所有可到达的起点,然后检查所有可能的起点.
• 并发