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

Рассматривается одна конструкция параллельной реализации метода динамического программирования для решения задачи последовательного обхода множеств (мегаполисов) с ограничениями в виде условий предшествования, именуемая обобщенной задачей курьера; предполагается, что на множествах должны выполняться работы, сопровождаемые затратами. Исследуется вычислительная процедура, предусматривающая частичное построение массива значений функции Беллмана и реализуемая на системе слоев пространства позиций. В основе конструкции находится модель дискретной динамической системы, для которой конструируются области достижимости, реализуемые по рекуррентной схеме.

Ключевые слова

маршрут, мегаполис, динамическое программирование.

Литература

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 с.