Одна параллельная процедура построения функции Беллмана в обобщенной задаче курьера с внутренними работами
Автор: Ченцов Александр Георгиевич
Рубрика: Математическое моделирование
Статья в выпуске: 18 (277), 2012 года.
Бесплатный доступ
Рассматривается одна конструкция параллельной реализации метода динамического программирования для решения задачи последовательного обхода множеств (мегаполисов) с ограничениями в виде условий предшествования, именуемая обобщенной задачей курьера; предполагается, что на множествах должны выполняться работы, сопровождаемые затратами. Исследуется вычислительная процедура, предусматривающая частичное построение массива значений функции Беллмана и реализуемая на системе слоев пространства позиций. В основе конструкции находится модель дискретной динамической системы, для которой конструируются области достижимости, реализуемые по рекуррентной схеме.
Маршрут, мегаполис, динамическое программирование
Короткий адрес: https://sciup.org/147159140
IDR: 147159140 | УДК: 519.6
A parallel procedure of constructing Bellman function in the generalized courier problem with interior works
A construction of the parallel realization of dynamic programming method for solving the problem of sequential visiting for sets (megalopolises) with constraints in the form of preceding conditions; this problem is called generalized courier problem. It is supposed that, on these sets, the works with inputs are fulfilled. The computing procedure used partial constructing of the Bellman function array and realized by layers of the position space is investigated. In the foundation of construction the idea of a discrete dynamic system is situated; for this system, attainability domains realized by recurrence scheme are constructed.
Список литературы Одна параллельная процедура построения функции Беллмана в обобщенной задаче курьера с внутренними работами
- Ченцов, А.А. Экстремальная задача маршрутизации с внутренними потерями/А.А. Ченцов, А.Г. Ченцов, П.А. Ченцов//Тр. Ин-та математики и механики УрО РАН. -2008. -Т. 14, № 3. -С. 183-201.
- Ченцов, А.Г. Об оптимальной маршрутизации в условиях ограничений/А.Г. Ченцов//Докл. Акад. наук. -2008. -Т. 423, № 3. -С. 303-307.
- Ченцов, А.А. Экстремальная задача маршрутизации перемещений с ограничениями и внутренними потерями/А.А. Ченцов, А.Г Ченцов, П.А. Ченцов//Изв. вузов. Математика. -2010. -№ 6. -С. 64-81.
- Ченцов, А.Г. Метод динамического программирования в экстремальных задачах маршрутизации с ограничениями/А.Г. Ченцов//Известия РАН. Теория и системы управления. -2010.-№ 3.-С. 61-73.
- Ченцов, А.А. Условия предшествования в одной задаче экстремальной маршрутизации с внутренними работами/А.А. Ченцов, А.Г. Ченцов, П.А. Ченцов//Алгоритмы и программные средства параллельных вычислений. -2010. -Вып 10. -С. 60-76.
- Ченцов, А.Г. Экстремальные задачи маршрутизации и распределения заданий: вопросы теории/А.Г. Ченцов. -М.: Ин-т компьютерных исследований, 2008. -240 с.
- Меламед, И.И. Задача коммивояжера. Вопросы теории/И.И. Меламед, С.И.Сергеев, И.Х. Сигал//Автоматика и телемеханика. -1989.-№ 9.-С. 3-34.
- Меламед, И.И. Задача коммивояжера. Точные алгоритмы/И.И. Меламед, С.И.Сергеев, И.Х. Сигал//Автоматика и телемеханика.-1989.-№ 10.-С. 3-29.
- Меламед, И.И. Задача коммивояжера. Приближенные алгоритмы/И.И. Меламед, С.И.Сергеев, И.Х. Сигал//Автоматика и телемеханика. -1989.-№ 11.-С. 3-26.
- Гэри М. Вычислительные машины и труднорешаемые задачи/М. Гэри, Д. Джонсон. -М.: Мир, 1982.-416 с.
- Беллман, Р. Применение динамического программирования к задаче о коммивояжере/Р. Беллман//Кибернетический сборник. -М.: Мир, 1964.-Т. 9.-С. 219-228.
- Хелд, М. Применение динамического программирования к задачам упорядочения/М. Хелд, Р.М. Карп.//Кибернетический сборник. -М., 1964.-Т. 9. -С. 202-218.
- Использование метода динамического программирования для оптимизации траектории перемещения работников в радиационно опасных зонах с целью минимизации облучения/А.Н. Сесекин, О.Л. Ташлыков, С.Е. Щеклеин, М.Ю. Куклин, А.Г. Ченцов, А.А. Кадников//Изв. вузов. Ядерная энергетика.-2006. -№ 2. -С. 41-48.
- Разработка оптимальных алгоритмов вывода АЭС из эксплуатации с использованием методов математического моделирования/О.Л. Ташлыков, А.Н. Сесекин, С.Е. Щеклеин, А.Г. Ченцов//Изв. вузов. Ядерная энергетика. -2009. -№ 2. -С. 115-120.
- Куратовский, К. Теория множеств/К. Куратовский, А. Мостовский. -М.: Мир, 1970.
- Кормэн, Т. Алгоритмы: построение и анализ/Т. Кормэн, Ч. Лейзерсон, Р. Ривест. -М.: МЦНМО, 1990. -960 с.
- Варга, Дж. Оптимальное управление дифференциальными и функциональными уравнениями/Дж. Варга.-М.: Наука, 1977.-624 с.
- Красовский, Н.Н. Теория управления движением/Н.Н. Красовский.-М.: Наука, 1968. -475 с.
- Панасюк, А.И. Асимптотическая магистральная оптимизация управляемых систем/А.И. Панасюк, В.И. Панасюк.-Минск: Наука и техника, 1986.-296 с.
