UPD. Я решил проблему.
Пусть DP[i][vertex_a][vertex_b] - это состояние с посещенными городами i, и два игрока, стоящих в вершинах vertex_a, vertex_b (гарантируется, что один из них стоит в list[i]). WLOG предполагает vertex_a ≤ vertex_b, так как эта таблица DP не несет информацию о позициях игроков. Доступно только три состояния от DP[i][vertex_a][vertex_b], а именно DP[i + 1][vertex_a][vertex_b], DP[i + 1][list[i]][vertex_b], DP[i + 1][vertex_a][list[i]]. Нам также нужно хранить только два слоя DP, поэтому для вычисления оптимальной стоимости пути требуется только sizeof(int) * 2 * 200 * 200 байтов. Чтобы получить путь, будет last_move_id[i][vertex_a][vertex_b], несущий информацию о игроке, который сделал перемещение в состоянии DP[i][vertex_a][vertex_b] и last_move_positions[i][vertex_a][vertex_b], сохраняя количество вершин, из которых игрок достиг list[i]. Поскольку число вершин не превышает 200, сохраните их, чтобы сохранить их как byte, поэтому sizeof(byte) * 1000 * 200 * 200 байтов для каждого массива. Чтобы поддерживать эти массивы, должен быть другой массив positions[i][vertex_a][vertex_b][3], содержащий информацию о позиции каждого игрока, нужны только последние два слоя, поэтому sizeof(byte) * 2 * 200 * 200 * 3 байты для этого. Сложность времени O(N * L * L).
В моей реализации C++ используются 76Mb и 320 ms.
Я борюсь со следующей проблемой конкурентного программирования от российского онлайн-судьи http://informatics.mccme.ru/moodle/mod/statements/view.php?chapterid=3379. Согласно правилам, я должен указать источник проблемы, насколько я помню.
К сожалению, нет английской версии веб-сайта, поэтому я попытаюсь описать проблему.
Вход состоит из полного орграфа
Gс вершинамиLи некоторого списка вершин (длина не болееN). Три человека начинаются с вершин1, 2, 3соответственно. Они должны посещать каждую вершину из входного списка, вопросы порядка, вершинаi + 1обязательно посещается послеi. В какой-то момент только один человек может сделать ход (если один человек перейдет от какой-либо предыдущей вершины к вершинеi, другие остаются на месте, они не могут двигаться параллельно). Если человек/игрок стоит в вершинеiи должен перейти в вершинуj, он должен взять ребро(i, j)вместо кратчайшего пути к вершине j (алгоритм Флойда-Варшалла не может использоваться для ускорения вычислений здесь), Достаточно, чтобы вершина была посещена одним человеком, что означает, что все они могут быть посещены человеком 1, в то время как другие будут стоять на месте. Стоимость края(i, i)всегда0, не существует многогранников, все реберные веса неотрицательны, аGпредставляется какL x Lматрица смежности. Выведите стоимость кратчайшего пути для этих трех людей, чтобы посещать вершины из списка amd, какой человек посещал каждую вершину. Список входных данных для посещений - это мультимножество (Nможет быть больше, чемL)
Я нашел эту проблему несколько похожей на проблему Two-Person Traversal of the Sequence of Cities, за исключением того, что это версия из трех человек, и они начинаются с разных позиций и имеют большое различие, что люди должны посетить определенную последовательность вершины с допустимыми повторениями. Я исследовал решения этой проблемы, и временная сложность была бы O(L^3)
для двухстороннего обхода последовательности городов, и для моей проблемы было бы O(N^4), что слишком медленно, так как даже алгоритм O(N^3) не будет соответствовать временным рамкам, я думаю, что что-то вроде O(LN^2) могло бы работать.
Ограничения:
3 ≤ L ≤ 200, 1 ≤ N ≤ 1000
0 ≤ вес края ≤ 2000
Ограничение по времени: 1 с, ограничение памяти - 256 МБ
Я также точно знаю, что эту проблему можно решить, используя 64 Мб.
Эта проблема помечена как 2D dynamic programming.
Я не могу придумать эту точную динамику 2D. Я подумал о довольно простом решении этой проблемы:
Исходное состояние трех человек - (1, 2, 3). При обработке первой вершины мы вычисляем:
1:(list[1], 2, 3) = (1, 2, 3) + weight(1, list[1])
1:(1, list[1], 3) = (1, 2, 3) + weight(2, list[1])
1:(1, 2, list[1]) = (1, 2, 3) + weight(3, list[1]).
Как можно видеть, это динамическая таблица 4D, но я думаю, что сохранить число текущей итерации ненужным, превратив ее в 3D one. Более того, можно заметить, что для вычисления (i + 1) -го уровня требуется только информация о i-м, что делает его отличной оптимизацией памяти. Тем не менее, если мы забудем, что на графике имеется только не более 200 вершин, и мы думаем о состояниях как кортежи (i, j, k), где i, j, k - числа игроков последней ступени 1, 2, 3, сделанных с шагом, что означает что на m-м этапе один из i, j, k равен m. Следуя этой логике и рассматривая все возможные повторения, количество явных наборов на m-й стадии:
Number_at_stage(m) = Number_at_stage(m - 1) + 6 * (m - 1), Number_at_stage(1) = 3, Number_at_stage(2) = 9, Number_at_stage(1000) = 2991009.
Number_at_stage(1) Я получил следующие мысли:
(0, 0, 0) -> (1, 0, 0), (0, 1, 0), (0, 0, 1)
Я суммировал количество отдельных кортежей на этапах 1..1000 и получил ужасное количество 997004997, которое составляет почти миллиард. Это означает, что количество отдельных кортежей, представляющих такие движения, асимптотически кубическое (не удивительно, но очевидно). Я не понимаю, как улучшить идею. Думая таким образом, я не знаю, как работать с такими состояниями, как (i, j, k) и (k, j, i), поскольку они фактически эквивалентны в том, что один и тот же набор шагов может быть сделан на основе на этих. Я просто не знаю, как обрабатывать такие состояния и хранить информацию о том, что посетил человек в каком городе (простой многомерный массив?).
Моя следующая мысль заключалась бы в том, чтобы иметь двумерный DP (i, j), сохраняющий оптимальную сумму расстояний для подписок с элементами из я в j. Ответ будет сохранен в DP (1, N), если индексирование идет от 1. Я могу вычислить все подмножества длины 1, 2,... N. Существует большая проблема с этой идеей, я не знаю, как обрабатывать DP (i, j), не зная всех потенциальных позиций, на которых могут стоять игроки (все элементы из списка, идущие до я и начальные позиции 1, 2, 3). Я также не знаю, как определить, какой игрок сделал ход с помощью этого подхода.
Не могли бы вы мне помочь найти 2D-динамику?
