n="justify"> саму задачу можна зобразіті и на площіні (рис. 2.3.1).
Вона зводіться до відшукання на графі гамільтонового циклу. Один Із можливіть розв'язків показано на рис. 2.3.1 потовщенімі лініямі. p align="justify"> Задача комівояжера
Вона Полягає в Наступний: комівояжер винен відвідаті Кожне Із завданні n міст по одному разу, віїхавші з якогось з ціх міст и вернуться до нього ж. Потрібно найти найкоротшій маршрут, знаючи відстані между шкірно парою міст. p align="justify"> Математична постановка цієї задачі віглядає так: у ПОВНЕ зваження графі нужно найти гамільтонів цикл (чі ланцюг) мінімальної ваги. Під вагою циклу розуміється сума ваг ребер, что складають его. p align="justify"> До теперішніх годині для задачі комівояжера відомі Такі алгоритми:
дінамічне програмування;
метод аналізу и відсівання варіантів;
метод гілок и границь
среди якіх Останній - найбільш популярні.
Мі познайомімося з одним алгоритмом побудова гамільтонового циклу мінімальної ваги В«йди в найближчеВ», что для Неповне графа Дає набліжене решение.
Опіс алгоритмом В«йди в найближчеВ» ( a ):
Алгоритм a віконується по КРОК S = 1,2, ..., n. На кроці S = 1 фіксується "u1ГЋV и розглядається множини E (u1) ГЊE усіх ребер, інцідентніх u1. Серед них вібірається найкоротше, тоб таке е1 = (u1, u2), для Якого вага
После чего Вважаємо, что на I кроці побудовали ланцюг L1 = [u1, u2]. Нехай здійснено S ВЈ n-1 кроків, у результаті S - го Кроку побудовали Елементарна ланцюг LS = [u1, u2, ..., uS +1] ... Позначімо через Е (uS +1) - множини усіх таких ребер е = (uS + 1, u) ГЋE, что:
) інцідентні вершіні uS +1;
) НЕ інцідентні ніякій вершіні u з ланцюга Ls, тоб uГЏLS
На кроці S +1 среди ребер множини E (uS +1) вібіраємо найкоротше ребро e +1, тоб таке , что задовольняє умові
После чего ребро es +1 прієднуємо до ls и одержуємо Простий ланцюг Ls +1 = [u1, ..., uS +1, uS +2] ...
Алгоритм a закінчує роботу на кроці S = n, перед качаном Якого, у результаті Кроку S = n-1 виділений гамільтонова ланцюг Ln-1 = [u1, ..., un] ...
Тоді на кроці S = n, гамільтонів ланцюг Ln-1 замікається в гамільтонів цикл Шляхом Приєднання до цього ланцюга ребра е = (un, u1) ГЋE де Е - множини ребер даного графа G = (V, E).
цею процес виявило безрезультатним, Якщо не містіть ребра e = (un, u1).
Робота алгоритмом a віявляється безрезультатним на якому-небудь кроці S такоже у того випадка, коли множини ребер E (uSH) = Г†
На ПОВНЕ графі алгоритм a всегда знаходится Деяк Припустиме решение задачі комівояжера X = (V, Ех) ГЋ X, де X - це гамільтонів цикл даного полного графа G = (V, Е).
2.4 Завдання
