1 – 2 – 5–3: Верхняя оценка («жадный алгоритм»), определяемая суммарной стоимостью данного маршрута 1 ® 2 ® 5 ® 3 ® 4®1, равна 17. Нижняя оценка определяется суммой минимальных элементов строк с учетом того, что из 1го города идем в 2 ® 5® 3. Она равна 15.
1 – 2 – 5–4: Верхняя оценка («жадный алгоритм»), определяемая суммарной стоимостью данного маршрута 1 ® 2 ® 5 ® 4 ® 3®1, равна 16. Нижняя оценка определяется суммой минимальных элементов строк с учетом того, что из 1го города идем в 2й, из 2го в 5й. Она равна 13.
13/12
●
 |
 |
| |
В результате решения задачи, дальше ветвиться нам не куда. Запишем оптимальный маршрут коммивояжера:
1 ® 2 ® 5 ® 4 ® 3®1
Таким образом, задача решена.
Заключение
Практика порождает все новые и новые задачи оптимизации, причем их сложность растет. Требуются новые математические модели и методы, которые учитывают наличие многих критериев, проводят глобальный поиск оптимума. Другими словами, жизнь заставляет развивать математический аппарат оптимизации.
Реальные прикладные задачи дискретной оптимизации очень сложны. Современные методы оптимизации далеко не всегда справляются с решением реальных задач без помощи человека. Нет, пока такой теории, которая учла бы любые особенности функций, описывающих постановку задачи. Следует отдавать предпочтение таким методам, которыми проще управлять в процессе решения задачи.
Список использованных источников
1. Беллман, Р. Динамическое программирование – М.: ИЛ, 1960.– 400 с.
2. Беллман, Р. Прикладные задачи динамического программирования – М.: Наука, 1965. – 457 с.
3. Сигал И.Х., Иванова А.П. Введение в прикладное дискретное программирование: модели и вычислительные алгоритмы. М.: ФИЗМАТЛИТ, 2003. — 240 с.
4. Р. Беллман, С. Дрейфус Прикладные задачи динамического программирования – М., 1965 г., 460 стр.
