Chinese postman problem

Ойлеров цикъл. Задача за Китайския пощальон.

Ойлеров цикъл

Доста популярен и любопитен факт е, че Ойлер е обявен от много умни глави, за бащата на Теорията на Графите1. Приносът на Ойлер е, че сам е съставил и решил първата задача на тема графи. Вдъхновили го мостовете в град Кьонигсберг (Königsberg), Прусия. Ето как изглеждала обстановката по реката, съответно примерния граф с който Ойлер си е блъскал главата.
konigsbergbridges2ie6.png
В скучния свят на ребра и върхове, това изглежда така:
eolershitzw8.jpg
Наглед простата задача - "може ли да обходя всички мостове и пак да съм на брега, от който съм тръгнал?", ражда красив проблем, решението на който се използва и днес, например в разшифроването на човешкия геном.

Задача: В даден неориентиран граф G = (V, E) да се намери път(цикъл), който да започне и завърши в даден връх v от V, такъв че минава (пътя) през всички ребра в графа.

Решението на Ойлер е просто, дал е дефиниция точно в какви графи е решима задачата2.

Теорема: За да е решима задачата на Ойлер, е нужно степените на върховете на графа да са четни.

Дефиниция: Ойлеров цикъл в граф наричаме цикъл, който минава през всички ребра на графа.
Дефиниция: Ойлеров път между два върха a и b от V, наричаме път между a и b, такъв че минава през всички ребра на графа. В случая

Теорема: В неориентиран свързан граф G = (V, E) съществува Ойлеров път тогава и само тогава, когато има 0 или 2 върха с нечетна степен. В случая, когато всички върхове са със четна степен, съществува цикъл (или път от а до а).
Както се досещате, това е обобщение на задачата на Ойлер.

Алгоритъм за намиране на Ойлеров цикъл в неориентиран, свързан граф с четни степени на върховете

Алгоритъм 1 - този който беше обяснен на лекции

Инициализация:
избираме произволно υ (това е ню в unicode xD) = v0, ;
Ks = 0, за всяко s от V - идентификатор, с помощта на който после ще възстановим (обединим) цялостния цикъл - решение на задачата.
marki = false, за всяко i от E - маркировка на ребрата, използвано ли е даденото ребро или подлежи на обхождане;
Ще ни е нужен и двумерен масив L : L[i][j] = k значи, че на j-тото посещение на върха i сме отишли на връх k. Отново ще го ползваме накрая, с масива K.

Action:
i) избираме произволно неизползвано ребро i = (υ, y)

  1. marki = true;
  2. Kυ++;
  3. Lυ(Kυ) = y;
  4. ако y има инцидентно неизползвано ребро отиди на ii)
  5. иначе (y == v0), отиди на iii)

ii) υ = y, goto i)

iii) Нека λ0 е произволен връх с непосетено инцидентно ребро.

  1. съществува λ0, тогава υ = λ0, goto i)
  2. не съществува λ0, goto iv)

iv) Конструираме цикъла, начало е v0. Ако отиваме във връх x, го напускаме по Lx(Kx), Kx = Kx - 1;

Както казах, употребата на алгоритъма е сравнително широка. Освен че се ползва за решаването на други основни задачи от теорията на графите, като задачата за Китайския пощальон, с която ще се занимаем след малко, алгоритъмът е приложим и за решаване на реални проблеми (просто няма как хляб от Фантастико да си купиш, без да си го научил). Ето и примерна задача http://acm.uva.es/p/v100/10054.html (online judge @ http://icpcres.ecs.baylor.edu/onlinejudge/ , Browse Problems -> Contest Volumes -> Volume C -> 10054 - The Necklace).

Алгоритъм 2 - евентуално по-лесен за писане и разбиране.

Идеята е същата, просто имплементацията е по-различна.

Инициализация:
списък L - тук ще получим крайния резултат, само че в обратен ред;
с curNode ще бележим върха, който в момента разглеждаме;
стек S - тук пазим временния резултат докато обхождаме ребрата;
S = {v0} първоначално;

Action:
i) curNode = top of S;
ii) ako curNode няма необходени инцидентни ребра:

  1. слагаме curNode в края на L (L.append(curNode));
  2. pop S;

iii) иначе, за произволно необходено ребро (curNode ,i)

  1. трием реброто (или просто го маркираме за обходено)
  2. push i to S;
  3. goto i)

Забележка: горният алгоритъм е просто създаден за рекурсия (DFS), но нали досега всички излагани алгоритми ги разглеждаме итеративно…

Chinese Postman Problem

Задача: Даден е произволен, свързан, неориентиран граф G=(V, E, e) с цени по ребрата (ei - цена на реброто i от E), като цените са неотрицателни (за да има решение задачата). Намерете цикъл, който минава поне по един път през всички ребра от графа, такъв че цената на този цикъл да е минимална.

