Задача комівояжера була поставлена в 1934 році, і вона є такою ж складною як і Велика теорема Ферма.
Комівояжер (бродячий торгівець) мусить вийти з першого міста, відвідати по разу в невідомому порядку міста 1,2, 3 ... n й повернутися в перше місто. Відстань між містами відома. В якому порядку слід обходити міста, щоб замкнений шлях (тур) комівояжера був найкоротшим?
В термінах теорії графов ЗК можна сформулювати так:
Дано повний граф з n вершинами, довжина ребра (i, j)= Сij. Знайти гамільтоновий цикл мінімальної довжини.
Гамільтонів цикл
В 1859 р У. Гамільтон придумав гру “Навколосвітня подорож”, де треба було відшукати такий шлях, що проходить скрізь усі вершини (міста, пункти призначення) графа, щоб відвідати кожну вершину одноразово й повернутися назад. Шляхи, що володіють такою властивістю, називають гамільтоновими циклами.
Жадібний алгоритм – алгоритм находження найменшої відстані шляхом вибору самого короткого, ще не вибраного ребра за умовах, що вона не створює циклу з вже вибраними ребрами.
До ідеї метода гілок та меж приходило багато дослідників, але Літтл з співавторами на основі вказаного метода розробили вдалий алгоритм розв’язку ЗК й цим сприяли популяризації підхода. З того часу метод гілок та меж був з успіхом застосований до багатьох задач. Для рішення ЗК було придумано декілька інщих модифікацій методу, але в більшості підручників викладається робота Літтла.
Алгоритм Дейкстри
Одним з варіантів рішення ЗК є варіант знаходженя найкоротшого шляху, що вміщує всі міста. Отриманий ланцюг потім доповнюється вихідним містом – виникає шуканий тур.
