8

（这不完全是我遇到的问题，但它是同构的，我认为这种解释对其他人来说最容易理解。）

假设我在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 。效率被定义为“最少的移动次数”，不一定是“最小的线性距离”：如果移动集可以让您以更少的移动到达那里，则允许选择比其他候选者更远离dest的p 。move 中的向量必须是可用向量的严格子集；您不能多次使用同一个向量，除非它在输入集中出现多次。

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

使用已接受的解决方案进行更新

我采用了一种与下面标记为“已接受”的解决方案非常相似的解决方案。我遍历所有点和向量，并构建所有可到达点的列表以及到达它们的路线。我将此列表转换为 < dest , p+vectors > 的散列，为每个目标点选择最短的向量集。（还有一点对哈希大小的优化，这里不相关。）随后的dest查找在恒定时间内发生。

4

6 回答 6

6

实际上，考虑到您有大约 10 个向量，对于给定的目标点，您可以仅从向量子集中计算1024 个“目标” ——例如，每个可到达的空间，以及关于哪组移动到达那里的信息。这可能是“慢”或“快”，具体取决于上下文（如果在 GPU 等并行计算设备上实现，速度会快得离谱）。

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

（感谢斯特兰克）

于 2010-01-21T19:05:30.147 回答
5

我相信您将能够对 A*（又名 A 星）寻路算法进行广义应用。没有理由不能在第 N 个空间内完成。如果您可以描述每一步的成本，它可以保证最佳路径。

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

于 2010-01-21T19:03:42.380 回答
5

因此，您希望找到向量集的子集，使得该子集总和为给定值。在一维中，这称为子集和问题，并且是 NP-Complete。

幸运的是，您只有约 10 个向量，因此您的问题规模实际上非常小且易于处理。首先尝试每个起点的所有 2^10 移动组合，然后选择最好的移动组合。然后从那里开始寻找简单的优化。

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

  • 优先搜索子集，包括指向正确方向的向量。
  • 中间相遇。使用哈希表存储使用移动集前半部分的子集可到达的所有点，并查看是否可以使用移动集的后半部分从末端开始击中任何点。
  • 倒退。您只有一个端点，因此从那里散列所有可到达的起点，然后检查所有可能的起点。
  • 并发
于 2010-01-21T19:07:05.743 回答
2

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

于 2010-01-21T19:00:25.740 回答
1

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

您可以通过使用中间相遇解决方案将其优化为 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)) 的时间。

于 2010-01-21T20:37:18.393 回答
0
  1. 从头开始。
  2. 做一段时间
  3. 获取到目的地的距离
  4. 测试所有可能的动作，并选择一个让您一举接近目的地的动作。
  5. 结束做

这可能会在目的地周围摇摆不定，但它会让你靠近。

于 2010-01-21T19:05:04.993 回答