Содержание
- 2. СОДЕРЖАНИЕ Текущий контроль знаний. Задача коммивояжера и ее решение перебором.
- 3. Текущий контроль знаний
- 4. Содержательные постановки задач коммивояжера 1. Разомкнутая постановка задачи: коммивояжер должен объехать все n городов, побывав в
- 5. Графовая интерпретация замкнутой задачи коммивояжера 1 2 7 4 3 5 6 Гамильтонов контур а1=1,2,3,4,7,5,6,1 -.
- 6. Обозначения и определения
- 7. Формальная постановка аддитивной замкнутой задачи коммивояжера
- 8. Формальная постановка аддитивной разомкнутой задачи коммивояжера
- 9. Формальная постановка минимаксной разомкнутой задачи коммивояжера Самостоятельно: дать формальную постановку минимаксной замкнутой задачи коммивояжера.
- 10. Графовая интерпретация разомкнутой задачи коммивояжера 1 2 7 4 3 5 6 L1=1,2,3,4,7,5,6 -. L2=5,3,4,6,1,2,7 -.
- 11. Переход от разомкнутой к замкнутой задаче коммивояжера 1 3 2 4 4 3 2 1 0
- 12. Решение разомкнутой задачи коммивояжера перебором всех перестановок 1 3 2 4 9 5 3 7 4
- 13. ПРИНЦИП РАБОТЫ ГЕНЕРАТОРА ПЕРЕСТАНОВОК
- 14. АЛГОРИТМ РАБОТЫ ГЕНЕРАТОРА ПЕРЕСТАНОВОК 1 Ввод n 2 M(i)=i; i=1,2,3,…, n 5 M(n)=M(n)+1 Да Нет Получена
- 15. ДОСТОИНСТВА И НЕДОСТАТКИ АЛГОРИТМА ГЕНЕРАЦИИ ПЕРЕСТАНОВОК Достоинства: Генерация всех n! перестановок. Простота алгоритма. Легкость программной реализации.
- 16. Выделение всех контуров на орграфе алгоритмом Неметри 1 4 3 2 3 2 4 7 7
- 17. РЕШИТЬ САМОСТОЯТЕЛЬНО Найти перебором решение минимаксной разомкнутой задачи коммивояжера на графе G(X,U) при условии, что стартовой
- 19. Скачать презентацию