Динамическое программирование в обобщенной задаче курьера с внутренними работами: элементы параллельной структуры
Аннотация
Рассматриваются вопросы, связанные с реализацией динамического программирования в задачах последовательного обхода мегаполисов, осложненной условиями предшествования и внутренними работами, осуществляемыми в пределах мегаполисов. Предложена схема построения усеченного (неполного) массива значений функции Беллмана, использующая параллельные вычисления и не проигрывающая в качестве. Предлагаемая процедура реализована на многопроцессорной вычислительной системе; распараллеливание реализуется на этапе построения слоев функции Беллмана.
Об авторах
Алексей Михайлович Григорьев
Институт математики и механики УрО РАН
Россия
Россия
Евгений Евгеньевич Иванко
Институт математики и механики УрО РАН
Россия
Россия
Александр Георгиевич Ченцов
Институт математики и механики УрО РАН
Россия
Россия
Список литературы
1. Меламед И.И., Сергеев С.И., Сигал И.X. Задача коммивояжера. Вопросы теории // Автоматика и телемеханика, 1989. №9. С. 3-34.
2. Меламед И.И., Сергеев С.И., Сигал И.X. Задача коммивояжера. Точные алгоритмы // Автоматика и телемеханика, 1989. №10. С. 3-29.
3. Меламед И.И., Сергеев С.И., Сигал И.X. Задача коммивояжера. Приближенные алгоритмы // Автоматика и телемеханика, 1989. №11. С. 3-26.
4. Беллман Р. Применение динамического программирования к задаче о коммивояжере // Кибернетический сборник. М.: Мир, 1964. Т. 9. С, 219-228.
5. Хелд М., Карп P.M. Применение динамического программирования к задачам упорядочения // Кибернетический сборник, М.: Мир, 1964. Т. 9. С. 202-218.
6. Сергеев С.И. Гибридные системы управления и динамическая задача коммивояжера // Автоматика и телемеханика, 2008. №1. С. 45-54.
7. Сигал И.X., Иванова A.П. Введение в прикладное дискретное программирование: модели и вычислительные алгоритмы. М.: Наука, 2007. С. 304.
8. Ченцов А.А., Чепцов А.Г., Чепцов П.A. Экстремальная задача маршрутизации с внутренними потерями / / Труды Института математики и механики УрО РАН. 2008. Т.14, №3. С. 183-200.
9. Ченцов А.Г. Об оптимальной маршрутизации в условиях ограничений // Доклады Академии Наук. 2008. Т.423, №3. С. 303-307.
10. Ченцов А.Г. Метод динамического программирования в экстремальных задачах маршрутизации с ограничениями // Известия РАН. Теория и системы управления. 2010. №3. С. 52-66.
11. Ченцов А.А., Ченцов А.Г., Ченцов П.А. Экстремальная задача маршрутизации перемещений с ограничениями и внутренними потерями // Известия вузов. Математика. 2010. № 6. С. 64-81.
12. Ченцов А.Г. Экстремальные задачи маршрутизации и распределения заданий: вопросы теории. М.; Ижевск: НИЦ "Регулярная и хаотическая динамика", Ижевский институт компьютерных исследований, 2008. 240 с.
13. Коротаева Л.П., Сесекин А.П., Ченцов А.Г. Об одной модификации метода динамического программирования в задаче последовательного сближения // Журн. вычисл. математики и мат, физики, 1989. Т. 29, № 8. С. 1107-1113.
14. Коротаева Л.Н., Назаров Э.М., Ченцов А.Г. Об одной задаче о назначениях // Журн. вычисл. математики и мат. физики, 1993. Т. 33, № 4. С. 483-494.
15. Ченцов А.А., Ченцов А.Г. О решении задачи маршрутной оптимизации методом динамического программирования / / Автоматика и телемеханика. 1998. № 9. С. 117-129.
16. Ченцов А.Г., Ченцов П.А. Маршрутизация с условиями предшествования (задача курьера): метод динамического программирования // Вестник УГТУ- УПИ. Екатеринбург, 2004. Ч. 1. №15 (45). С. 148-152.
17. Куратовский К., Мостовский А. Теория множеств. М.: Мир. 1970. 416 с.
18. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. М.: МЦНМО, 2000. 960 с.
19. Сесекин А.Н., Ташлыков О.Л., Щеклеин С.Е., Куклин М.Ю., Ченцов А.Г., Кадников А. А. Использование метода динамического программирования для оптимизации траектории перемещения работников в радиационно опасных зонах с целью минимизации облучения // Известия вузов. Ядерная энергетика. 2006. № 2. С. 41-48.
20. Ташлыков О. Л., Сесекин А.Н., Ченцов А. Г., Щеклеин С. К., Балушкин Ф. А., Хомяков А. П. Возможности математических методов моделирования в решении проблемы облучаемости персонала // Вопросы радиационной безопасности. 2009. № 4. С. 39-49.
21. Ташлыков О.Л., Сесекин А.Н.. Щеклеин С.Е., Ченцов А.Г. Разработка оптимальных алгоритмов вывода АЭС из эксплуатации с использованием методов математического моделирования // Известия вузов. Ядерная энергетика. 2009. № 2. С. 115-120.
Рецензия
Для цитирования:
Григорьев А.М., Иванко Е.Е., Ченцов А.Г. Динамическое программирование в обобщенной задаче курьера с внутренними работами: элементы параллельной структуры. Моделирование и анализ информационных систем. 2011;18(3):101-124.
For citation:
Grigoriev A.M., Ivanko E.E., Chentsov A.G. Dynamic Programming in a Generalized Courier Problem with Inner Tasks: Elements of a Parallel Structure. Modeling and Analysis of Information Systems. 2011;18(3):101-124. (In Russ.)
Просмотров: 384
Послать статью по эл. почте 