Класове оптимизационни задачи за най-къс път.
Основните класове задачи за най-къс път са :
- най-къси пътища от даден връх до всички останали;
- най-къс път между два дадени върха от графа;
- най-къс път от всеки връх в графа, до всеки друг връх;
По-горните класове задачи ще бъдат разглеждани за графи със следните характеристики:
- графи, в които теглото на всяко ребро е неотрицателно число;
- произволни графи, с произволни тегла на ребрата;
- ациклични графи;
- графи, в които теглото на всяко ребро е 1;
Алгоритми за решаване на задачи за най-къс път в граф.
Естествено началото е за един от най-комерсиалните алгоритми - алгоритъмът на Дейкстра (Dijkstra). Причините, поради които този алгоритъм е толкова известен са няколко. Той е доста понятен и някак естествен (в сравнение с други алгоритми за решаване на същия тип задачи). Лесно се имплементира на PC и прилага на лист. Когато се наложи да се ползва, всичко, което е нужно, е малко практика. Дава добри резултати при имплементация на PC откъм време, с някои оптимизации естествено.
Алгоритъм на Дейкстра
Преди да изложа алгоритъма, първо някои пояснения:
Ще вземем граф G(V, A) с N върха и неотрицателни стойности на дъгите (ще видим по-късно защо това е от значение), номерирани от 1 до N. Избираме като начален връх върха с номер 1 и ще търсим най-късите пътища от него до всички останали.
нека с:
- $d_i$ бележим най-късия път от връх $1$ до връх $i$.
- $d^*_i$ бележим временно най-късия път от връх $1$ до връх $i$.
- curNode запишем върхът, който сме избрали да прибавим на дадената стъпка от алгоритъма.
- S осначим множеството на всички върхове от графа, за който още не знаем най-късия път до тях.
- $l(i, j)$ означим теглото на реброто с начало връх $i$ и край връх $j$.
- с $prev_i$ ще означаваме предшественика на върхът $i$ по пътя от връх $1$ до връх $i$, иначе казано това ще е нашият списък на бащите. Тук е важно да се направи една забележка: Запаметяването на пътя по този линеен по памет начин е единствено осъществимо от факта, че най-късият път, между всеки два върха в нашия граф, е прост. Последното следва от липсата на отрицателни цикли. От това, че алгоритъмът намира прости пътища, следва че графът $G`(V, A`)$, подграф на $G$ със същите върхове, но с дъги само дъгите участващи в най-късите пътища от $1$ до всички останали върхове, и без ориентация на дъгите, всъщност е дърво (последното е доста важно).
Ето и самият алгоритъм.
Първоначално настройваме:
- $S = {1, 2, 3 ... N}$;
- $d^*_i = \inf$, за всяко $i = 1$ да $N$;
- $d^*_1 = 0$;
- $prev_i = -1$, за всяко $i = 1$ до $N$;
Действията извършвани във всяка стъпка от алгоритъма:
- dcurNode = d*curNode;
- S = S / {curNode};
- Ако $S = \varnothing$, край;
- за всеки връх j от S , такъв че $(curNode, j) \in A$, преизчисляваме : ако d*j > dcurNode + l(curNode, j), то prevj = curNode и разбира се d*j = dcurNode + l(curNode, j);
- минаваме през всеки елемент от S и избираме елемента j с най-къс временно най-къс път d*j ,избираме curNode = j;
- отиваме на 1-а стъпка от алгоритъма;
Лема Да докажем, че избраният за curNode на всяка стъпка връх действително притежава качеството временно най-късият до него път d*curNode да е и глобално най-къс.
Доказателство
Сложност на алгоритъма на Дейкстра Сложност поначало не сме дефинирали като отделно понятие, но не мисля да се впускам в обяснения. Който иска може да потърси из нета материали по темата, останалите - ще се учи някъде около четвърти семестър. Като цяло, алгоритъмът на Дейкстра "върви" (или влиза в нова стъпка) докато $S \ne \varnothing$ и на всяка стъпка добавя по един връх, следователно имаме N на брой стъпки, където N е броят на върховете. Във всяка стъпка, действие 4 изисква да се обходят всички съседи на curNode, а на действие 5 преминаваме през всички "неизбрани" до момента върхове, за да фиксираме най-оптималния. Другите действия - 1, 2, 3, 6 - са с константна сложност (О(1)). Като имаме предвид, че не разглеждаме мултиграф, може да приемем че стъпка 4 е с не по-голяма сложност от стъпка 5 (в общия случай), а стъпка 5 е с линейна сложност (O(N)), следователно сложността на всяка стъпка е линейна (сложността на една стъпка е сложността на най-скъпото действие в нея). N на брой стъпки с O(N) сложност ни дават O(N2) сложност. Тук идва един тънък момент, който не бива да се пропуска - сумирането на действие 4 от всяка от N-е стъпки ни дава общия брой на ребрата - M, заради което сложността на алгоритъма без оптимизации достига O(M + N2) = O(N2)( N2 ≥ M ⇒ 2N2 ≥ M + N2 ). Kогато започнем да оптимизираме, това M не е за изпускане, понеже не може да не прегледаме всички ребра, тоест си остава в сложността на алгоритъма, колкото и да оптимизираме останалата част. С оптимизации е възможно да ускорим изпълняването на стъпка 5 до логаритмична сложност (O(log2N)) с помощта на абстрактна структура от данни, наречена пирамида heap, което ни дава O(M + Nlog2N) оптимална сложност на алгоритъма.
Сега да видим как работи алгоритъмът с един прост пример. По принцип няма да има примери след всеки алгоритъм, защото това би било излишно, но поради популярността му смятам че е добре да бъде максимално понятно обяснен.
Нека нашият неориентиран (за алгоритъма ориентацията на графа е без значение) граф G(V, A) има следните характеристики
|
Матрица на съседство:
|
Цел: да се намерят най-късите пътища от връх 1 до всички останали.
Инициализацията е ясна, ето какво се случва при прилагането на алгоритъма по стъпки. В таблицата, за всеки връх динамично се подновява стойността на временно най-късия път, докато съответният връх все още се намира в S. i-ият ред съответства на i-та стъпка от алгоритъма, или по-точно информацията, с която разполагаме в началото ѝ. Щом даден връх бива избран за curNode на дадена стъпка, то в реда съответстващ на стъпката той ще е с удебелен шрифт.
стъпка N# | d*1 | d*2 | d*3 | d*4 | d*5 | d*6 |
1 | 0 | inf | inf | inf | inf | inf |
2 | 0 | inf | 5 | 8 | inf | inf |
3 | 0 | inf | 5 | 7 | 8 | inf |
4 | 0 | 10 | 5 | 7 | 8 | 14 |
5 | 0 | 10 | 5 | 7 | 8 | 14 |
6 | 0 | 10 | 5 | 7 | 8 | 12 |
Ето и нещо за хората които си купуват списания и книги заради картинките(като мен), - визуална реализация на написаното в таблицата:
Забележка: Картинките са взети директно от сайта на Американската олимпиада по информатика. Надяваме се да не ни съдят :)
Примерна задача : http://acm.timus.ru/problem.aspx?space=1&num=1031.