'

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

Понравилась презентация – покажи это...





Слайд 0

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


Слайд 1

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


Слайд 2

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


Слайд 3

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


Слайд 4

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


Слайд 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 — точный тур


Слайд 6

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


×

HTML:





Ссылка: