🗊Презентация Полное построение алгоритма. Часть 1. Задача коммивояжера

Категория: Устройства и комплектующие
Нажмите для полного просмотра!
Полное построение алгоритма. Часть 1. Задача коммивояжера, слайд №1Полное построение алгоритма. Часть 1. Задача коммивояжера, слайд №2Полное построение алгоритма. Часть 1. Задача коммивояжера, слайд №3Полное построение алгоритма. Часть 1. Задача коммивояжера, слайд №4Полное построение алгоритма. Часть 1. Задача коммивояжера, слайд №5Полное построение алгоритма. Часть 1. Задача коммивояжера, слайд №6Полное построение алгоритма. Часть 1. Задача коммивояжера, слайд №7Полное построение алгоритма. Часть 1. Задача коммивояжера, слайд №8Полное построение алгоритма. Часть 1. Задача коммивояжера, слайд №9Полное построение алгоритма. Часть 1. Задача коммивояжера, слайд №10Полное построение алгоритма. Часть 1. Задача коммивояжера, слайд №11Полное построение алгоритма. Часть 1. Задача коммивояжера, слайд №12Полное построение алгоритма. Часть 1. Задача коммивояжера, слайд №13Полное построение алгоритма. Часть 1. Задача коммивояжера, слайд №14Полное построение алгоритма. Часть 1. Задача коммивояжера, слайд №15Полное построение алгоритма. Часть 1. Задача коммивояжера, слайд №16Полное построение алгоритма. Часть 1. Задача коммивояжера, слайд №17Полное построение алгоритма. Часть 1. Задача коммивояжера, слайд №18Полное построение алгоритма. Часть 1. Задача коммивояжера, слайд №19Полное построение алгоритма. Часть 1. Задача коммивояжера, слайд №20Полное построение алгоритма. Часть 1. Задача коммивояжера, слайд №21Полное построение алгоритма. Часть 1. Задача коммивояжера, слайд №22Полное построение алгоритма. Часть 1. Задача коммивояжера, слайд №23Полное построение алгоритма. Часть 1. Задача коммивояжера, слайд №24Полное построение алгоритма. Часть 1. Задача коммивояжера, слайд №25Полное построение алгоритма. Часть 1. Задача коммивояжера, слайд №26Полное построение алгоритма. Часть 1. Задача коммивояжера, слайд №27Полное построение алгоритма. Часть 1. Задача коммивояжера, слайд №28Полное построение алгоритма. Часть 1. Задача коммивояжера, слайд №29Полное построение алгоритма. Часть 1. Задача коммивояжера, слайд №30
Скачать

Содержание ▲

Вы можете ознакомиться и скачать презентацию на тему Полное построение алгоритма. Часть 1. Задача коммивояжера. Доклад-сообщение содержит 30 слайдов. Презентации для любого класса можно скачать бесплатно. Если материал и наш сайт презентаций Mypresentation Вам понравились – поделитесь им с друзьями с помощью социальных кнопок и добавьте в закладки в своем браузере.

Слайды и текст этой презентации

Слайд 1


Полное построение алгоритма ч 1. Задача коммивояжера
Описание слайда:
Полное построение алгоритма ч 1. Задача коммивояжера

Слайд 2


Содержание лекции Постановка задачи коммивояжера. Построение модели (в терминах теории графов). Исчерпывающий алгоритм для задачи коммивояжера. Оценка сложности алгоритма. Решение "задачи коммивояжера" методом полного перебора (исчерпывающий алгоритм). Отладка и документирование программ.
Описание слайда:
Содержание лекции Постановка задачи коммивояжера. Построение модели (в терминах теории графов). Исчерпывающий алгоритм для задачи коммивояжера. Оценка сложности алгоритма. Решение "задачи коммивояжера" методом полного перебора (исчерпывающий алгоритм). Отладка и документирование программ.

Слайд 3


Полное построение алгоритма. Этапы: Постановка задачи. Построение модели решения (математической модели, аналога и т.д.). Разработка алгоритма. Проверка правильности алгоритма. Реализация алгоритма. Анализ алгоритма и его сложности. Проверка программы. Составление документации
Описание слайда:
Полное построение алгоритма. Этапы: Постановка задачи. Построение модели решения (математической модели, аналога и т.д.). Разработка алгоритма. Проверка правильности алгоритма. Реализация алгоритма. Анализ алгоритма и его сложности. Проверка программы. Составление документации

