寻找路径组合的算法？

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不是其位置改变D_i:

P_{t+1} = P_t + D_i

机器人可以按照自己的意愿和任何顺序进行任何多次的舞蹈动作.

让k-dance定义为k舞蹈动作的序列.

很明显,有m^k可能是k-dances.

我们有兴趣知道k-dance的可能终点位置的集合,并且对于每个终点位置,在该位置处有多少k-dances结束.

一种方法是这样做:

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]用某种线性代数相关技巧"直接" 计算吗？或其他一些方法？

Answer 1

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

有问题的矩阵很快就会变得巨大，就像(k*(max(D_i_j)-min(D_i_j)))^n（如果 Q 接近原点，每个维度都可以减半），但这对于你的S矩阵来说也是如此