Приликата със задачата на Ойлер е очевидна, тя дефакто решава частен случай на задачата за китайския пощальон (КП). Остава само да попроменим графа от КП, така че да му приложим алгоритъма, за намиране на Ойлеров цикъл. Нужно е да се промени степента на всички върхове от нечетна степен. Ясно е, че премахването на ребра, за да сторим горното, би било крайно грубо, и би ни докарало до грешен краен отговор. Затова ще прибавяме ребра и то не точно прибавяме, а размножаваме. Ще създадем копия на вече съществуващи ребра, така че да докараме графа до граф с Ойлеров цикъл. Естествено избора на ребра, които да бъдат копирани е доста важен, и е свързан с условието за минималност на теглото на цикъла. На помощ за избора идва създателя на проблема - Мей-Ко Куан.

Теорема 1 на Мей-Ко Куан: в оптималното решение на задачата за Китайския Пощальон, не съществува ребро с повече от едно копие.


Теорема 2 на Мей-Ко Куан: Във всеки цикъл на графа, сумата от теглата на добавените (копия) ребра не трябва да надвишава половината от цялостната сума на ребрата в цикъла.

Твърдението е що-годе интуитивно, поне според преподавателя, защото ако сумата на добавените ребра е повече от половината цялостна сума, то ако разменим избора, за копия на ребра, ще получим по-оптимално решение. Никакви практични следствия от теорема 2 не са ми известни (ако много си играе човек може да направи експоненциален алгоритъм за задачата чрез проверка на цикли), но все пак е полезно да се знае :)

Алгоритъм за Chinese Postman Problem (в неориентиран граф)

Нека е даден свързан, неориентиран граф G = (V, E), където di е степента на връх i, за всяко i от V.

i) Ако di е четно, за всяко i от V, то не търсим нищо друго освен Ойлеров цикъл в графа - прилагаме алгоритъма от първата част на темата. Иначе преминаваме към ii).

ii) Създаваме индуциран пълен подграф G` = (V`, E`), където:

  1. V` = {i | i от V && di е нечетно}
  2. E` = {(i`, j`) | i` , j` от V` && e(i`, j`) = цената на най-късия път от i до j в G}
  3. Намираме максимален matching M в G`.
  4. продължаваме с iii)

iii) По построение, всяко ребро φ от M, съответства на път в G. За всяко ребро φ от G` в M, обхождаме и правим копие в E- на всяко ребро от съответния път в G. Като обходим всички φ, модифицираме началния граф до $\mbox{G = (V, } E\bigcup E^-)$. goto i).

Забележка: След изпълнение на стъпка ii), която е най-трудна и важна в изпълнението на алгоритъма, сме постигнали 2 много важни неща:

  1. поправили сме степента на всички върхове в графа (така де, на тия които имаха нужда от поправка), до четна степен;
  2. открили сме точния минимум на функцията от задачата - сумата от теглата на ребрата по цикъла е равна на сумата на теглата на всички ребра от модифицирания G. Остава само да изпълним алгоритъма за Ойлеров цикъл, за да видим и конкретното решение.

Алгоритъм за Chinese Postman Problem (в ориентиран граф)

Този вариант на задачата е сходен с неориентирания, нужни са малки промени, като цялостната сложност на Време за изпълнение и имплементиране е значително по-малка.

Като начало, поставяме основите с Теорема на Ойлер (вариант за ориентирани графи): В ориентиран граф G = (V, A) има Ойлеров цикъл т.с.т.к. степента на вход (d+i) на всяко i от V е равна на степента на изход (d-i). За такъв граф G казваме, че е симетричен.

Алгоритъмът за намиране на Ойлеров цикъл в симетричен граф е аналогичен с този от неориентирания случай, иска само малки модификации, няма да се спирам на него. Какво да правим с нашия изтормозен китайски приятел, как да му кажем да си обходи района, та да не се "мине" с излишни раходки? Ами решението на задачата в този вариант е що-годе аналогично, пак правим копия. Начинът за подбор на дъгите е моментът, където решението се различава. Отново търсим най-къси пътища, но matching-а вече е bipartite matching, тоест избягваме от тегавия за писане General matching алгоритъм. Ето какво правим:

  1. означаваме Di = d-i - d+i , за всяко i от V;
  2. образуваме двуделен граф от върховете с цени между тях, определени от избрания алгоритъм за най-евтин път. В него пускаме ценово-зависим поток (Min-Cost Max-Flow) от върховете i с по-малко изходни ребра (Di > 0) към върховете j с по-малко входни ребра (Dj < 0).

Забележка: В някои специфични графи, решаването на проблема за КП е NP-пълна задача. Пример са смесени графи - графи с ориентирани и неориентирани дъги.

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-NonCommercial-ShareAlike 3.0 License