Содержание
- 2. Содержание лекции Постановка задачи коммивояжера. Построение модели (в терминах теории графов). Исчерпывающий алгоритм для задачи коммивояжера.
- 3. Полное построение алгоритма. Этапы: Постановка задачи. Построение модели решения (математической модели, аналога и т.д.). Разработка алгоритма.
- 4. Постановка задачи. Прежде, чем понять задачу её, необходимо четко сформулировать. Обычно процесс точной формулировки задачи сводится
- 5. Постановка задачи. Сформулируем постановку на примере. "Задача Коммивояжера". Агент по продаже компьютеров должен посетить 20 городов.
- 6. Постановка задачи Что дано? Исходная информация в виде перечня городов. Известно: Количество городов Стоимость переезда из
- 7. Постановка задачи. Что хотим найти? Как снизить дорожные расходы: найти такую последовательность объезда городов, что стоимость
- 8. Постановка задачи Дополнительная информация: Маршрут начинается и кончается в базовом городе и проходит по одному разу
- 9. Постановка задачи Что надо получить? Список городов, содержащий каждый город только один раз, (за исключением базового
- 10. Постановка задачи Что надо получить? Сумма стоимостей между каждыми двумя городами маршрута - это общая стоимость
- 11. Построение модели решения (математической модели, аналога и т.д.). Задача четко сформулирована, теперь необходимо составить для неё
- 12. Построение модели решения (математической модели, аналога и т.д.). Приступая к разработке модели, следует, по крайней мере,
- 13. Построение модели решения (математической модели, аналога и т.д.). Гаусс, Лейбниц, Эйнштейн? Ищем похожую задачу Что нужно
- 14. Построение модели решения (математической модели, аналога и т.д.). Модель построена, если можно утвердительно ответить на следующие
- 15. Построение модели для задачи коммивояжера Решали ли мы раньше подобные задачи? Вероятно, нет, однако мы сталкивались
- 16. Построение модели для задачи коммивояжера Точка - город. расстояние между каждой парой точек, соответствующих городам i
- 17. Построение модели для задачи коммивояжера Схема - частный случай известного в математике графа, или сети.
- 18. Обоснование модели В общем случае сеть — это множество точек (на плоскости) вместе с линиями, соединяющими
- 19. Обоснование модели. Представление графа в виде матрицы Для нашей задачи рассмотрим представление графа в виде матрицы
- 20. Матрица стоимостей для задачи коммивояжера
- 21. Модель для задачи коммивояжера Что ищем? В терминах теории графов список городов определяет замкнутый цикл, начинающийся
- 22. Модель для задачи коммивояжера Например, для рассматриваемого графа гамильтонов цикл 1 – 5 – 3 –
- 23. Разработка алгоритма. Выбор алгоритма зависит от выбранной модели. Два разных алгоритма могут быть правильными, но сильно
- 24. «Исчерпывающий алгоритм» решения задачи коммивояжера Произвольно пронумеруем города целыми числами от 1 до n. Базовому городу
- 25. Исчерпывающий алгоритм (ETS): Образуем перестановки первых n-1 чисел Выбираем первую перестановку, строим соостветствующий путь и вычисляем
- 26. Проверка правильности алгоритма. Это один из наиболее трудных этапов. Проверка правильности алгоритма часто заменяется проверкой правильности
- 27. Проверка правильности алгоритма. Для большинства алгоритмов очень сложно составить систему тестов, проверяющую все особенности, тонкости работающей
- 28. Методика доказательства правильности алгоритма. Предположим, что алгоритм описан в виде последовательности шагов: от шага 1 до
- 29. Доказательство для алгоритма «задачи коммивояжера». Проверяется каждый цикл. При этом будет проверен и цикл с минимальной
- 31. Скачать презентацию