代码之家 › 专栏 › 技术社区 › JSBÕ±Õ¸Õ£Õ¹

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

path-finding language-agnostic algorithm

JSBÕ±Õ¸Õ£Õ¹ · 技术社区 · 15 年前

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

假设我在 n -空间维度。使用3个维度,例如:

A : [1,2,3]
B : [4,5,6]
C : [7,8,9]

我也有一组向量来描述这个空间中可能的运动:

V1 : [+1,0,-1]
V2 : [+2,0,0]

现在,给点理由最 ,我需要找到一个起点磷以及一组向量移动那会让我最以最有效的方式。效率被定义为“最少移动次数”,不一定是“最小线性距离”:允许选择磷离这儿远一点最比其他候选人,如果移动设置是这样,你可以在更少的移动。向量在移动必须是可用向量的严格子集;除非同一向量在输入集中出现多次,否则不能多次使用该向量。

我的输入包含大约100个起始点和大约10个向量,我的维数是大约20。在应用程序的整个生命周期中,起点和可用向量都是固定的,但我将为许多不同的对象寻找路径。最点。我想优化速度,而不是记忆。算法失败是可以接受的(找不到 目的地 )

使用接受的解决方案更新

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

6 回复 | 直到 15 年前

Kornel Kisielewicz 15 年前

实际上,考虑到你有大约10个向量,你可以最点,只计算 1024个“靶子” 从向量的子集——例如每个可到达的空间,以及关于哪一组移动到那里的信息。这可能是“慢”的,也可能是“快”的,这取决于上下文(如果在类似GPU的并行计算设备上实现的话,速度是荒谬的快)。

有了所有到达那里的集合,你可以更快地计算出路径,然后你可以选择要到达的点。最在最少的移动中,从查询或进一步查询的子集中进行选择。

(多亏了斯特里兰克)

Matt 15 年前

我相信您将能够对一个*(又名星)路径查找算法进行一般化的应用。没有理由不能在第N个空间中完成。如果你能描述每一步的成本,它是最理想的路径。

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

Craig Gidney Mihai 15 年前

所以你想找到向量集的一个子集,这样子集就等于一个给定的值。在一维中,这称为 subset sum problem ,并且是NP完全的。

幸运的是,您只有大约10个向量,所以您的问题大小实际上非常小,而且很容易处理。首先,尝试每个起点的所有2^10个移动组合,并选择最佳组合。然后从那里开始寻找简单的优化。

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

优先搜索子集,包括指向正确方向的向量。
在中间相遇。使用哈希表来存储使用移动集前半部分的子集可到达的所有点,并查看是否可以使用移动集后半部分从结尾开始命中任何点。
往后走。您只有一个端点,所以从那里散列所有可到达的起点,然后检查所有可能的起点。
并发性

Svante 15 年前

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

moinudin 15 年前

正如科内尔所说,您最多有2^10=1024个可到达的目的地。因此,您可以通过简单的递归生成,在2^n时间内生成所有可到达的目的地(其中n是向量数)。当然,这会足够快。不过,假设您想要拉伸它。

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

xpda 15 年前

从开始处开始。
做一段时间
到目的地的距离
测试所有可能的移动,并在一次移动中选择一个最接近目标的移动。
结束做

这可能会在目的地附近振荡,但它会让你靠近。