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




Скачати 27,53 Kb.
Дата конвертації08.12.2016
Розмір27,53 Kb.

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

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

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

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

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

  • Задача комівояжера була поставлена в 1934 році, і вона є такою ж складною як і Велика теорема Ферма.
  • Комівояжер (бродячий торгівець) мусить вийти з першого міста, відвідати по разу в невідомому порядку міста 1,2, 3 ... n й повернутися в перше місто. Відстань між містами відома. В якому порядку слід обходити міста, щоб замкнений шлях (тур) комівояжера був найкоротшим?
  • В термінах теорії графов ЗК можна сформулювати так:
  • Дано повний граф з n вершинами, довжина ребра (i, j)= Сij. Знайти гамільтоновий цикл мінімальної довжини.

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

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

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

  • Повний перебір (лексичний)
  • Обчислювальна геометрія
  • Жадібний алгоритм
  • Метод гілок та меж
  • Алгоритм Дейкстри

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

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

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

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

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

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

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

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

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

  • -
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 1
  • -
  • 6
  • 4
  • 8
  • 7
  • 14
  • 2
  • 6
  • -
  • 7
  • 11
  • 7
  • 10
  • 3
  • 4
  • 7
  • -
  • 4
  • 3
  • 10
  • 4
  • 8
  • 11
  • 4
  • -
  • 5
  • 11
  • 5
  • 7
  • 7
  • 3
  • 5
  • -
  • 7
  • 6
  • 14
  • 10
  • 10
  • 11
  • 7
  • -
  • табл. 2
  • -
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 1
  • -
  • 2
  • 0
  • 4
  • 3
  • 10
  • 4
  • 2
  • 0
  • -
  • 1
  • 5
  • 1
  • 4
  • 6
  • 3
  • 1
  • 4
  • -
  • 1
  • 0
  • 7
  • 3
  • 4
  • 4
  • 7
  • 0
  • -
  • 1
  • 7
  • 4
  • 5
  • 4
  • 4
  • 0
  • 2
  • -
  • 4
  • 3
  • 6
  • 7
  • 3
  • 3
  • 4
  • 0
  • -
  • 7
  • табл. 3
  •  
  • -
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 1
  • -
  • 0
  • 0
  • 3
  • 3
  • 6
  • 2
  • 0
  • -
  • 1
  • 4
  • 1
  • 0
  • 3
  • 1
  • 2
  • -
  • 0
  • 0
  • 3
  • 4
  • 4
  • 5
  • 0
  • -
  • 1
  • 3
  • 5
  • 4
  • 2
  • 0
  • 1
  • -
  • 0
  • 6
  • 7
  • 1
  • 3
  • 3
  • 0
  • -
  • 2
  • 1
  • 4
  • табл. 4
  • 27+7=34
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 1
  • -
  • 01
  • 0
  • 3
  • 3
  • 6
  • 2
  • 01
  • -
  • 1
  • 4
  • 1
  • 0
  • 3
  • 1
  • 2
  • -
  • 01
  • 0
  • 3
  • 4
  • 4
  • 5
  • 01
  • -
  • 1
  • 3
  • 5
  • 4
  • 2
  • 0
  • 1
  • -
  • 0
  • 6
  • 7
  • 1
  • 3
  • 3
  • 01
  • -
  • табл. 5
  • 1
  • 3
  • 4
  • 5
  • 6
  • 2
  • 01
  • 1
  • 4
  • 1
  • 0
  • 3
  • 1
  • -
  • 01
  • 0
  • 3
  • 4
  • 4
  • 01
  • -
  • 1
  • 3
  • 5
  • 4
  • 0
  • 1
  • -
  • 0
  • 6
  • 7
  • 3
  • 3
  • 01
  • -
  • табл. 6
  • 1
  • 3
  • 4
  • 5
  • 6
  • 2
  • 01
  • 1
  • 4
  • 1
  • 0
  • 3
  • 03
  • -
  • 01
  • 0
  • 3
  • 4
  • 3
  • 01
  • -
  • 1
  • 3
  • 5
  • 3
  • 0
  • 1
  • -
  • 0
  • 6
  • 6
  • 3
  • 3
  • 01
  • -
  • табл. 7
  • 3
  • 4
  • 5
  • 6
  •  
  • 2
  • 1
  • 4
  • 1
  • 0
  •  
  • 4
  • 01
  • -
  • 1
  • 3
  •  
  • 5
  • 0
  • 1
  • -
  • 0
  •  
  • 6
  • 3
  • 3
  • 01
  • -
  •  
  • табл. 8
  • 3
  • 4
  • 5
  • 6
  • 2
  • 1
  • 3
  • 1
  • 0
  • 4
  • 01
  • -
  • 1
  • 3
  • 5
  • 0
  • 02
  • -
  • 0
  • 6
  • 3
  • 2
  • 03
  • -
  • табл. 9
  • 3
  • 4
  • 6
  • 2
  • 1
  • 3
  • 03
  • 4
  • 03
  • -
  • 3
  • 5
  • 0
  • 03
  • 0
  • табл. 10
  • 3
  • 4
  • 4
  • 0
  • -
  • 5
  • 0
  • 0
  • табл. 11

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

  • Алгоритм лексичного перебору
  • Кількість міст
  • Час обробки, с
  • 10
  • 41
  • точний
  • 12
  • 12000 (3г. 20хв.)
  • 32
  • -*
  • 100
  • -*
  • Метод гілок та меж
  • 10
  • ~0
  • точний
  • 32
  • ~0.0001
  • 100
  • 1.2

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

  • Навести приклади.
  • Домашнє завдання
  • 2.Написати програмний код розв’язку
  • задачі комівояжера

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

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


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

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