Варианты метода динамического программирования для маршрутных задач с условиями предшествования и «технические» вопросы их реализации на ЭВМ

Решение маршрутных задач с условиями предшествования методом динамического программирования (МДП) состоит в получении оптимального решения полной задачи из оптимальных решений всех существенных в смысле условий предшествования подзадач. Наиболее распространенные варианты МДП состоят в последовательном переборе этих подзадач и различаются, в первую очередь, способом организации перебора.
В одной из первых работ, посвященных методу динамического программирования (МДП) для задач с условиями предшествования, учитывавшей задачу курьера, (Lawler, 1979), предлагался «прямой» МПД c перебором существенных подзадач в порядке возрастания размерности: оптимальный маршрут строится с «головы» — первого элемента. Этот метод получил достаточно широкую известность, тем не менее, корректность этого метода доказана не была.
С середины 2000х годов в отделе управляемых систем А.Г. Ченцовым и соавторами развивается «попятный» МДП, впервые примененный для обобщенной задачи курьера, и затем распространенный на более общие маршрутные задачи, в котором перебор существенных подзадач также происходит в порядке возрастания размерности; см. (Ченцов, 2008). В рамках этого метода маршрут строится с «хвоста», последнего элемента; для этого варианта МДП корректность доказана. Мы докажем эквивалентность «прямой» и «попятной» процедур в смысле тождественности получаемых из них оптимальных маршрутов. Это доказательство открывает возможность непосредственного применения результатов о сложности «прямого» МДП (см., (Steiner, 1990)), а также обеспечивает корректность метода «разделяй и властвуй», предложенного в (Lawler, 1979) в качестве «представляющего теоретический интерес», на основе которого можно построить альтернативный способ параллелизации МДП.
Кроме того, мы рассмотрим «технические» вопросы реализации МДП:
1) Какие существуют подходы к эффективному построению существенные подзадач?
2) Какие структуры данных следует использовать для хранения значений функции Беллмана?