№ 18 (277), выпуск 12Страницы 53 - 76

Одна параллельная процедура построения функции Беллмана в обобщенной задаче курьера с внутренними работами

А.Г. Ченцов
Рассматривается одна конструкция параллельной реализации метода динамического программирования для решения задачи последовательного обхода множеств (мегаполисов) с ограничениями в виде условий предшествования, именуемая обобщенной задачей курьера; предполагается, что на множествах должны выполняться работы, сопровождаемые затратами. Исследуется вычислительная процедура, предусматривающая частичное построение массива значений функции Беллмана и реализуемая на системе слоев пространства позиций. В основе конструкции находится модель дискретной динамической системы, для которой конструируются области достижимости, реализуемые по рекуррентной схеме.
Полный текст
Ключевые слова
маршрут, мегаполис, динамическое программирование.
Литература
1. Ченцов, А.А. Экстремальная задача маршрутизации с внутренними потерями / А.А. Ченцов, А.Г. Ченцов, П.А. Ченцов // Тр. Ин-та математики и механики УрО РАН. - 2008. - Т.,14, № 3. - С. 183-201.
2. Ченцов, А.Г. Об оптимальной маршрутизации в условиях ограничений / А.Г. Ченцов // Докл. Акад. наук. - 2008. - Т.,423, № 3. - С. 303-307.
3. Ченцов, А.А. Экстремальная задача маршрутизации перемещений с ограничениями и внутренними потерями / А.А. Ченцов, А.Г Ченцов, П.А. Ченцов // Изв. вузов. Математика. - 2010. - № 6. - С. 64-81.
4. Ченцов, А.Г. Метод динамического программирования в экстремальных задачах маршрутизации с ограничениями / А.Г. Ченцов // Известия РАН. Теория и системы управления. - 2010.- № 3.- С. 61-73.
5. Ченцов, А.А. Условия предшествования в одной задаче экстремальной маршрутизации с внутренними работами / А.А. Ченцов, А.Г. Ченцов, П.А. Ченцов // Алгоритмы и программные средства параллельных вычислений. - 2010. - Вып 10. - С. 60-76.
6. Ченцов, А.Г. Экстремальные задачи маршрутизации и распределения заданий: вопросы теории / А.Г. Ченцов. - М.: Ин-т компъютерных исследований, 2008. - 240 с.
7. Меламед, И.И. Задача коммивояжера. Вопросы теории / И.И. Меламед, С.И.Сергеев, И.Х. Сигал // Автоматика и телемеханика. - 1989.- № 9.- С. 3-34.
8. Меламед, И.И. Задача коммивояжера. Точные алгоритмы / И.И. Меламед, С.И.Сергеев, И.Х. Сигал // Автоматика и телемеханика.- 1989.- № 10.- С. 3-29.
9. Меламед, И.И. Задача коммивояжера. Приближенные алгоритмы / И.И. Меламед, С.И.Сергеев, И.Х. Сигал // Автоматика и телемеханика. - 1989.- № 11.- С. 3-26.
10. Гэри М. Вычислительные машины и труднорешаемые задачи / М. Гэри, Д. Джонсон. - М.: Мир, 1982.- 416 c.
11. Беллман, Р. Применение динамического программирования к задаче о коммивояжере / Р. Беллман // Кибернетический сборник. - М.: Мир, 1964.- Т.,9.- С. 219-228.
12. Хелд, М. Применение динамического программирования к задачам упорядочения / М. Хелд, Р.М. Карп. // Кибернетический сборник. - М., 1964.- Т.,9. - С. 202-218.
13. Использование метода динамического программирования для оптимизации траектории перемещения работников в радиационно опасных зонах с целью минимизации облучения / А.Н. Сесекин, О.Л. Ташлыков, С.Е. Щеклеин, М.Ю. Куклин, А.Г. Ченцов, А.А. Кадников // Изв. вузов. Ядерная энергетика.- 2006. - № 2. - С. 41-48.
14. Разработка оптимальных алгоритмов вывода АЭС из эксплуатации с использованием методов математического моделирования / О.Л. Ташлыков, А.Н. Сесекин, С.Е. Щеклеин, А.Г. Ченцов // Изв. вузов. Ядерная энергетика. - 2009. - № 2. - С. 115-120.
15. Куратовский, К. Теория множеств / К. Куратовский, А. Мостовский. - М.: Мир, 1970.
16. Кормэн, Т. Алгоритмы: построение и анализ / Т. Кормэн, Ч. Лейзерсон, Р. Ривест. - М.: МЦНМО, 1990. - 960 с.
17. Варга, Дж. Оптимальное управление дифференциальными и функциональными уравнениями / Дж. Варга.- М.: Наука, 1977.- 624 с.
18. Красовский, Н.Н. Теория управления движением / Н.Н. Красовский.- М.: Наука, 1968. - 475 с.
19. Панасюк, А.И. Асимптотическая магистральная оптимизация управляемых систем / А.И. Панасюк, В.И. Панасюк.- Минск: Наука и техника, 1986.- 296 с.