Презентация на тему Задача Коммивояжера

и расположения элементов некоторого, обычно, конечного множества в соответствии

с заданными правилами.

сделан Г. Лейбницем (диссертация «Комбинаторное искусство»), Я. Бернулли (работа

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

путешествие», состоящую в отыскании такого пути, проходящего через все

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

из первого города, посетить по разу в неизвестном порядке

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

замечания:
Во-первых, в постановке Сij означали расстояния, поэтому они должны

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

алгоритм
Метод имитации отжига
Метод ветвей и границ
Метод генетических алгоритмов
Метод муравьиной

колонии

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

Задача о производстве красок
Задача о дыропробивном прессе

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.