Некоторые исследования задачи коммивояжера


The Presentation inside:

Slide 0

МОСКОВСКИЙ ФИЗИКО-ТЕХНИЧЕСКИЙ ИНСТИТУТ(ГУ) Факультет управления и прикладной математики Кафедра «Математическое моделирование сложных процессов и систем» Некоторые исследования задачи коммивояжера Научный руководитель: доцент, к.ф-м.н. Оленев Николай Николаевич Выполнила: Перлова Светлана Дмитриевна


Slide 1

Метод выпуклого многоугольника Построение наибольшего выпуклого многоугольника Включение внутренних точек к ближайшим граням


Slide 2

Недостатки метода Подразумевается существование полного связного графа Неудобный метод задания условия


Slide 3

Метод достройки до эйлерова цикла


Slide 4

Добавим ребро 6 — 2 2 — 3 2 — 5 2 — 1 — 3 3 — 4 — 5 2 — 6 — 5 Конечный тур: 3-1-2-6-5-4-3


Slide 5

Задача с несколькими коммивояжерами Наиболее удаленные вершины 4 и 3 1 — 4 — 5 2 — 3 — 6 2 + 3 + 4 = 9 2 + 1 + 5 = 8 17 < 23 1-4-5-6-3-2-1 — точный тур


Slide 6

КОНЕЦ Спасибо за внимание.


×

HTML:





Ссылка: