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

Содержание

• 
  Слайд 1

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

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

• 
  Слайд 2

  Содержание

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

• 
  Слайд 3

  Введение

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

• 
  Слайд 4
  

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

• 
  Слайд 5
  

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

• 
  Слайд 6

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

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

• 
  Слайд 7
  

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

• 
  Слайд 8

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

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

• 
  Слайд 9

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

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

• 
  Слайд 10

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

  Задача о коммивояжере [Электронный ресурс] // 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.

• 
  Слайд 11

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