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