Я пытаюсь решить эту проблему на SPOJ:Идеи для SPOJ FISHER
http://www.spoj.pl/problems/FISHER/
Я не мог придумать решение для этого. Я нашел несколько потоков на topcoder, но я мог только предположить, что DP будет использоваться. Было бы очень полезно, если бы кто-нибудь мог направить меня на это.
Если вы используете динамическое программирование для решения обычных проблем с самым коротким контуром, вы получаете http://en.wikipedia.org/wiki/Bellman%E2%80%93Ford_algorithm. Конечно, это игнорирует временные ограничения. Вы всегда можете сделать алгоритм динамического программирования более гибким - ценой - путем расширения пространства состояний. В этом случае вместо отслеживания на каждом узле стоимости самого дешевого пути к этому узлу, найденного до сих пор, вы можете отслеживать, для i = 1,2,3,4 .. стоимости дешевого пути к узлу со временем к этому узлу не более i. Вы должны иметь возможность обновить этот массив затрат с помощью варианта рекурсии, используемой для расчета единой стоимости - каждая рекреационная релаксация принимает вектор самых дешевых затрат с учетом времени и учитывает добавление времени и стоимости этого края на каждом смещении, чтобы увидеть, результирующий расширенный путь лучше, чем самый известный путь, заканчивающийся до этого края.
Интересно, можно ли сэкономить время, преобразовывая алгоритм Дейкстры аналогичным образом? По крайней мере, вы можете запустить алгоритм Дейкстры сначала, вовремя, а затем отбросить все узлы с кратчайшим временным путем дольше, чем ваше ограничение по времени.
Использование динамического программирования.
Вы отслеживаете только путь к узлу, если все пути, которые занимают меньше времени, чем стоимость выше. Когда вы видите новый путь, вы можете использовать двоичный поиск, чтобы найти самый длинный путь времени, который является одним и тем же временем или короче, а затем добавить новый путь, только если он стоит меньше, чем тот, и не превысил лимит времени. Когда вы добавляете его, удалите все существующие пути, которые занимают больше времени и не дешевле.
Наконец, вы получите массив путей к окончательному узлу, который упорядочен по времени. Выберите самый дешевый, который подходит во временном ограничении.
Обратите внимание, что вы, вероятно, хотите, список задач узлов, чтобы рассмотреть, и узел может заводиться в этом списке TODO несколько раз (он обматывает назад на это каждый раз, когда вы находите новый дешевый путь к нему.)
Альтернативный способ решения проблемы - использовать алгоритм Дейкстры http://www.geeksforgeeks.org/greedy-algorithms-set-6-dijkstras-shortest-path-algorithm/. Ограничения: n<=50 и time<=1000. Пусть время задано = T. Таким образом, мы разберем каждый узел в T-узлах, в которых dist[node][i] представляет собой кратчайший путь к узлу в течение заданного времени i. Таким образом, мы будем запускать алгоритм на узлах n * T с краями n * n * T, которые будут в пределах заданных временных ограничений со сложностью O((n * T + n * n *T) * log(N * T)). Мое принятое решение: http://ideone.com/H8UUMf