Като коментар, за решението на третата конкурсна задача предлагаме, с малки изменения, обяснението на миналогодишния победител от задочните кръгове на конкурса Петър Петров от София.

Поставената задача е един от вариантите на известната “задача за китайския пощальон” (Chinese Postman Problem). По-точно - вариантът с неориентиран, претеглен граф. При ориентиран граф, задачата се решава по-различно, и на практика доста по-лесно. В нашия случай един от етапите е особено труден - ефективното намиране на минимално по стойност перфектно съчетание (matching) в претеглен, пълен граф. Но за това по-късно.

За да изложим идеята на решението, най-напред ще припомним какво означава “Ойлеров цикъл” - това е цикъл, който преминава през всяко ребро в графа точно по веднъж. Един граф се нарича Ойлеров, ако за него съществува Ойлеров цикъл. Има теорема, която гласи, че даден неориентиран граф е Ойлеров тогава и само тогава, когато степента на всеки един от върховете му е четна.

Очевидно, ако графът е Ойлеров, тогава оптималното решение на нашата задача е един негов Ойлеров цикъл. Съответно, отговорът който трябва да изведем, е просто общата сума от дължините на ребрата в графа. Можем да отбележим, че това от кой връх започваме движението няма никакво значение в текущата задача.

По-интересно става, ако графът не е Ойлеров. Очевидно, в този случай ще трябва да минем по някои от ребрата повече от веднъж. И така, задачата може да бъде решена, ако успеем да “допълним” графа до Ойлеров по оптимален начин. Разбира се, допълването е чисто “виртуално”, целта му е да определи през кои точно ребра трябва да се мине повече от веднъж, така че да се получи най-добро решение. Щом веднъж определим кои са въпросните ребра, просто добавяме тяхната сума към общата сума на всички ребра, и получаваме търсения в задачата отговор.

Критични за решаването на задачата са върховете с нечетна степен. Лесно може да се докаже, че върховете с нечетна степен винаги са четен брой. Оказва се, че в оптималното решение “добавените” ребра образуват непресичащи се (по ребра) пътища, всеки от които свързва връх с нечетна степен с друг връх с нечетна степен (доказателства за това твърдение може да се намери в Интернет, на някои от адресите посочени по-долу). Очевидно, ако вземем един път между два такива върха, и повторим всички ребра, участващи в него, това ще доведе до промяна на четността на степените на двата крайни върха (точно това искаме), и ще запази четностите на степените на междинните върхове. Следователно, нашата цел е така да комбинираме два по два въпросните върхове (тези с нечетна степен), че общата дължина на пътищата, участващи в комбинациите да е минимална.

Първата стъпка е лесна - да намерим минималните разстояния между всеки два върха в графа. Това става с добре известния алгоритъм на Floyd, чиято сложност е O(N³). Може да се постигне и по-бързо решение, използвайки “сложната” версия на алгоритъма на Dijkstra, но според мен не си струва усилията. Така получаваме нов пълен граф, съставен от върховете с нечетна степен. Всяко ребро на този граф е с дължина равна на намерения на първа стъпка минимален път между краищата му. Следващата стъпка е трудната - намирането на минимално съчетание в пълния претеглен граф на върховете с нечетни степени. Това е известен проблем, за който съществуват ефективни, но сложни алгоритми. Първият ефективен (полиномиален) алгоритъм е предложен от Edmonds през 1965 г. Впоследствие проблемът е изследван допълнително и има няколко модификации на оригиналния алгоритъм, които са с подобрена сложност. В общи линии сложността на всеки от тях е близка до O(N3), т.е. не е по-лоша от вече използвания алгоритъм на Floyd. Неприятното е, че средната дължина на сорсовете на съществуващите имплементации е много голяма. В Интернет могат да бъдат намерени няколко доста добри такива имплементации (виж линковете по-долу).

Методът, използван от мен, е сравнително прост. Един елементарен greedy-алгоритъм, който на всяка стъпка съчетава двата най-близки върха, по принцип дава доста добри резултати. Причината те не винаги да са оптимални е, че понякога се оказва по-изгодно да “изпуснем” двата най-близки върха, за да останат свободни за друго съчетание. Забелязва се обаче, че това се случва сравнително рядко, и предимно в “нагласени” конфигурации. Ако ограничим допустимия брой на “изпусканията” до някое малко число - например 2 или 3, обикновеното пълно изчерпване ще има съвсем прилична сложност. Аз съм ги ограничил до 2, при което пълното изчерпване е със сложност O(N³). Разбира се, при големи стойности на N, не винаги се получава оптималния резултат. Добавил съм също така и един randomized алгоритъм от тип Monte Carlo, който дава добри (но не прекалено :) резултати за конкретната задача. Идеята е да “изпускаме” с определена вероятност, като променяме вероятностния коефициент. Ако увеличим броя опити, вероятността да уцелим оптималното решение нараства.

Интересни www-адреси по темата:
http://www.geocities.com/SiliconValley/Peaks/1667/
http://www.cs.mdx.ac.uk/harold/cpp/default.htm
http://www.or.uni-bonn.de/home/rohe/matching.html
http://elib.zib.de/pub/Packages/mathprog/matching/weighted/index.html

Какво може да се добави към анализа на Петър Петров? На една от посочените по-горе страници в Интернет може да бъде намерена реализация на алгоритъм за намиране на перфектно съчетание с минимална цена в претеглен неориентиран граф, известна като Blossom IV. Участниците, които са решили да използват тази реализация видимо са направили най-правилния избор. Колкото и добре да е замислен един greedy алгоритъм, в общия случай той не може да намери оптималното решение. Очевидно е, че добре написан backtraking ще намери оптимални решения, но това ще става за време, което надхвърля определеното за тестване.