Презентация "Задача Коммивояжера" – проект, доклад

Задача Коммивояжера

Выполнила: Котова А.А. Группа 2.1 Руководитель: Рунова Л.П.

Содержание

Введение Общее описание Простейшие методы решения Практическое применение Список источников

Введение

Комбинаторика – раздел математики, посвященные решению задач выбора и расположения элементов некоторого, обычно, конечного множества в соответствии с заданными правилами.

Большой вклад в систематическое развитие комбинаторных методов был сделан Г. Лейбницем (диссертация «Комбинаторное искусство»), Я. Бернулли (работа «Искусство предположений»), Л. Эйлером. Можно считать, что с появлением работ Я. Бернулли и Г. Лейбница комбинаторные методы выделились в самостоятельную часть математики. В работах Л.Эйлера по разбиениям и композициям натуральных чисел на слагаемые было положено начало одному из основных методов перечисления комбинаторных конфигураций – методу производящих функций.

В 1859 г. У. Гамильтон придумал игру «Кругосветное путешествие», состоящую в отыскании такого пути, проходящего через все вершины (города, пункты назначения) графа, чтобы посетить каждую вершину однократно и возвратиться в исходную. Пути, обладающие таким свойством, называются гамильтоновыми циклами.

Общее описание

Постановка задачи следующая: Коммивояжер (бродячий торговец) должен выйти из первого города, посетить по разу в неизвестном порядке города 2,1,3..n и вернуться в первый город. Расстояния между городами известны. В каком порядке следует обходить города, чтобы замкнутый путь (тур) коммивояжера был кратчайшим?

Относительно математизированной формулировки ЗК уместно сделать два замечания: Во-первых, в постановке Сij означали расстояния, поэтому они должны быть неотрицательными, т.е. для всех jÎТ: Cij³0; Cjj=∞ (1) (последнее равенство означает запрет на петли в туре), симметричными, т.е. для всех i,j: Cij= Cji (2) и удовлетворять неравенству треугольника, т.е. для всех: Cij+ Cjk³Cik (3)

Простейшие методы решения задачи коммивояжера

Полный перебор Случайный перебор Жадные алгоритмы Деревянный алгоритм Метод имитации отжига Метод ветвей и границ Метод генетических алгоритмов Метод муравьиной колонии

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

Кроме очевидного применения ЗК на практике, существует ещё ряд задач, сводимых к решению ЗК: Задача о производстве красок Задача о дыропробивном прессе

Список источников

Задача о коммивояжере [Электронный ресурс] // URL: http://zs7.ru/text/nauka/kommivoyager. Метод ветвей и границ [Электронный ресурс] // URL: http://pco.iis.nsk.su/ICP/Practice/dd8-3/node9.html. Практическое применение задачи коммивояжера [Электронный ресурс] // URL: http://lmatrix.ru/news2/news2_4.html.

Спасибо за внимание