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

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

tapinapura

Презентацию на тему Задача Коммивояжера можно скачать абсолютно бесплатно на нашем сайте. Предмет презентации : Разные. Красочные слайды и илюстрации помогут вам заинтересовать своих одноклассников или аудиторию. Для просмотра содержимого презентации воспользуйтесь плеером, или если вы хотите скачать презентацию - нажмите на соответствующий текст под плеером. Презентация содержит 11 слайдов.

скачать презентацию

Слайды презентации

Слайд 1: Презентация Задача Коммивояжера
Слайд 1

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

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

Слайд 2: Презентация Задача Коммивояжера
Слайд 2

Содержание

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

Слайд 3: Презентация Задача Коммивояжера
Слайд 3

Введение

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

Слайд 4: Презентация Задача Коммивояжера
Слайд 4

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

Слайд 5: Презентация Задача Коммивояжера
Слайд 5

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

Слайд 6: Презентация Задача Коммивояжера
Слайд 6

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

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

Слайд 7: Презентация Задача Коммивояжера
Слайд 7

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

Слайд 8: Презентация Задача Коммивояжера
Слайд 8

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

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

Слайд 9: Презентация Задача Коммивояжера
Слайд 9

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

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

Слайд 10: Презентация Задача Коммивояжера
Слайд 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: Презентация Задача Коммивояжера
Слайд 11

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

Список похожих презентаций

  • Яндекс.Метрика
  • Рейтинг@Mail.ru