寻找路径组合的算法？

Question

假设你有一个在n维欧几里得空间中起点为原点P_0=(0,0,...,0)的舞蹈机器人。

这个机器人可以执行m种不同的舞蹈动作D_1, D_2, ..., D_m。

D_i是一个由n个整数组成的向量(D_i_1, D_i_2, ..., D_i_n)。

如果机器人执行了第i个舞蹈动作，它的位置将会发生改变:

P_{t+1} = P_t + D_i

机器人可以随意多次执行任何一种舞蹈动作，并且可以按照任意顺序执行。

定义一个k-dance为k个舞蹈动作的序列。

很明显，总共有m^k种可能的k-dances。

我们想知道所有可能的k-dance结束时的位置集合，并且对于每个结束位置，有多少个k-dance在该位置结束。

一种实现方法如下:

P0 = (0, 0, ..., 0);

S[0][P0] = 1

for I in 1 to k
    for J in 1 to m
        for P in S[I-1]
            S[I][P + D_J] += S[I][P]

现在，S[k][Q] 将会告诉你有多少个 k-dances 结束于位置 Q。

假设 n、m、|D_i| 都很小（小于 5），并且 k 小于 40。

有没有更快的方法？我们能否通过一些线性代数相关技巧或其他方法“直接”计算 S[k][Q] 呢？

- Andrew Tomazos

---

在n维欧几里得空间中，跳舞机器人加1。 - Reinstate Monica -- notmaynard

你尝试过使用规则并让HMM为您处理吗？？您认为它在您的情况下适用吗？？ - mamdouh alramadan

Answer 1

由于舞蹈动作是可互换的，因此您可以假设对于 i < j，机器人在进行 D_j 动作之前会先完成所有的 D_i 动作，从而减少实际计算的组合数。

如果您跟踪每个舞蹈动作的使用次数，则计算总组合数应该很容易。

- Jens Schauder

---

在我的示例算法中，S[i] 是基于 S[i-1] 计算的。每个 S[i] 都是位置向量（在时间 i）的直方图。使用您的方法来计算此直方图中的一个条目，我只能得到非递减序列的计数（而不是任何序列）。最终，如何将这些非递减序列的计数转换为所需的任何序列的计数，考虑到每个条目都是许多不同的非递减序列的混合？ - Andrew Tomazos

不仅要记录结束位置和路径数量，还需要跟踪每个舞步（N_i）的使用次数。到达该位置的组合总数为k！/ Sum（N_i！）。 - Jens Schauder

在S[t][p]的每个元素处，有(t+m+1 choose m)种可能的组合。因此，这将增加所需的存储和性能，乘以这个数量？因此，这不比我最初建议的算法更糟吗？ - Andrew Tomazos

我不理解那个论点。我认为只有在P_x的数量可以被不同的D_y组合到达时，存储才会显著增加。因为它们必须作为不同的直方图进行维护，而在您的算法中，它们存储在一个节点中。另一方面，您需要计算的组合较少，这应该在k >> m时产生最显着的影响。因此，我期望在k >> m时我的算法更有效，而在k << m时您的算法更有效。 - Jens Schauder

Answer 2

您可以创建一个邻接矩阵，其中包含您空间中的舞蹈移动转换（在可达到的k步内的部分，否则它将是无限的）。然后，此矩阵的n次幂的P_0行包含S[k]值。

所讨论的矩阵很快变得巨大，大约为(k*(max(D_i_j)-min(D_i_j)))^n（如果Q靠近原点，则每个维度都可以减半），但对于您的S矩阵也是如此。

- voidengine

Answer 3

由于一维问题与子集和问题密切相关，您可能可以采用类似的方法——找到所有舞蹈向量的组合，使它们的第一个坐标恰好需要k步移动才能相加得到正确的结果；然后取这个组合的子集，并检查其中哪些组合的和是正确的第二个坐标，再取匹配两者的子集并检查它是否符合第三个坐标，以此类推。

通过这种方式，您至少只需执行非常简单的加法操作来完成极其痛苦的O(n^k)步骤。它确实会找到所有能够达到给定值的向量。

- argentage

---

当你说要将它们相加以获得正确的第一个值P_0_0时，P_0_0是什么？我已经将P_0定义为零向量和原点。你是指P_0吗？ - Andrew Tomazos

假设您指的是 P_0，我如何找到所有相加得到 P_0 的舞蹈向量组合？ - Andrew Tomazos

该页面描述的伪多项式时间算法非常类似；您的优势在于可以用于达到总和的元素数量被精确地限制为k。 - argentage

对不起，我的意思是给定结束位置的第一个坐标。 - argentage