1.3.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]

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

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

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

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

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

Приклад 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
4	8	11	4	-	5	11
5	7	7	3	5	-	7
6	14	10	10	11	7	-
табл. 1

Рішення. Жадібний алгоритм (йди в найближче місто із міста 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-forceenumeration» - «перебір тваринної силою», як його називають в англомовній літературі. Зрозуміло, що повний перебір практично застосуємо тільки в задачах малого розміру. Нагадаємо, що ЗК з n містами вимагає при повному переборі розгляду (n-1)! / 2 турів в симетричній завданню і (n-1)! Турів в несиметричною, а факторіал, як показано в наступній таблиці, зростає гнітюче швидко:

5!	10!	15!	20!	25!	30!	35!	40!	45!	50!
~102	~106	~1012	~1018	~10125	~1032	~1040	~1047	~1056	~1064

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

Нехай є деякий алфавіт і набори символів алфавіту (букв), звані словами. Букви в алфавіті впорядковані: наприклад, в російській алфавіті порядок букв абя (символ  читається «передує)». Якщо заданий порядок букв, можна впорядкувати і слова. Скажімо, дано слово u = (u1, u2, .., um) - складається з букв u1, u2, .., um - і слово v = (v1, v2, .., vb). Тоді якщо u1v1, то і uv, якщо ж u1 = v1, то порівнюють другу букви і т.д. Цей порядок слів і називається лексикографічним. Тому в російських словниках (лексиконах) слово «абажур» стоїть раніше слова «абака». Слово «бур» стоїть раніше слова «бура», бо пробіл вважається попереднім будь букві алфавіту.

Розглянемо, скажімо, перестановки з п'яти елементів, позначених цифрами 1..5. Лексикографічно першої перестановкою є 1-2-3-4-5, другий - 1-2-3-5-4, ..., останньою - 5-4-3-2-1. Потрібно усвідомити загальний алгоритм перетворення будь перестановки в безпосередньо наступну.

Правило таке: скажімо, дана перестановка 1-3-5-4-2. Потрібно рухатися по перестановці справа наліво, поки вперше не побачимо число, менше, ніж попереднє (у прикладі це 3 після 5). Це число, Pi-1 треба збільшити, поставивши замість нього якесь число з розташованих правіше, від Pi до Pn. Число більше, ніж Pi-1, безсумнівно, знайдеться, так як Pi-1 <Pi. Якщо є кілька великих чисел, то, очевидно, треба ставити менше з них. Нехай це буде Pj, j> i-1. Потім число Pi-1 і всі числа від Pi до Pn, не рахуючи Pj потрібно впорядкувати по зростанню. В результаті вийде безпосередньо наступна перестановка, у прикладі - 1-4-2-3-5. Потім вийде 1-4-2-5-3 (той же алгоритм, але спрощений випадок) і т.д.

Потрібно розуміти, що в ЗК з n містами не потрібні всі перестановки з n елементів. Тому що перестановки, скажімо, 1-3-5-4-2 і 3-5-4-2-1 (останній елемент з'єднаний з першим) ставлять одне і те ж тур, лічений спершу з міста 1, а потім з міста 3 . Тому потрібно зафіксувати початковий місто 1 і приєднувати до нього всі перестановки з інших елементів. Цей перебір дасть (n-1)! різних турів, тобто повний перебір в несиметричною ЗК (ми як і раніше будемо розрізняти тури 1-3-5-4-2 і 1-2-4-5-3).

Даний алгоритм описаний мовою Паскаль (див. Додатки).

Приклад 2. Вирішимо ЗК, поставлену в Прімері 1 лексикографічним перебором. Наведена вище програма надрукує міста, складові кращий тур: 1-2-6-5-4-3 і егодліну 36.

Бажано удосконалити перебір, застосувавши розум. У наступному пункті описаний алгоритм, який реалізує просту, але широко застосовну і дуже корисну ідею.