Слайд 4


Постановка задачи. Прежде, чем понять задачу её, необходимо четко сформулировать. Обычно процесс точной формулировки задачи сводится к постановке правильных вопросов. Понятна ли терминология? Что дано? Что нужно найти? Как определить решение? Каких данных не хватает и все ли они нужны? Являются ли какие-то данные бесполезными? Какие сделаны допущения?
Описание слайда:
Постановка задачи. Прежде, чем понять задачу её, необходимо четко сформулировать. Обычно процесс точной формулировки задачи сводится к постановке правильных вопросов. Понятна ли терминология? Что дано? Что нужно найти? Как определить решение? Каких данных не хватает и все ли они нужны? Являются ли какие-то данные бесполезными? Какие сделаны допущения?

Слайд 5


Постановка задачи. Сформулируем постановку на примере. "Задача Коммивояжера". Агент по продаже компьютеров должен посетить 20 городов. Компания возмещает ему 50% стоимости дорожных расходов. Известна цена проезда между каждыми двумя городами. Коммивояжеру хотелось бы снизить дорожные расходы.
Описание слайда:
Постановка задачи. Сформулируем постановку на примере. "Задача Коммивояжера". Агент по продаже компьютеров должен посетить 20 городов. Компания возмещает ему 50% стоимости дорожных расходов. Известна цена проезда между каждыми двумя городами. Коммивояжеру хотелось бы снизить дорожные расходы.

Слайд 6


Постановка задачи Что дано? Исходная информация в виде перечня городов. Известно: Количество городов Стоимость переезда из города i в город j Комментарий: в принципе, можно сразу отметить, что дана матрица стоимостей С: сij- стоимость переезда из i в j.
Описание слайда:
Постановка задачи Что дано? Исходная информация в виде перечня городов. Известно: Количество городов Стоимость переезда из города i в город j Комментарий: в принципе, можно сразу отметить, что дана матрица стоимостей С: сij- стоимость переезда из i в j.

Слайд 7


Постановка задачи. Что хотим найти? Как снизить дорожные расходы: найти такую последовательность объезда городов, что стоимость всего пути будет наименьшей. Необходима ли дополнительная информация? Есть ли приоритеты в городах?
Описание слайда:
Постановка задачи. Что хотим найти? Как снизить дорожные расходы: найти такую последовательность объезда городов, что стоимость всего пути будет наименьшей. Необходима ли дополнительная информация? Есть ли приоритеты в городах?

Слайд 8


Постановка задачи Дополнительная информация: Маршрут начинается и кончается в базовом городе и проходит по одному разу через все остальные города.
Описание слайда:
Постановка задачи Дополнительная информация: Маршрут начинается и кончается в базовом городе и проходит по одному разу через все остальные города.

Слайд 9


Постановка задачи Что надо получить? Список городов, содержащий каждый город только один раз, (за исключением базового города, который стоит в списке первым и последним), который был бы оптимальным для коммивояжера. Что значит «оптимальный»?
Описание слайда:
Постановка задачи Что надо получить? Список городов, содержащий каждый город только один раз, (за исключением базового города, который стоит в списке первым и последним), который был бы оптимальным для коммивояжера. Что значит «оптимальный»?

Слайд 10


Постановка задачи Что надо получить? Сумма стоимостей между каждыми двумя городами маршрута - это общая стоимость маршрута представленного списка. Необходимо представить список наименьшей стоимости.
Описание слайда:
Постановка задачи Что надо получить? Сумма стоимостей между каждыми двумя городами маршрута - это общая стоимость маршрута представленного списка. Необходимо представить список наименьшей стоимости.

Слайд 11


Построение модели решения (математической модели, аналога и т.д.). Задача четко сформулирована, теперь необходимо составить для неё математическую модель. Выбор модели существенно влияет на остальные этапы решения задачи. Невозможно предложить набор правил, автоматизирующих этап моделирования.
Описание слайда:
Построение модели решения (математической модели, аналога и т.д.). Задача четко сформулирована, теперь необходимо составить для неё математическую модель. Выбор модели существенно влияет на остальные этапы решения задачи. Невозможно предложить набор правил, автоматизирующих этап моделирования.

