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

Содержание Введение 1. Завдання комівояжера 1.1. Загальне опис 1.2. Методи виконання завдання комівояжера 1.2.1. Жадібний алгоритм. 1.2.2. Дерев’яний алгоритм 1.2.3. Метод гілок і національних кордонів 1.2.4. Алгоритм Дейкстры 1.2.5. Мій метод виконання завдання комівояжера 1.2.6. Аналіз методів виконання завдання комівояжера 1.3. Практичне застосування завдання коммивояжера Выводы Литература Приложения.

Комбінаторика — розділ математики, присвячений рішенню завдань вибору і розташування елементів деякого, зазвичай кінцевого безлічі в відповідність до заданими правилами.

І таке правило визначає спосіб побудови деякою конструкції з елементів вихідного безлічі, званої комбінаторної конфігурацією. Тому можна сказати, що метою комбинаторного аналізу вивчення комбінаторних конфігурацій. Це вивчення включає у собі питання існування комбінаторних конфігурацій, алгоритми їх побудови, оптимізацію таких алгоритмів, і навіть вирішення завдань перерахування, в частковості визначення числа конфігурацій даного класу. Найпростішим прикладом комбінаторних конфігурацій є перестановки, поєднання і размещения.

Вагомий внесок у систематичне розвиток комбінаторних методів був зроблено Р. Лейбніцем (дисертація «Комбинаторное мистецтво»), Я. Бернуллі (робота «Мистецтво припущень»), Л. Эйлером. Можна вважати, що з появою робіт Я. Бернуллі і Р. Лейб-ница комбінаторні методи виділилися на самостійну частина математики. У працях Л. Эйлера по разбиениям і композиціям натуральних чисел на складові було покладено початок одного з основних методів перерахування комбінаторних конфігурацій — методу які виробляють функций.

Повернення інтересу до комбінаторному аналізу належить до 50-му років ХХ в. у зв’язку з бурхливим розвитком кібернетики та дискретною математики широким використанням електронно-обчислювальної техніки. У цей час активізувався інтерес до класичним комбинаторным задачам.

Класичні комбінаторні завдання — це завдання вибору і розташування елементів кінцевого безлічі, що мають у ролі вихідної деяку формулювання розважального змісту на кшталт головоломок.

У 1859 р. У. Гамільтон придумав гру «Кругосвітню подорож», яке у знаходженні такого шляху, який струменіє крізь ці вершини (міста, пункти призначення) графа, зображеного на рис. 1, щоб відвідати кожну вершину одноразово і в вихідну. Шляхи, які мають таким властивістю, називаються гамильтоновыми циклами.

Завдання про гамильтоновых циклах в графі отримала різні узагальнення. Один із цих узагальнень — завдання комівояжера, що має низку застосувань в дослідженні операцій, зокрема за рішенні деяких транспортних проблем.

1. Завдання коммивояжера.

1. Загальне описание.

Завдання комівояжера (надалі сокращённо — ЗК) є одним із знаменитих завдань теорії комбінаторики. Вона стала поставлено 1934 року, і про неї, як про Велику теорему Ферма обламували зуби кращі математики. У своїй сфері (оптимізації дискретних завдань) ЗК є своєрідною полігоном, у якому випробовуються нові методы.

Постановка завдання следующая.

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

