Обзор вариаций метода динамического програмирования для задач маршрутизации и теории расписаний с ограничениями в виде условий предшествования

С начала 2000х годов в отделе исследуются задачи маршрутизации с ограничениями в виде условий предшествования; для поиска точных решений применяется особая модификация метода динамического программирования, разработанная А.Г. Ченцовым и соавторами, которая позволяетисключить обработку списков заданий, не удовлетворяющих условиям предшествования. Похожие методы предлагались для менее общих постановок маршрутной задачи (без зависимости функций стоимости от списка заданий и рассмотрения мегаполисов) ранее: (Schrage, Baker, 1978) и (Lawler, 1979). Доклад посвящен сравнению данных алгоритмов с тем, который применяется в отделе. Данная задача представляет интерес, поскольку для алгоритмов Щреге–Бейкера и Лоулера известны (Steiner, 1990) оценки пространственной и комбинаторной сложности. Первое является особо важным, так как чаще всего с ростом размерности динамическое программирование «упирается» именно в объем доступной памяти.