Задача комівояжера Вч. Гісь І. В



Дата конвертації15.06.2016
Розмір445 b.


Задача комівояжера

  • Вч. Гісь І.В.


Як оптимально розв’язати задачу комівояжера?



Для цього необхідно:



Задача комівояжера (бродячий торговець)

  • Задача комівояжера була поставлена в 1934 році, і вона є такою ж складною як і Велика теорема Ферма.

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

  • В термінах теорії графов ЗК можна сформулювати так:

  • Дано повний граф з n вершинами, довжина ребра (i, j)= Сij. Знайти гамільтоновий цикл мінімальної довжини.



Гамільтонів цикл

  • В 1859 р У. Гамільтон придумав гру “Навколосвітня подорож”, де треба було відшукати такий шлях, що проходить скрізь усі вершини (міста, пункти призначення) графа, щоб відвідати кожну вершину одноразово й повернутися назад. Шляхи, що володіють такою властивістю, називають гамільтоновими циклами.



Методи розв’язку задачі комівояжера

  • Повний перебір (лексичний)

  • Обчислювальна геометрія

  • Жадібний алгоритм

  • Метод гілок та меж

  • Алгоритм Дейкстри



Якщо можна побудувати опуклий багатокутник, в якому усі міста лежать по периметру, то такий опуклий багатокутник є найкоротшим туром.

  • Якщо можна побудувати опуклий багатокутник, в якому усі міста лежать по периметру, то такий опуклий багатокутник є найкоротшим туром.



Жадібний алгоритм алгоритм находження найменшої відстані шляхом вибору самого короткого, ще не вибраного ребра за умовах, що вона не створює циклу з вже вибраними ребрами.

  • Жадібний алгоритм алгоритм находження найменшої відстані шляхом вибору самого короткого, ще не вибраного ребра за умовах, що вона не створює циклу з вже вибраними ребрами.



Метод гілок та меж

  • До ідеї метода гілок та меж приходило багато дослідників, але Літтл з співавторами на основі вказаного метода розробили вдалий алгоритм розв’язку ЗК й цим сприяли популяризації підхода. З того часу метод гілок та меж був з успіхом застосований до багатьох задач. Для рішення ЗК було придумано декілька інщих модифікацій методу, але в більшості підручників викладається робота Літтла.



Алгоритм Дейкстри

  • Одним з варіантів рішення ЗК є варіант знаходженя найкоротшого шляху, що вміщує всі міста. Отриманий ланцюг потім доповнюється вихідним містом – виникає шуканий тур.



Ідея розв’язку задачі методом гілок та меж









Аналіз методів ріщення задачі комівояжера



1. Де можна практично використати задачу комівояжера?



Використані джерела:

  • В. М. Бондарев, В. И. Рублинецкий, Е. Г. Качко. Основы программирования. – Харьков, Фолио; Ростов на Дону, Феникс, 1998, 368 с.

  • http://www.monax.ru/- колеція рефератів




База даних захищена авторським правом ©pres.in.ua 2016
звернутися до адміністрації

    Головна сторінка