Слайд 12


Построение модели решения (математической модели, аналога и т.д.). Приступая к разработке модели, следует, по крайней мере, задать два основных вопроса: Какие математические структуры больше всего подходят для задачи (это может сразу упростить ее и повлиять на выбор алгоритма) Существует ли решенные аналогичные задачи. (На что похоже, в чем отличие)
Описание слайда:
Построение модели решения (математической модели, аналога и т.д.). Приступая к разработке модели, следует, по крайней мере, задать два основных вопроса: Какие математические структуры больше всего подходят для задачи (это может сразу упростить ее и повлиять на выбор алгоритма) Существует ли решенные аналогичные задачи. (На что похоже, в чем отличие)

Слайд 13


Построение модели решения (математической модели, аналога и т.д.). Гаусс, Лейбниц, Эйнштейн? Ищем похожую задачу Что нужно для модели?: описать на языке математики, что нам дано и что хотим найти, сделать выбор математических структур, переформулировать задачу необходимо в терминах соответствующих математических объектов.
Описание слайда:
Построение модели решения (математической модели, аналога и т.д.). Гаусс, Лейбниц, Эйнштейн? Ищем похожую задачу Что нужно для модели?: описать на языке математики, что нам дано и что хотим найти, сделать выбор математических структур, переформулировать задачу необходимо в терминах соответствующих математических объектов.

Слайд 14


Построение модели решения (математической модели, аналога и т.д.). Модель построена, если можно утвердительно ответить на следующие вопросы: Вся ли важная информация задачи описана математическими объектами? Существует ли математическая величина, ассоциируемая с искомым результатом? Выявлено ли какое-нибудь полезное соотношение между объектами модели? Можно работать с моделью? Насколько удобно ли с ней работать?
Описание слайда:
Построение модели решения (математической модели, аналога и т.д.). Модель построена, если можно утвердительно ответить на следующие вопросы: Вся ли важная информация задачи описана математическими объектами? Существует ли математическая величина, ассоциируемая с искомым результатом? Выявлено ли какое-нибудь полезное соотношение между объектами модели? Можно работать с моделью? Насколько удобно ли с ней работать?

Слайд 15


Построение модели для задачи коммивояжера Решали ли мы раньше подобные задачи? Вероятно, нет, однако мы сталкивались с задачей выбора пути по дорожным картам или в лабиринте. Представим нашу задачу в виде карты: Города - точки, соединенные отрезками, на которых проставлена стоимость проезда из первого города во второй. (Длины отрезков при этом роли не играют).
Описание слайда:
Построение модели для задачи коммивояжера Решали ли мы раньше подобные задачи? Вероятно, нет, однако мы сталкивались с задачей выбора пути по дорожным картам или в лабиринте. Представим нашу задачу в виде карты: Города - точки, соединенные отрезками, на которых проставлена стоимость проезда из первого города во второй. (Длины отрезков при этом роли не играют).

Слайд 16


Построение модели для задачи коммивояжера Точка - город. расстояние между каждой парой точек, соответствующих городам i и j, - сij Расположим точки любым удобным способом, соединим точки i и j линиями и проставим на них «веса» сij
Описание слайда:
Построение модели для задачи коммивояжера Точка - город. расстояние между каждой парой точек, соответствующих городам i и j, - сij Расположим точки любым удобным способом, соединим точки i и j линиями и проставим на них «веса» сij

Слайд 17


Построение модели для задачи коммивояжера
Описание слайда:
Построение модели для задачи коммивояжера

Слайд 18


Обоснование модели В общем случае сеть — это множество точек (на плоскости) вместе с линиями, соединяющими некоторые или все пары точек; над линиями могут быть проставлены веса Каждый граф можно представить на плоскости множеством точек, соответствующих вершинам, которые соединены линиями, соответствующими ребрам. Вершины графа на рисунке выделяют обычно кружочками или квадратиками, так как не всегда точки пересечения ребер являются вершинами графа.
Описание слайда:
Обоснование модели В общем случае сеть — это множество точек (на плоскости) вместе с линиями, соединяющими некоторые или все пары точек; над линиями могут быть проставлены веса Каждый граф можно представить на плоскости множеством точек, соответствующих вершинам, которые соединены линиями, соответствующими ребрам. Вершины графа на рисунке выделяют обычно кружочками или квадратиками, так как не всегда точки пересечения ребер являются вершинами графа.

