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

Question

假设我在一个n维空间中有一组点。以三维为空间为例：

（这不是我所遇到的确切问题，但同构，并且我认为这个解释对其他人来说最容易理解。）

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。 moves中的向量必须是可用向量的严格子集；除非它在输入集合中出现多次，否则不能重复使用相同的向量。

我的输入包含约100个起始点和大约10个向量，我的维数为20左右。起始点和可用向量将固定应用程序的生命周期，但我将为许多不同的dest点寻找路径。我想优化速度，而不是内存。算法无法找到到dest的可能路径是可以接受的。

采纳的解决方案更新

我采用了与下面标记为“已接受”的解决方案非常相似的解决方案。我遍历所有点和向量，并构建到达它们的所有可达点列表。我将此列表转换为<dest，p+向量>的哈希表，选择每个目标点的最短向量集。（这里还有一些哈希表大小的优化，但与本题无关。）随后的dest查找在常数时间内完成。

- JSBձոգչ

---

实际上，考虑到您的限制，从100个起始点出发，您大约有1024个可能到达的位置，因此有大约十万个可能的目的地（这些可能不是唯一的）。在这里，预先计算成哈希表可能会起作用。 - David Thornley

我认为你在引号中的介绍性括号中并不是指“正交”。 - Svante

@Svante，你是对的。更正为“同构”。 - JSBձոգչ

每个维度的范围是多少？ - klochner

Answer 1

实际上，考虑到您有大约10个向量，对于给定的“dest”点，您可以仅从向量子集中计算出1024个“目标”，例如每个可到达空间以及到达那里所需的移动集合信息。这可能会根据上下文而变得“慢”或“快”（如果在像GPU这样的并行计算设备上实现，则速度非常快）。

拥有所有到达目的地的集合后，您可以更快地计算路径，然后从您的查询或更远的子集中选择最少移动的起点以到达“dest”。

（感谢Strilanc）

- Kornel Kisielewicz

---

你需要使用动态规划方法来解决这个问题。 - klochner

@klochner 请解释你的理由。如果尺寸和范围很大，那会占用很多内存（因此也会花费更多时间）。1024个目的地基本算不了什么。 - moinudin

仔细考虑了一下，你是对的——直接计算所有和（102420）并检查匹配（在最坏情况下为102420*100）会更快。 - klochner

我唯一看到的问题是，随着我添加的每个向量，搜索时间呈指数增长。向量数量大约为10个，但可能会增加到20或30个，这将使此算法的性能急剧下降。 - JSBձոգչ

不是搜索时间呈指数增长 - 而是可达性表的生成时间，这可以提前完成（因为它仅取决于向量和起始点，这些都是固定的）。通过该表进行搜索的时间甚至可以变为O（1），因为您可以构建一个完美的哈希（因为表内容是固定的）。 - caf

Answer 2

我相信您可以将A*（也称为A星）路径查找算法进行泛化应用。在Nth空间中，它同样适用。只要您能描述每次移动的成本，它就保证了最优路径。 http://en.wikipedia.org/wiki/A*_search_algorithm

- Matt

---

考虑到你有一组动作，距离并不是一个好的近似值。 - Kornel Kisielewicz

@Kornel，我不太确定我理解了。 - Matt

@Matt -- A算法的启发式是基于距离的 -- 如果你只走单步，那么这个算法效果很好 -- 但在这里，移动更像象棋中的马 -- 更糟糕的是，它只有几步就结束了。简而言之 -- “击中”目标比“接近”目标更困难。第一步解决方案可能会把你带“远离”目标 -- 这可能是唯一的解决方案。A算法将遍历整个可能性树。更不用说，要判断路径是否不可行，你仍然需要遍历整个树 -- 启发式算法在这里并没有太大的帮助。 - Kornel Kisielewicz

@Kornel A* 启发式算法基于成本，通常实现的成本是距离。但这并不一定是唯一的选择——成本可以是你想要的任何东西。而且，如果已经找到了解决方案，就没有必要遍历整棵树。A* 算法类似于广度优先搜索，因此当到达目标时就会停止，而且保证是最有效率的。你可以放弃所有未访问的路径，因为你已经知道它们的成本更高。如果没有解决方案，你将不得不遍历整棵树，但我想不出有哪个算法能够避免这种情况。 - Matt

他们的意思是对于任何给定的点，你没有一个好的启发式来估计到达目标的总路径长度。你的启发式将是现有的路径长度，也就是广度优先搜索。 - klochner

Answer 3

所以，您想找到一个向量子集，使得该子集的总和等于给定的值。在一维中，这被称为子集和问题，是NP-完全问题。

幸运的是，您只有大约10个向量，因此您的问题规模实际上相当小且可处理。首先尝试针对每个起点尝试所有2^10个移动组合并选择最佳组合。然后从那里开始寻找简单的优化方法。

可能有效的一些简单优化方法：

• 优先搜索包括指向正确方向的向量的子集。
• 中途相遇法。使用哈希表存储可以使用前半部分移动集的子集到达的所有点，并查看是否可以使用后半部分移动集从末尾开始到达任何点。
• 向后搜索。由于只有一个端点，因此从那里哈希所有可到达的起始点，然后检查所有可能的起始点。
• 并发

- Craig Gidney

---

2的10次方？你的数学搞错了；> -- 记住向量可以按不同顺序排列，这给我们带来了10！= 3628800。 - Kornel Kisielewicz

向量加法是可交换的，顺序不会影响最终结果。 - Craig Gidney

然而，如果解决方案集很小，那么它仍然是一个很大的改进。 - Kornel Kisielewicz

在计算过程中，您当然会跟踪这些信息。您不仅存储可到达点，还存储可到达点和它们的成本的元组。 - Craig Gidney

你正在通过暴力方法（或一些简单的启发式算法）解决线性规划问题。这种方法在任何线性规划求解器面前都是不堪一击的。 - klochner

Answer 4

假设您拥有起始点和一组固定的向量，您能计算出所有可到达目的地的列表，然后只需查找给定的目的地吗？

- Chris Hulan

Answer 5

正如Kornel所说，您最多有2^10 = 1024个可达目的地。因此，您可以通过简单的递归生成在2^N时间内（其中N是向量数量）生成所有可达目的地。当然，这将足够快。但是，假设您想要将其扩展。

您可以通过使用meet-in-the-middle解决方案将其优化为O(2^(N/2+1))时间。您将向量集拆分为两个子集，并独立地生成每个子集的所有可达目的地。然后，您遍历一个可达目的地集，并针对每个位置找到它与目标目的地之间的差异。如果该差异向量在另一个可达目的地集中，则您就有了一个解决方案：将两者合并即可完成。这里的难点在于有效地查询是否在另一个集合中具有所需的向量：可以使用哈希表在O(1)时间内完成此操作。

每个子集的时间复杂度为O(2^(N/2))，两个子集的时间复杂度为O(2^(N/2+1))。将两者合并的时间复杂度为O(2^(N/2))。因此，总时间复杂度为O(2^(N/2+1))。

- moinudin

Answer 6

1. 从起点开始。
2. 循环一段时间
3. 获取到目的地的距离
4. 测试所有可能的移动并选择一个可以在一步内最接近目的地的移动。
5. 结束循环

这可能会在目的地周围摆动，但它会让你靠近目标。

- xpda