Представьте, что у вас есть танцевальный робот в 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-танца, а для каждой конечной позиции, сколько k-танцев заканчивается в этом месте.
Один из способов сделать это:
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-танцев заканчивается в позиции Q
Предположим, что n, m, |D_i| малы (меньше 5), а k меньше 40.
Есть ли более быстрый способ? Можно ли как-то вычислить S[k][Q] "каким-то образом связанным с линейной алгеброй трюком? или какой-либо другой подход?
Вы можете создать матрицу смежности, которая будет содержать переходы танцевального движения в вашем пространстве (та часть, которая достижима в k движется, иначе она будет бесконечной). Затем строка P_0 n-й степени этой матрицы содержит значения S [k].
Матрица, о которой идет речь, быстро становится огромной, что-то вроде (k*(max(D_i_j)-min(D_i_j)))^n (каждое измерение может быть уменьшено в два раза, если Q близко к началу), но это верно для вашей матрицы S, а также
Так как одномерная проблема тесно связана с проблемой суммой подмножества, вы, вероятно, можете воспользоваться аналогичным подходом - найти все комбинации векторов танца, которые складываются вместе, чтобы иметь правильную первую координату с точно k ходами; затем возьмите это подмножество комбинаций и проверьте, какая из них имеет правильную сумму для второго, и возьмите подмножество, которое соответствует обоим, и проверит его для третьего и т.д.
Таким образом, вы, по крайней мере, должны выполнить очень простое дополнение для чрезвычайно болезненного шага O (n ^ k). Он действительно найдет все векторы, которые попадут в заданное значение.
Так как танцевальные движения взаимозаменяемы, вы можете предположить, что при a i < j робот сначала перемещает все D_i перед движением D_j, тем самым уменьшая количество комбинаций для фактического вычисления.
Если вы отслеживаете количество попыток каждого танцевального движения, то общее количество комбинаций должно быть легким.