Одна параллельная процедура построения функции Беллмана в обобщенной задаче курьера с внутренними работами
Автор: Ченцов Александр Георгиевич
Рубрика: Математическое моделирование
Статья в выпуске: 18 (277), 2012 года.
Бесплатный доступ
Рассматривается одна конструкция параллельной реализации метода динамического программирования для решения задачи последовательного обхода множеств (мегаполисов) с ограничениями в виде условий предшествования, именуемая обобщенной задачей курьера; предполагается, что на множествах должны выполняться работы, сопровождаемые затратами. Исследуется вычислительная процедура, предусматривающая частичное построение массива значений функции Беллмана и реализуемая на системе слоев пространства позиций. В основе конструкции находится модель дискретной динамической системы, для которой конструируются области достижимости, реализуемые по рекуррентной схеме.
Маршрут, мегаполис, динамическое программирование
Короткий адрес: https://sciup.org/147159140
IDR: 147159140
Список литературы Одна параллельная процедура построения функции Беллмана в обобщенной задаче курьера с внутренними работами
- Ченцов, А.А. Экстремальная задача маршрутизации с внутренними потерями/А.А. Ченцов, А.Г. Ченцов, П.А. Ченцов//Тр. Ин-та математики и механики УрО РАН. -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 с.