Слайд 19


Обоснование модели. Представление графа в виде матрицы Для нашей задачи рассмотрим представление графа в виде матрицы стоимостей. Предположим, что стоимость проезда из города i в город j такая же как и из города j в город i, хотя, вообще говоря, это не всегда так. Как видно из примера на рис.1, в нашем случае число городов равно 5. Заполним матрицу стоимостей С
Описание слайда:
Обоснование модели. Представление графа в виде матрицы Для нашей задачи рассмотрим представление графа в виде матрицы стоимостей. Предположим, что стоимость проезда из города i в город j такая же как и из города j в город i, хотя, вообще говоря, это не всегда так. Как видно из примера на рис.1, в нашем случае число городов равно 5. Заполним матрицу стоимостей С

Слайд 20


Матрица стоимостей для задачи коммивояжера
Описание слайда:
Матрица стоимостей для задачи коммивояжера

Слайд 21


Модель для задачи коммивояжера Что ищем? В терминах теории графов список городов определяет замкнутый цикл, начинающийся с базового города и возращающийся туда же после прохождения каждой вершины графа по одному разу. Такой цикл называется гамильтоновым циклом. Задача решена, если мы нашли гамильтонов цикл с наименьшей стоимостью.
Описание слайда:
Модель для задачи коммивояжера Что ищем? В терминах теории графов список городов определяет замкнутый цикл, начинающийся с базового города и возращающийся туда же после прохождения каждой вершины графа по одному разу. Такой цикл называется гамильтоновым циклом. Задача решена, если мы нашли гамильтонов цикл с наименьшей стоимостью.

Слайд 22


Модель для задачи коммивояжера Например, для рассматриваемого графа гамильтонов цикл 1 – 5 – 3 – 4 – 2 – 1 имеет стоимость: 5+2+1+4+1=13 Является ли он маршрутом с минимальной стоимостью? Это пока неизвестно.
Описание слайда:
Модель для задачи коммивояжера Например, для рассматриваемого графа гамильтонов цикл 1 – 5 – 3 – 4 – 2 – 1 имеет стоимость: 5+2+1+4+1=13 Является ли он маршрутом с минимальной стоимостью? Это пока неизвестно.

Слайд 23


Разработка алгоритма. Выбор алгоритма зависит от выбранной модели. Два разных алгоритма могут быть правильными, но сильно отличаться по эффективности работы. Критерии эффективности различных алгоритмов и способы оценки мы рассмотрим позже, а сейчас попытаемся описать самый очевидный подход к алгоритму решения нашей задачи.
Описание слайда:
Разработка алгоритма. Выбор алгоритма зависит от выбранной модели. Два разных алгоритма могут быть правильными, но сильно отличаться по эффективности работы. Критерии эффективности различных алгоритмов и способы оценки мы рассмотрим позже, а сейчас попытаемся описать самый очевидный подход к алгоритму решения нашей задачи.

Слайд 24


«Исчерпывающий алгоритм» решения задачи коммивояжера Произвольно пронумеруем города целыми числами от 1 до n. Базовому городу припишем номер n. Таким образом, каждый гамильтонов цикл однозначно соответствует перестановке целых чисел: n 1, 2, 3, … n-1, n n n-5, 2, 3, …, n-1, n-2 n и др. Для любой перестановки мы можем проследить гамильтонов цикл на графе, и в то же время вычислить стоимость соответствующего пути.
Описание слайда:
«Исчерпывающий алгоритм» решения задачи коммивояжера Произвольно пронумеруем города целыми числами от 1 до n. Базовому городу припишем номер n. Таким образом, каждый гамильтонов цикл однозначно соответствует перестановке целых чисел: n 1, 2, 3, … n-1, n n n-5, 2, 3, …, n-1, n-2 n и др. Для любой перестановки мы можем проследить гамильтонов цикл на графе, и в то же время вычислить стоимость соответствующего пути.

Слайд 25


