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