11

origin =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ダンスを一連のk ダンス ムーブとして定義するとします。

明らかにm^k可能な k ダンスがあります。

k-dance の可能な終了位置のセットと、各終了位置について、その位置で終了する k-dance の数を知りたいと考えています。

これを行う 1 つの方法は次のとおりです。

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]で、位置 Q で終了する k ダンスの数がわかります

n、m、|D_i|は小さく (5 未満) k、40 未満であると仮定します。

もっと速い方法はありますか？S[k][Q]ある種の線形代数関連のトリックを使用して、何らかの方法で「直接」計算できますか? または他のアプローチ？

4

3 に答える 3

1

ダンスの動きは交換可能であるためi < j、ロボットの場合、動きのD_i前に最初にすべての動きを行いD_j、実際に計算する組み合わせの数を減らすことができます。

各ダンスの動きが行われた回数を追跡する場合、組み合わせの総数を計算するのは簡単です。

于 2013-01-04T10:40:31.970 に答える
1

1次元問題は部分和問題と密接に関連しているため、おそらく同様のアプローチを取ることができます。正確にk個の動きで正しい最初の座標を持つように加算されるダンスベクトルのすべての組み合わせを見つけます。次に、その組み合わせのサブセットを取得し、そのうちのどれが2番目の正しい合計を持っているかを確認し、両方に一致するサブセットを取得して3番目の組み合わせを確認します。

このようにして、少なくとも、非常に苦痛なO（n ^ k）ステップに対して非常に単純な追加を実行するだけで済みます。それは確かに与えられた値に当たるすべてのベクトルを見つけるでしょう。

于 2013-01-03T19:01:01.793 に答える
1

空間内のダンス移動トランジションを含む隣接行列を作成できます (k 回の移動で到達可能な部分、そうでない場合は無限になります)。次に、この行列の n 乗の P_0 行に S[k] 値が含まれます。

問題の行列はすぐに巨大になります(Q が原点に近い場合、すべての次元を半分にすることができます) が、それは行列にも(k*(max(D_i_j)-min(D_i_j)))^n当てはまりますS

于 2013-01-03T17:21:26.290 に答える