Исчерпывающий алгоритм (ETS): Образуем перестановки первых n-1 чисел Выбираем первую перестановку, строим соостветствующий путь и вычисляем его стоимость. Принимаем данную стоимость за минимальную. Выбираем перестановку, строим соостветствующий путь и вычисляем его стоимость. Сравниваем стоимость текущего пути с минимальной. Запоминаем минимальную из них. Возвращаемся к шагу 3. Такой алгоритм называется исчерпывающим или переборным алгоритмом.
Описание слайда:
Исчерпывающий алгоритм (ETS): Образуем перестановки первых n-1 чисел Выбираем первую перестановку, строим соостветствующий путь и вычисляем его стоимость. Принимаем данную стоимость за минимальную. Выбираем перестановку, строим соостветствующий путь и вычисляем его стоимость. Сравниваем стоимость текущего пути с минимальной. Запоминаем минимальную из них. Возвращаемся к шагу 3. Такой алгоритм называется исчерпывающим или переборным алгоритмом.

Слайд 26


Проверка правильности алгоритма. Это один из наиболее трудных этапов. Проверка правильности алгоритма часто заменяется проверкой правильности программы, то есть прогонкой её на различных тестах. Если выданные программой ответы могут быть подтверждены известными или вычисленными вручную данными, возникает искушение сделать вывод, что программа работает.
Описание слайда:
Проверка правильности алгоритма. Это один из наиболее трудных этапов. Проверка правильности алгоритма часто заменяется проверкой правильности программы, то есть прогонкой её на различных тестах. Если выданные программой ответы могут быть подтверждены известными или вычисленными вручную данными, возникает искушение сделать вывод, что программа работает.

Слайд 27


Проверка правильности алгоритма. Для большинства алгоритмов очень сложно составить систему тестов, проверяющую все особенности, тонкости работающей программы. 3% ошибок считается нормой. В документации должны быть описаны ситуации возникновения ошибок (ограничения).
Описание слайда:
Проверка правильности алгоритма. Для большинства алгоритмов очень сложно составить систему тестов, проверяющую все особенности, тонкости работающей программы. 3% ошибок считается нормой. В документации должны быть описаны ситуации возникновения ошибок (ограничения).

Слайд 28


Методика доказательства правильности алгоритма. Предположим, что алгоритм описан в виде последовательности шагов: от шага 1 до шага n. Предложим обоснование правомерности каждого шага (выделение инварианта). Проведем доказательство конечности алгоритма, при этом будут проверены все подходящие входные данные и получены все подходящие выходные данные.
Описание слайда:
Методика доказательства правильности алгоритма. Предположим, что алгоритм описан в виде последовательности шагов: от шага 1 до шага n. Предложим обоснование правомерности каждого шага (выделение инварианта). Проведем доказательство конечности алгоритма, при этом будут проверены все подходящие входные данные и получены все подходящие выходные данные.

Слайд 29


Доказательство для алгоритма «задачи коммивояжера». Проверяется каждый цикл. При этом будет проверен и цикл с минимальной стоимостью; он будет запомнен (не потеряем). Этот путь будет отброшен только в том случае, если существует путь с меньшей стоимостью. Алгоритм должен закончить работу, так как число путей, которые нужно проверить, конечно: (n-1)!
Описание слайда:
Доказательство для алгоритма «задачи коммивояжера». Проверяется каждый цикл. При этом будет проверен и цикл с минимальной стоимостью; он будет запомнен (не потеряем). Этот путь будет отброшен только в том случае, если существует путь с меньшей стоимостью. Алгоритм должен закончить работу, так как число путей, которые нужно проверить, конечно: (n-1)!

Слайд 30


Доказательство для алгоритма «задачи коммивояжера». Подобный метод известен как "доказательство исчерпыванием". Это самый грубый из всех методов доказательства. Правильность алгоритма ничего не говорит о его эффективности. Исчерпывающие алгоритмы редко бывают хорошими во всех отношениях.
Описание слайда:
Доказательство для алгоритма «задачи коммивояжера». Подобный метод известен как "доказательство исчерпыванием". Это самый грубый из всех методов доказательства. Правильность алгоритма ничего не говорит о его эффективности. Исчерпывающие алгоритмы редко бывают хорошими во всех отношениях.

Скачать

Похожие презентации
Mypresentation.ru
Загрузить презентацию