Аби виконати завдання до наукового виду, введём деякі терміни. Отже, міста перенумеровані числами j (Т=(1,2,3.n). Тур комівояжера то, можливо описаний циклічною перестановкою t=(j1,j2,., jn, j1), причому всі j1. jn — різні номери; що у початок і наприкінці j1, показує, що перестановка зациклену. Відстані між парами вершин Сij утворюють матрицю З. Завдання у тому, щоб знайти такої тур t, щоб мінімізувати функционал.

[pic].

Щодо математизированной формулювання ЗК доречно зробити два замечания.

По-перше, у постановці Сij означали відстані, тому повинно бути неотрицательными, тобто. всім j (Т: |Сij (0; Cjj=? |(2)|.

(останнє рівність означає заборона петлі в турі), симетричними, тобто. всім i, j: |Сij= Сji. |(3)|.

і задовольняти нерівності трикутника, тобто. всім: |Сij+ Сjk (Cik |(4)|.

У математичної постановці говориться про довільній матриці. Зроблено це оскільки є багато прикладних завдань, які описуються основний моделлю, але завжди умовам (2)-(4) не задовольняють. Особливо порушується умова (3) (наприклад, якщо Сij — не відстань, а Плата проїзд: часто туди квиток стоїть одну ціну, а назад — іншу). Тому ми будемо розрізняти два варіанта ЗК: симметричную завдання, коли умова (3) виконано, і несимметричную — інакше. Умови (2)-(4) по вмовчанням вважатимемо выполненными.

Друге зауваження стосується числа всіх можливих турів. У несиметричною ЗК все тури t=(j1,j2,., jn, j1) і t'=(j1,jn,., j2, j1) мають різну довжину, і повинні враховуватися обидва. Різних турів очевидно (n-1)!.

Зафіксуємо першою і останньому місці циклічною перестановці номер j1, а решта n-1 номерів переставимо усіма (n-1)! можливими способами. Через війну одержимо несиметричні тури. Симетричних турів є у два разів менша, т.к. кожен зарахований двічі: як t як і t'.

Можна уявити, що З полягає з одиниць і нулів. Тоді З можна інтерпретувати, як граф, де ребро (i, j) проведено, якщо Сij=0 і проведено, якщо Сij=1. Тоді, якщо є тур довжини 0, він пройде по циклу, що включає все вершини за одним разу. Такий цикл називається гамильтоновым циклом. Незамкнутый гамільтонів цикл називається гамильтоновой ланцюгом (гамильтоновым путём).

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

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

У несиметричною ЗК замість «цикл» кажи «контур», а замість «ребра» — «дуги» чи «стрелки».

Деякі прикладні завдання формулюються як ЗК, але у них потрібно мінімізувати довжину не гамильтонова циклу, а гамильтоновой ланцюга. Такі завдання називаються незамкнутыми. Деякі моделі зводяться до завданню про кількох коммивояжерах, однак коли ми туйки їх розглядати не будем.

1.2. Методи рішення ЗК.

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

Жадібний алгоритм — алгоритм перебування найкоротшого відстані шляхом вибору найкоротшого, не обраного ребра, за умови, що його не утворює циклу з роботи вже обраними рёбрами. «Жадібним» цей алгоритм названо адже останніх кроках доводиться жорстоко розплачуватися за жадность.

Подивимося, як поведеться під час вирішення ЗК жадібний алгоритм. Ось він перетвориться на стратегію «йди у найближчий (куди ще входив) місто». Жадібний алгоритм, очевидно, безсилий у цій завданню. Розглянемо приміром мережу на рис. 2, представляє вузький ромб. Нехай комівояжер стартує з міста 1. Алгоритм «йди ви найближчий місто» виведе їх у місто 2, потім 3, потім 4; на останньому кроці доведеться передплачувати жадібність, повертаючись по довгою діагоналі ромбу. Через війну це не є найкоротший, а довжелезний тур.

На користь процедури «йди у найближчий» можна сказати лише те, що з старті вже з міста вона поступиться стратегії «йди в дальнейший».

Як кажуть, жадібний алгоритм помиляється. Чи можна довести, що він помиляється помірковано, що отриманий ним тур гірше мінімального, між іншим, в 1000 раз? Ми доведемо, що цього довести неможливо, причому як для жадібного логарифма, а алгоритмів значно більше потужних. Але спочатку потрібно домовитися, як оцінювати похибка неточних алгоритмів, для визначеності, в завданню мінімізації. Нехай fB — справжній мінімум, а fA — той квазиминимум, який отримано за алгоритмом. Зрозуміло, що fA/ fB?1, але ці - тривіальне твердження, може бути похибка. Щоб оцінити її, потрібно затиснути ставлення оцінкою згори: |fA/fB ?1+ n?, |(5)|.

де, як у вищу математику, ??0, але, проти звичаю, то, можливо дуже великих. Розмір? і служитиме мірою похибки. Якщо алгоритм мінімізації задовольнятиме нерівності (5), мова йтиме, що він має похибка ?.

Припустимо тепер, що є алгоритм, А рішення ЗК, похибка що потребує оцінити. Візьмемо довільний граф G (V, E) і за ним складемо вхідну матрицю ЗК: |С[i, j]={ |1,если ребро (i, j) належить Є | | |1+n? інакше |.

Якщо графі G є гамільтонів цикл, то мінімальний тур відбувається за цьому циклу і fB = n. Якщо алгоритм, А теж завжди знаходитиме цей нелегкий шлях, то результатам алгоритму можна судити, чи є гамільтонів цикл в довільному графі. Проте, непереборного алгоритму, який міг би відповісти, чи є гамільтонів цикл в довільному графі, досі нікому невідомо. Таким чином, наш алгоритм, А повинен іноді помилятися і включатимуть в тур хоча б одне ребро довжини 1+n?. Але тоді fA ((n-1)+(1+n?) отже fA/fB=1+n? тобто. перевершує похибка? на задану нерівністю (5). Про величині? в нашому міркуванні ми домовлялися, отже? може бути насильно велик.

Отже доведено наступна теорема.

Або алгоритм, А визначає, чи існує у довільному графі гамільтонів цикл, або похибка При рішенні ЗК може бути насильно велика.

Це міркування було опубліковано Сані і Гонзалесом в 1980 р. Теорему Сани-Гонзалеса полягає в тому, що немає жодних обмежень на довжину ребер. Теорему не проходить, якщо відстані підпорядковуються нерівності трикутника (4).

Якщо він дотримується, можна запропонувати кілька алгоритмів з похибкою 12. Перш, ніж описати такий алгоритм, варто згадати старовинну головоломку. Чи можна накреслити однієї лінією відкритий конверт? Рис. 2 показує, які можна (цифри на відтинках показують порядок їх проведення). Закритий конверт (рис. 3.) однієї лінією намалювати не можна й ось чому. Будемо називати лінії ребрами, які перехрестя — вершинами.

Коли точку проводиться лінія, то використовується два ребра — одне для входу в вершину, одне — для виходу. Якщо рівень вершини нечетна — то ній лінія повинна початися чи скінчитися. На рис. 3 вершин нечетной ступеня дві: лише у лінія починається, на другий — закінчується. Проте за рис. 4 є чотири вершини ступеня три, але в однієї лінії може бути чотири кінця. Якщо ж треба увиразнити постать однієї замкнутої лінією, усі її вершини повинен мати четную степень.

Правильно і зворотне твердження: коли всі вершини мають четную ступінь, то постать накреслити однієї незамкнутій лінією. Справді, процес проведення лінії може скінчитися, лише коли лінія ввійде у вершину, звідки вже виходу немає: все ребра, приєднані до цією вершиною (зазвичай кажуть: инцидентные цією вершиною), вже прокреслено. Якщо за цьому намальована вся постать, то потрібне твердження доведено; якщо ні, видалимо вже намальовану частина G'. Після цього графа залишиться одна чи кілька зв’язкових компонент; нехай G' - одне з таких компонент. З огляду на связности вихідного графа G, G' і G'' мають хоч одну загальну вершину, скажімо, v. Якщо в G'' віддалені якісь ребра, то четному числу від транспортування кожної вершини. Тому G'' - зв’язний і всі його вершини мають четную ступінь. Побудуємо цикл в G'' (то, можливо, не намалювавши всього G'') і крізь v додамо прорисованную частина G'' до G'. Збільшуючи в такий спосіб прорисованную частина G', ми доможемося те, що G' охопить весь G.

Це завдання колись вирішив Эйлер, і замкнуту лінію, що покриває все ребра графа, тепер називаю эйлеровым циклом. Фактично було доведено наступна теорема.

Эйлеров цикл в графі існує тоді й тільки тоді, коли (1) граф зв’язний і (2) усі його вершини мають парні степени.

1.2.2. Дерев’яний алгоритм.

Нині можна обговорити алгоритм рішення ЗК через побудова найкоротшого остовного дерева. Для стислості називатиме цей алгоритм деревянным.

Спочатку обговоримо властивість випрямлення. Розглянемо якусь ланцюг, наприклад, на див. мал.5. Якщо справедливо нерівність трикутника, то d[1,3](d[1,2]+d[2,3] і d[3,5](d[3,4]+d[4,5].

Склавши ці дві нерівності, одержимо d[1,3]+d[3,5](d[1,2]+d[2,3]+d[3,4]+d[4,5]. По нерівності трикутника одержимо. d[1,5](d[1,3]+d[3,5]. Остаточно d[1,5](d[1,2]+d[2,3]+d[3,4]+d[4,5].

Отже, якщо справедливо нерівність трикутника, то тут для кожної ланцюга вірно, що відстань з початку остаточно ланцюга менше (або дорівнює) сумарною довжини всіх ребер ланцюга. Це узагальнення розхожого переконання, що пряма коротше кривой.

Повернімося до ЗК і опишемо вирішальний її дерев’яний алгоритм.

1. Побудуємо на вхідний мережі ЗК найкоротший остовное дерево і подвоїмо усі його ребра. Одержимо граф G — зв’язний і з вершинами, мають лише парні степени.

2. Побудуємо эйлеров цикл G, починаючи з вершини 1, цикл задається переліком вершин.

3. Переглянемо перелік вершин, починаючи із першого, і закреслювати кожну вершину, яка повторює вже зустрінуту в последовательности.

Залишиться тур, який і є результатом алгоритму. Приклад 1. Дана повна мережу, показана на див. мал.5. Знайти тур жадібним і дерев’яним алгоритмами. |- |1 |2 |3 |4 |5 |6 | |1 |- |6 |4 |8 |7 |14| |2 |6 |- |7 |11|7 |10| |3 |4 |7 |- |4 |3 |10|.

Рішення. Жадібний алгоритм (йди у найближчий місто із міста 1) дає тур 1-(4)-3-(3)-5(5)-4-(11)-6-(10)-2-(6)-1, де без скобок показані номери вершин, а дужках — довжини ребер. Довжина туру дорівнює 39, тур показано на рис. 5.

2. Дерев’яний алгоритм спочатку будує остовное дерево, показане на рис. 6 штрихової лінією, потім эйлеров цикл 1−2-1−3-4−3-5−6-5−3-1, потім тур 1−2-3−4-5−6-1 довжиною 43, який показаний суцільний лінією на рис. 6.

Теорему. Похибка дерев’яного алгоритму дорівнює 1.

Доказ. Візьмемо мінімальний тур довжини fB і видалимо потім із нього максимальне ребро. Довжина получившейся гамильтоновой ланцюга LHC менше fB. Але цю ланцюг можна як остовное дерево, т. до. ця ланцюг сягає все вершини і немає циклів. Довжина найкоротшого остовного дерева LMT менше, або дорівнює LHC. Маємо ланцюжок нерівностей |fB>LHC (LMT |(6)|.

Але подвоєну дерево — вона ж эйлеров граф — ми звели до туру у вигляді спрямлений, отже, довжина отриманого за алгоритмом туру задовольняє нерівності |2LMT>fA |(7)|.

Примножуючи (6) на дві голови і поєднуючи з (7), отримуємо ланцюжок нерівностей |2fB>2LHC (2LMT (fA |(8)|.

Тобто. 2fB>fA, тобто. fA/fB>1+(; (=1.

Теорему доказана.

Отже, ми довели, що дерев’яний алгоритм помиляється менш, ніж у двічі. Такі алгоритми вже називають приблизними, а чи не просто эвристическими.

Відомо ще кілька простих алгоритмів, які гарантують у найгіршому разі (=1. А, щоб знайти у тому числі алгоритм точніше, зайдемо з протилежного кінця й у початку опишемо «brute-force enumeration» — «перебір тваринної силою», як в англомовної літературі. Зрозуміло, що повний перебір практично застосуємо лише у завданнях малого розміру. Нагадаємо, що ЗК з n містами вимагає за повної переборі розгляду (n- 1)!/2 у симетричній завданню і (n-1)! Турів в несиметричною, а факторіал, як показано у наступному таблиці, зростає гнітюче швидко: |1 |- |0 |0 |3 |3 |6 | |2 |0 |- |1 |4 |1 |0 | |3 |1 |2 |- |0 |0 |3 | |табл. 4 |.

Викладемо алгоритм Литтла з прикладу 1 попереднього розділу. Повторно запишемо матрицю: |-|1 |2 |3 |4 |5|6 | |1|- |6 |4 |8 |7|14|.

Нам буде зручніше трактувати Сij як вартість проїзду із міста і в місто j. Припустимо, що добрий міський голова j видав указ виплачувати кожному въехавшему до міста її комівояжеру 5 доларів. Це означає, що кожен тур подешевшає п’ять доларів, що у будь-якому турі потрібно в'їхати до міста j. Але бо всі тури рівномірно подешевшали, то колишній мінімальний тур буде схвалений і тепер коштувати найменше. Добрий ж вчинок мера можна уявити, як зменшення всіх чисел j-го шпальти матриці З п’ять. Якби мер хотів спровадити комівояжерів з j-го міста Київ і встановив нагороду за виїзд до розмірі 10 доларів, можна було б висловити відніманням 10 з всіх елементів j-й тієї рядки. Це знову б змінило вартість кожного туру, але мінімальний тур був би мінімальним. Отже, доведено наступна лемма.

Віднімаючи будь-яку константу із усіх елементів будь-який рядки чи шпальти матриці З, ми залишаємо мінімальний тур минимальным.

Для алгоритму ми зможемо зручно отримати побільше нулів в матриці З, без там, проте, негативних чисел. І тому ми віднімемо з кожної рядки її мінімальний елемент (це й називається приведенням по рядкам, див. табл. 3), та був віднімемо з кожного шпальти матриці, наведеної по рядкам, його мінімальний елемент, отримавши матрицю, наведену по столбцам, див. табл. 4).

Прочерки по-діагоналі означають, що із міста і до міста і ходити не можна. Зауважимо, сума констант приведення по рядкам дорівнює 27, сума по столбцам 7, сума сум дорівнює 34.

Тур можна поставити системою з 6 підкреслених (виділених іншим кольором) елементів матриці З, наприклад, такий, як показано на табл. 2. Підкреслення елемента означає, що у турі з i-го елемента йдуть саме у j-тый. Для туру з 6 міст підкреслених елементів має бути шість, позаяк у турі з 6 міст є шість ребер. Кожен стовпець мусить мати рівно один підкреслений елемент (у кожний місто комівояжер в'їхав одного разу), у кожному рядку може бути рівно один підкреслений елемент (з кожного комівояжер виїхав одного разу); крім того, підкреслені елементи повинні описувати один тур, а чи не кілька менших циклів. Сума чисел підкреслених елементів є вартістю туру. На табл. 2 вартість дорівнює 36, що це мінімальний тур, який отримано лексикографічним перебором.

Тепер розмірковувати від наведеної матриці на табл. 2. Якщо ній зможуть вибудувати правильну систему підкреслених елементів, тобто. систему, що б трьом вищеописаним вимогам, і підкресленими елементами будуть лише нулі, то ясно, для цієї матриці ми матимемо мінімальний тур. Але він також буде мінімальним й у вихідної матриці З, лише тим, щоб отримати правильну вартість туру, потрібно буде назад додати все константи приведення, і вартість туру зміниться з 0 до 34. Отже, мінімальний тур може бути менше 34. Нас оцінку знизу всім туров.

Тепер приступимо до ветвлению. І тому проробимо крок оцінки нулів. Розглянемо нуль у клітині (1,2) наведеної матриці. Він означає, що ціна переходу із міста 1 до міста 2 дорівнює 0. Якщо ж ми підемо із міста 1 в місто 2? Тоді всі одно слід в'їхати до міста 2 за ціни, зазначені у другому стовпці; найдешевше за 1 (із міста 6). Далі, однак треба буде виїхати із міста 1 за ціну, зазначену У першій рядку; найдешевше до міста 3 за 0. Підсумовуючи ці дві мінімуму, маємо 1+0=1: а то й їхати «по нулю» із міста 1 до міста 2, треба заплатити незгірш від 1. Це і оцінка нуля. Оцінки всіх нулів поставлені на табл. 5 правіше і від нуля (оцінки нуля, рівні нулю, не ставились).

Виберемо максимальну з цих оцінок (в прикладі кілька оцінок, рівних одиниці, виберемо першу їх, у клітині (1,2)).

Отже, вибрано нульовий ребро (1,2). Розіб'ємо все тури на два класу — які включають ребро (1,2) і які включають ребро (1,2). Про другий клас можна сказати, доведеться приплатити ще 1, отже тури цього стоять 35 чи больше.

Щодо першого класу, у ньому треба розглянути матрицю на табл. 6 з вычеркнутой першої рядком і другим стовпцем. | |1|2|3|4|5|6| |1|-|0|0|3|3|6| | | |1| | | | | |2|0|-|1|4|1|0| | |1| | | | | | |3|1|2|-|0|0|3| | | | | |1| | | | |1|3|4|5|6| |2|0|1|4|1|0| | |1| | | | | |3|1|-|0|0|3| | | | |1| | | |4|4|0|-|1|3| | | |1| | | | |5|4|0|1|-|0| |6|7|3|3|0|-| | | | | |1| | |табл. 6 | | |1|3|4|5|6| |2|0|1|4|1|0| | |1| | | | | |3|0|-|0|0|3| | |3| |1| | | |4|3|0|-|1|3| | | |1| | | | |5|3|0|1|-|0| |6|6|3|3|0|-| | | | | |1| | |табл. 7 | | |3|4|5|6| |2|1|4|1|0| |4|0|-|1|3| | |1| | | | |5|0|1|-|0| |6|3|3|0|-| | | | |1| | |табл. 8 |.

Додатково в зменшеної матриці поставлений заборона у клітині (2,1), т. до. вибрано ребро (1,2) і замикати передчасно тур руба (2,1) не можна. Зменшену матрицю можна навести на 1 за першим стовпцю, отже кожен тур, їй відповідальний, стоїть незгірш від 35. Результат наших розгалужень і отримання оцінок показаний на див. мал.6. Гуртки представляють класи: верхній гурток — клас всіх турів; нижній лівий — клас всіх турів, які включають ребро (1,2); нижній правий — клас всіх турів, не які включають ребро (1,2). Числа над гуртками — оцінки снизу.

Продовжимо галуження у позитивний бік: вліво — вниз. І тому оцінимо нулі в зменшеної матриці C[1,2] на табл. 7. Максимальна оцінка в клітині (3,1) дорівнює 3. Отже, оцінка для правої нижньої вершини на рис. 7 є 35+3=38. Для оцінки лівої нижньої вершини на рис. 7 потрібно викреслити зі матриці C[1,2] ще рядок 3 і стовпець 1, отримавши матрицю C[(1,2); INSERT INTO `ref` (`id_predmet`, `name_predmet`, `id_ref`, `name_ref`, `text_ref`) VALUES (3,1)] на табл. 8. У цю матрицю потрібно поставити заборона у клітину (2,3), оскільки вже побудований фрагмент туру з ребер (1,2) і (3,1), тобто. [3,1,2], і треба заборонити передчасне замикання (2,3). Ця матриця наводиться по стовпцю на 1 (табл. 9), в такий спосіб, кожен тур відповідного класу (тобто. тур, у якому ребра (1,2) і (3,1)) стоїть 36 і більше. | |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|0| | | | |3| |4|0|-|3| | |3| | | |5|0|0|0| | | |3| | |табл. 10 | | |3 |4 | |4 |0 |- | |5 |0 |0 | |табл. 11 |.

Оцінюємо тепер нулі в наведеної матриці C[(1,2); INSERT INTO `ref` (`id_predmet`, `name_predmet`, `id_ref`, `name_ref`, `text_ref`) VALUES (3,1)] нуль з максимальної оцінкою 3 перебуває у клітині (6,5). Негативний варіант має оцінку 38+3=41. Для отримання оцінки позитивного варіанта прибираємо рядок 6 і стовпець 5, ставимо заборона у клітину (5,6), див. табл. 10. Ця матриця неприводима. Отже, оцінка позитивного варіанта не збільшується (рис.8).

Оцінюючи нулі в матриці на табл. 10, отримуємо галуження за вибором ребра (2,6), негативний варіант отримує оцінку 36+3=39, а отримання оцінки позитивного варіанта викреслюємо другий рядок і шостий стовпець, одержуючи матрицю на табл. 11.

У матрицю треба додати заборона у клітину (5,3), оскільки вже побудований фрагмент туру [3,1,2,6,5] і треба заборонити передчасний повернення (5,3). Тепер, коли залишилася матриця 2×2 з заборонами по-діагоналі, достраиваем тур ребрами (4,3) і (5,4). Ми недаремно гілкувалися, по позитивним варіантів. Зараз отримано тур: 1>2>6>5>4>3>1 вартістю 36. При досягненні низу по дереву перебору клас турів звузився до одного туру, а оцінка знизу перетворилася на точну стоимость.

Отже, все класи, мають оцінку 36 і від, кращого туру не містять. Тому відповідні вершини викреслюються. Викреслюються також вершини, обидва нащадка якої викреслені. Ми колосально скоротили повний перебір. Залишилося перевірити, зовсім позбавлений найкращого туру клас, відповідний матриці С[Not (1,2)], тобто. наведеної матриці із забороною у клітині 1,2, наведеної на 1 по стовпцю (що було оцінку 34+1=35). Оцінка нулів дає 3 для нуля у клітині (1,3), отже оцінка негативного варіанта 35+3 перевершує вартість вже отриманого туру 36 і негативний варіант отсекается.

Для отримання оцінки позитивного варіанта виключаємо з матриці перший рядок та третій стовпець, ставимо заборона (3,1) й одержуємо матрицю. Ця матриця наводиться по четвертої рядку на 1, оцінка класу сягає 36 і гурток закреслюється. Оскільки в вершини «все» вбиті обидва нащадка, вона убивається теж. Вершин не залишилося, перебір закінчено. Нас хоча б мінімальний тур, який показаний підкресленням на табл. 2.

Задовільних теоретичних оцінок швидкодії алгоритму Литтла і родинних алгоритмів немає, але практика показує, що у сучасних ЕОМ часто дозволяють вирішити ЗК з n = 100. Це величезний прогрес проти повним перебором. З іншого боку, алгоритми типу гілок і національних кордонів є, якщо неможливо доводити їх остаточно, ефективними эвристическими процедурами.

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

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

Можна запропонувати багато процедур вирішення цього завдання, наприклад, фізичне моделювання. На пласкою дошці малюється карта місцевості, в міста, що лежать на роздоріжжі доріг, вбиваются цвяхи, за кожен цвях надягається кільце, дороги вкладаються мотузками, які прив’язуються до відповідним кільцям. Щоб знайти найкоротший відстань між і і k, треба взяти I до однієї правицю і k до іншої і розтягти. Ті мотузки, які натянутся і дадуть розводити руки ширші й полягають утворюють найкоротшого шляху між і і k. Проте математична процедура, яка промоделирует цю фізичну, має дуже складно. Відомі алгоритми простіше. Одне з них — алгоритм Дейкстры, запропонований Дейкстрой ще 1959 г. Цей алгоритм вирішує загальну задачу:

У орієнтованої, неориентированной чи змішаної (т. е. такий, де частина доріг має одностороннє рух) мережі знайти найкоротшого шляху між двома заданими вершинами.

Алгоритм використовує три масиву з n (= числу вершин мережі) чисел кожен. Перший масив a містить мітки з цими двома значеннями: 0 (вершина ще не розглянута) і одну (вершина розглянуто); другий масив b містить відстані - поточні найкоротші відстані від vi до відповідної вершини; третій масив з містить номери вершин — k-й елемент ck є номер передостанній вершини на поточному найкоротшому шляхи виходу з vi в vk. Матриця відстаней Dik задає довжини дуг dik; якщо такий дуги немає, то dik присвоюється велика кількість Б, однакову «машинної бесконечности».

Нині можна описать:

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

1(инициализация).

У циклі від однієї до n заповнити нулями масив а; заповнити числом і масив з: перенести i-тую рядок матриці D в масив b; a[i]: =1; c[i]: =0; {i-номер стартовою вершины}.

2(общий шаг).

Знайти мінімум серед неотмеченных (т. е. тих k, котрим a[k]=0); нехай мінімум досягається на індексі j, т. е. bj (bk; a[j]: =1;

якщо bk>bj+djk то (bk:=bj+djk; ck:=j) {Умова означає, шлях vi. vk довші, ніж шлях vi. vj, vk. Якщо всі a[k] відзначені, то довжина шляху vi. vk дорівнює b[k]. Тепер потрібно перерахувати вершини, що входять до найкоротший путь}.

3(выдача ответа).

{Шлях vi. vk видається у порядку наступній процедурой:}.

3.1. z:=c[k];

3.2. Видати z;

3.3. z:=c[z]; Якщо z = 0, то кінець, інакше можливість перейти до 3.2.

На виконання алгоритму потрібно n раз переглянути масив b з n елементів, т. е. алгоритм Дейкстры має квадратичную складність. Проілюструємо роботу алгоритму Дейкстры численным прикладом (для більшої складності, вважаємо, деякі міста (вершини) i, j не з'єднані між собою, т. е. D[i, j]=?). Нехай, наприклад, i=3. Потрібна знайти найкоротші шляхи виходу з вершини 3. Вміст масивів a, b, c після виконання першого пункту показано на табл. 12:

Вочевидь, вміст таблиці змінюється принаймні виконання загального кроку. Це це випливає з наступній таблицы:

Однією з можливих недоліків такого алгоритму необхідно знати не матрицю відстаней, а координати кожного на площині. Якщо нам відома матриця відстаней між містами, але невідомі їх координати, то тут для їх перебування потрібно вирішуватиметься n систем квадратних рівнянь з n невідомими кожної координати. Вже для 6 міст це зробити дуже складно. Якщо ж, навпаки, є координати всіх міст, але немає матриці відстаней з-поміж них, то створити матрицю нескладно. Це можна легко зробити на умі для 5−6 міст. Для великої кількості міст можна скористатися можливостями комп’ютера, тоді як промоделировать рішення системи квадратних рівнянь за комп’ютером досить сложно.

За підсумками вищевикладеного можна дійти невтішного висновку, мій алгоритм, поруч із дерев’яним алгоритмом і алгоритмом Дейкстры, можна зарахувати до приближённым (хоча для цього алгоритмом жодного разу зазначалося видачі неправильного варианта).

1.2.6. Аналіз методів виконання завдання коммивояжера.

Для підбиття підсумків до вивчення методів рішення ЗК протестируем найоптимальніші алгоритми за комп’ютером за такими показниками: кількість міст, час обробки, ймовірність неправильного відповіді. Дані занесём в таблицю. |Алгоритм лексичного перебору | |У |Час обработки,|Вероятность неправильного |Тип | |міст |з |відповіді, % |алгоритму | |10 |41 |0 |точний | |12 |12 000=3ч.20мин |0 | | |32 |-* |0 | | |100 |-* |0 | | |Метод гілок і національних кордонів | |10 |~0 |0 |точний | |32 |~0.0001 |0 | | |100 |1.2 |0 | | |Мій алгоритм рішення ЗК | |10 |0.001 |0 |наближений| |32 |2.5 |0 | | |100 |6 |0 | |.

*- ЗК з такою кількістю міст методом лексичного перебору сучасний комп’ютер не міг би вирішити нам навіть за постійно існування Вселенной.

Як кажуть за результатами цієї таблиці, алгоритм лексичного перебору можна лише що стосується кількістю міст 5.12. Метод гілок і кордонів, поруч із моїм методом, можна використовувати завжди. Хоча мій метод я відніс до приближённым алгоритмам, він є точним, оскільки довести зворотне не удалось.

1.3 Практичне застосування завдання коммивояжера.

Окрім очевидної застосування ЗК практично, існує ще ряд завдань, приводяться до вирішення ЗК.

Завдання про виробництві фарб. Є виробничі лінії для виробництва n фарб різного кольору; позначимо ці фарби номерами 1,2… n. Усю виробничу лінію вважатимемо одним процесором. Вважатимемо також, що одноразово процесор виробляє тільки один фарбу, тому фарби потрібно провадити у деякому порядку Оскільки виробництво циклічне, то фарби мають провадитися в циклічний порядку (=(j1,j2,., jn, j1). Після закінчення виробництва фарби і і для початком виробництва фарби j треба відмити устаткування від фарби і. І тому потрібен час C[i, j]. Вочевидь, що C[i, j] залежить як від і, і від j, І що, взагалі говоря, C[i, j]?C[j, i]. При деякому обраному порядку доведеться на певний цикл виробництва фарб витратити время.

[pic].

Де tk — чисте час виробництва k-ой фарби (беручи до уваги переналадок). Проте друга сума правій частині постійна, тому повне час на цикл виробництва мінімізується разом із загальним часом проти переналадку.

Отже, ЗК і завдання про мінімізації часу переналагодження — це просто одне завдання, лише варіанти її описані різними словами.

Завдання про дыропробивном пресі. Дыропробивной прес виробляє велике число однакових панелей — металевих аркушів, у яких послідовно за одним пробиваються отвори різної форми і величини. Схематично прес можна як столу, двигающегося незалежно по координатам x, y, і обертового над столом диска, за периметром якого розташовані дыропробивные інструменти різної форми і величини. Кожен інструмент є у одному примірнику. Диск може обертатися однакова у двох напрямах (координата обертання z). Є власне прес, який надавлює на підвішений під нього інструмент тоді, як під інструмент підведено потрібна точка листа.

Операція пробивки j-того отвори характеризується четвіркою чисел (xj, yj, zj, tj), де xj, yjкоординати потрібного становища столу, zj — координата потрібного становища диска і tj — час пробивки j-того отверстия.

Виробництво панелей носить циклічний характер: на початку й кінці обробки кожного аркуша стіл має перебувати у положеннях (x0, y0) диск в становищі z0 причому у цьому становищі отвір не пробивається. Це початкова стан системи вважатимуться пробивкой фіктивного нульового отвори. З параметрами (x0,y0,z0,0).

Щоб пробити j-тое отвір одразу після i-того необхідно здійснити такі действия:

1. Перемістити стіл по осі x з цього становища xi у безвихідь xj, витрачаючи у своїй час t (x)(|xi-xj|)=ti, j (x).

2. Зробити той самий по осі y, витративши час ti, j (y).

3. Повернути голівку по найкоротшою з цих двох дуг з цього становища zi у безвихідь zj, витративши час ti, j (z) .

4. Пробити j-тое отвір, витративши час tj.

Конкретний вид функцій t (x), t (y), t (z) залежить від механічних властивостей пресу КПРС і досить громіздкий. Явно виписувати цих функцій немає необходимости.

Дії 1−3 (переналагодження з i-того отвори j-тое) відбувається одночасно, і пробивка відбувається відразу після завершення самого тривалого з цих дій. Поэтому.

С[i, j] = max (t (x), t (y), t (z)).

Тепер, як і попереднього разі, завдання складання оптимальної програми для дыропробивного преса зводиться до ЗК (тут — симметричной).

Выводы.

1. Вивчено евристичний, наближений і точний алгоритми рішення ЗК.

Точні алгоритми рішення ЗК — це повний перебір чи удосконалений перебір. Обидва вони широко, особливо перший, неефективні при великому числі вершин графа.

2. Запропоновано власний ефективний метод рішення ЗК з урахуванням побудови опуклого багатокутника і включення до нього центральних вершин (городов).

3. Проходив аналіз найбільш раціональних методів рішення ЗК і визначено сфери їхньої ефективного дії: для малої кількості вершин можна використовувати точний метод лексичного перебору; для значної частини вершин раціональніше застосовувати метод гілок і національних кордонів чи метод автора роботи (Аніщенка Сергія Александровича).

4. Вивчено практичні застосування ЗК і завдання з переналадками, сводимые до ЗК.

5. Наведено тексти програм, дозволяють вирішити ЗК різними методами.

1. Про. Оре Графи та їх застосування. Пер. з анг. під ред. І.М. Яглома. ;

М., «Світ», 1965, 174 с.

2. У. П. Сигорский. Математичний апарат інженера. — До., «Техніка»,.

1975, 768 с.

3. Ю. М. Кузнєцов, У. І. Кузубов, А. Б. Волощенко. Математичне програмування: навчальних посібників. 2-ге вид. перераб. і доп. — М.;

Вищу школу, 1980, 300 з., ил.

4. Є. У. Маркова, А. М. Лисенков. Комбінаторні плани в завданнях багаточинникового експерименту. — М., Наука, 1979, 345 с.

5. Є. П. Липатов. Теорія графів і її застосування. — М., Знання, 1986, 32 с.

6. У. М. Бондарєв, У. І. Рублинецкий, Є. Р. Качко. Основи програмування. — Харків, Фоліо; Ростов на Дону, Фенікс, 1998, 368 с.

7. Ф. А. Новиков Дискретна математика для програмістів. — Санкт;

Петербург, Пітер, 2001, 304 з., ил.

8. Приложения.

———————————- [pic].

[pic].

[pic].

[pic].

[pic].

[pic].

[pic].

[pic].

[pic].

[pic].

[pic].

[pic].