11

想象一下，你有一个跳舞的机器人，在从 origin =n开始的维欧几里得空间中。P_0(0,0,...,0)

机器人可以做出m各种舞蹈动作D_1, D_2, ..., D_m

D_i是n整数的 -vector(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-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]用某种与线性代数相关的技巧以某种方式“直接”计算吗？或其他方法？

4

3 回答 3

1

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

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

于 2013-01-03T17:21:26.290 回答
1

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

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

于 2013-01-04T10:40:31.970 回答
1

由于一维问题与子集和问题密切相关，您可能会采取类似的方法 - 找到所有舞蹈矢量的组合，它们加在一起以获得正确的第一个坐标，恰好有 k 个动作；然后获取该组合的子集并检查其中哪些具有正确的第二个和，并获取与两者匹配的子集并检查它的第三个，依此类推。

这样，您至少只需为极其痛苦的 O(n^k) 步骤执行一个非常简单的加法。它确实会找到所有将达到给定值的向量。

于 2013-01-03T19:01:01.793 回答