Strona główna

Treść zadania: najdłUŻszy cykl (longest circuit)


Pobieranie 51.62 Kb.
Data18.06.2016
Rozmiar51.62 Kb.

  1. Treść zadania:



NAJDŁUŻSZY CYKL (LONGEST CIRCUIT)

INSTANCJA: Graf , długość dla każdej krawędzi oraz .

PYTANIE: Czy istnieje cykl prosty w o długości lub większej, tj. taki którego suma długości krawędzi wynosi co najmniej ?

Wersja optymalizacyjna


Zmienne decyzyjne: cykl prosty

Cel:



  1. Algorytm siłowy.



Algorytm siłowy zgodnie z nazwą oraz ideą działania generuje wszystkie możliwe rozwiązania problemu i wybiera z nich to, które maksymalizuje funkcję celu, czyli

w naszym przypadku znajduje cykl o największej długości. Działanie naszego algorytmu oparte jest na metodzie przeglądania grafu w głąb – DFS. W ten sposób procedura szukająca cykl generuje wszystkie możliwe ścieżki w grafie i sprawdzając zachodzenie incydencji pomiędzy wierzchołkami początkowym i końcowym na ścieżce osądza

o istnieniu tegoż cyklu . Cała operacja wyszukiwania jest wywoływana dla wszystkich wierzchołków grafu ustalanych po kolei jako wierzchołek startowy.

Analizując działanie algorytmu możemy wyróżnić etapy:



/*wypunktuj poniższa listę żeby wszystkie opisy metod miały ten sam format, będzie ladniej i bardziej spójnie*/

  • Procedura rozpoczyna swoje działanie z dwoma argumentami: wierzchołkiem

startowym oraz aktualnie przetwarzanym i w pierwszej kolejności sprawdza czy

istnieje między nimi krawędź, co przy pomyślnym wyniku testu pociąga za sobą

istnienie cyklu.


  • Jeśli cykl istnieje to badamy jego długość i ewentualnie uaktualniamy dotychczasowe

rozwiązanie.

  • Następnie dla wszystkich sąsiadów aktualnie przetwarzanego wierzchołka

rekurencyjnie wywołujemy procedurę przeszukującą.

  • W ten sposób wraz z kolejnymi „zagłębieniami rekurencyjnymi” generowane

są ścieżki w grafie dla których badany jest warunek istnienia cyklu.

Jeśli dalsze wywołania rekurencyjne nie są możliwe z powodu przetworzenia

wszystkich wierzchołków incydentnych na danym poziomie rekurencji, wtedy

algorytm dokonuje nawrotu o jeden „poziom wyżej” w hierarchii wywołań

rekurencyjnych i wybiera następny nie przetworzony jeszcze wierzchołek,

co z kolei prowadzi do wygenerowania nowych ścieżek.



  • Jeżeli postępujące nawroty doprowadzą do ponownej analizy wierzchołka

startowego, oznacza to , że zostały wygenerowane wszystkie ścieżki w grafie rozpoczynające się od danego wierzchołka startowego.

  • Następnie ustalany jest jako startowy kolejny wierzchołek grafu, a cała procedura

jest powtarzana.


Przykład działania:

Niech dany będzie graf , który w pliku wejściowym zapisany jest następująco:




8
5


1


5

0

1

4
0

0 1 4

0
6

7

8

9
2 7

0


2

3
4 9

0


4

2
5 5

1
2


2 6

1


6

3

5
6 8

2


7
3 2

3 6 2


4 7 5

5 7 3







Rozpoczynamy procedurę wyszukiwania cykli od wierzchołka 0. Wykonujemy operacje przeglądania w głąb DFS wybierając wierzchołki zgodnie

z uporządkowaniem rosnącym. W ten sposób tworzy się pierwsza ścieżka: 0-1 a następnie 0-1-2.

Na tym etapie pierwszy raz zachodzi potrzeba sprawdzenia czy istnieje krawędź pomiędzy 2 a 0,

co zapewni nam istnienie cyklu. Test kończy się pomyślnie, zatem mamy pierwszy cykl , którego długość wnosi 17.






Przeglądanie jednak się nie kończy na tym etapie ponieważ zgodnie z zasadą działania DFS kolejne wywołania rekurencyjne dodają do naszej ścieżki wierzchołki 3 oraz 6.Mamy więc ścieżkę 0-1-2-3-6.

W tym momencie zajdzie jednak potrzeba wykonania nawrotu, ponieważ wierzchołek 6 nie ma już nie przetworzonych sąsiadów, a ponadto test na istnienie krawędzi łączącej go z wierzchołkiem 0 zakończył się fiaskiem.



Z tych samych przyczyn dokonamy nawrotu także z wierzchołka 3. Nawrót konieczny będzie także

z wierzchołka 2, bo choć wchodzi on w skład cyklu znalezionego wcześniej, to jednak zasada działania DFS wymusza przeglądnięcie pozostałych incydentnych

i nie odwiedzonych wierzchołków. W naszym przypadku oznacza to wywołanie rekurencyjne

dla wierzchołka 6, który w tym momencie jest znów interpretowany jako wierzchołek dotychczas nie odwiedzony (odznaczyliśmy go bowiem dokonując nawrotu – jest to różnica w stosunku do standardowego zachowania DFS) .





Na tym etapie aktualną ścieżką jest 0-1-6.

Kolejne wywołania rekurencyjne dodadzą do niej także wierzchołek 3 ,a następnie 2.

Dalsze zagnieżdżenie rekurencji nie będzie możliwe

z uwagi na fakt, że wierzchołki 0 oraz 1 już odwiedziliśmy, jednakże test na istnienie krawędzi pomiędzy 2 ,a wierzchołkiem początkowym czyli 0 zakończy się pomyślnie co zaowocuje stwierdzeniem istnienia cyklu 0-1-6-3-2-0 o długości 23, która jest największa z dotychczas uzyskanych i stanie się nową wartością funkcji celu.

Dalsze kroki algorytmu spowodują wykonanie nawrotów aż do wierzchołka 0, skąd analogicznie zostanie rozpoznany cykl 0-4-7-5-0.

Następnie cała procedura zostanie wywołana dla kolejnych wierzchołków startowych

(1,2, ... ,7).
Złożoność:

Analizując złożoność algorytmu siłowego nasuwa się spostrzeżenie (zgodnie z intuicją popartą informacją o tym, że algorytm korzysta z metody przeszukiwania DFS), że nasz algorytm powinien mieć złożoność równą złożoności algorytmu DFS czyli

O(|V|+|E| ) pomnożonej przez liczbę jego wywołań czyli n (tyle bowiem mamy wierzchołków startowych). Jednakże modyfikacje jakie zastosowaliśmy powodują, że metoda przeszukiwania odpowiada tej rozwiązującej problem znajdowania cyklu Hamiltona w grafie.

Jest to algorytm wykładniczy o złożoności . Zwróćmy uwagę, że algorytm szukający cyklu Hamiltona generuje wszystkie możliwe ścieżki w grafie, w sytuacji, gdy cykl Hamiltona nie istnieje w zadanym grafie. Nasz algorytm natomiast zawsze generuje wszystkie istniejące ścieżki. Stąd już prosty wniosek, że skoro nasz algorytm działa na tej samej zasadzie co ten szukający cyklu Hamiltona i ponadto wykonywany jest n-krotnie, to złożoność algorytmu siłowego będzie wynosiła .



  1. Algorytm branch & bound .

Idea algorytmów wykorzystujących strategie branch & bound opiera się na prostej zasadzie: szukając optymalnego rozwiązania zawsze zapamiętujemy najlepsze dotychczas uzyskane i jeżeli wartość/jakość kolejnego potencjalnego rozwiązania będzie według naszej oceny (oszacowania,heurystyki) gorsze od dotychczasowego, to obliczanie takiego rozwiązania nie jest wykonywane.


Stosując tę zasadę w przypadku algorytmu rozwiązującego nasz problem, modyfikujemy

algorytm siłowy.



  • Ustalamy dwa ograniczenia: dolne – lower bound ,oznaczmy je w skrócie jako LB

górne - upper bound, oznaczmy je w skrócie jako UB

  • LB będziemy identyfikować jako aktualnie najlepszą wartość funkcji celu znalezionej przez algorytm dotychczas ( czyli będzie to w naszym przypadku równoważne z długością najdłuższego cyklu znalezionego w trakcie działania algorytmu)

  • UB natomiast wyznaczymy sumując długość aktualnie badanej ścieżki oraz wartości wag wszystkich krawędzi dotychczas jeszcze nie przetworzonych przez algorytm, z wyjątkiem tych, które są incydentne z wierzchołkami aktualnej ścieżki

i które są incydentne z wierzchołkiem startowym dla którego procedura wyszukiwania już się zakończyła. Otrzymana w ten sposób suma jest największą długością potencjalnej ścieżki, którą właśnie badamy.

  • Jeżeli na pewnym etapie algorytmu oszacowanie UB da wynik mniejszy od LB,

to wiemy, że dalsze badanie aktualnej ścieżki jest zbędne ponieważ i tak nie

uzyskamy korzystniejszej wartości funkcji celu.


Metoda ta, daje w przypadku naszego problemu znajdowania najdłuższego cyklu bardzo wymierne efekty. Pozwala uniknąć wielu zbędnych wywołań rekurencyjnych procedury dzięki nawrotom wykonanym wcześniej na skutek oszacowania, że UB < LB.

Różnica w szybkości otrzymywania rozwiązania pomiędzy algorytmem siłowym,

a tym wykorzystującym strategię branch & bound jest tym większe, im większe jest nasycenie grafu krawędziami oraz im większa jest amplituda wartości wag krawędzi w grafie.
Ideę branch & bound ilustruje przykład:

Załóżmy, że mamy pewien graf o dużej liczbie wierzchołków, a na rysunku widzimy jego fragment.


7

1


3

6

0


2

2

3


4

5


2

5

4


8


7

8


8

4


4

3

10


9







Przyjmijmy scenariusz, w którym algorytm jest na następującym etapie: przeszukiwanie zakończyło się dla wierzchołka 0 jako startowego i znaleziono pewien cykl , który w tym momencie ma długość równą LB.
Obecnie niech będzie rozpatrywana ścieżka zawierająca wierzchołki 1-2-4. Uruchamiamy teraz procedurę generującą oszacowanie UB w celu podjęcia decyzji czy dalsze dodawanie wierzchołków do aktualnej ścieżki ma sens. Zgodnie z zasadą tworzenie naszego UB zauważamy, że do sumy tworzącej UB możemy wziąć wartości wag tych krawędzi , które nie są incydentne z aktualnie badaną ścieżką (nie licząc wierzchołków skrajnych). Wykluczamy zatem krawędzie (2,7) i (2,3). Dodatkowo wiemy, że algorytm zakończył działanie dla wierzchołka 0 jako startowego, a zatem wygenerował wszystkie możliwe ścieżki zawierające t


en wierzchołek. Prowadzi to do spostrzeżenia, że nie potrzebujemy także wszystkich krawędzi incydentnych z 0, bo wtedy analizowalibyśmy

jedną ze ścieżek już wcześniej zbadanych. Wykluczamy więc także krawędzie (1,0),(4,0),(10,0),(5,0),(8,0) .

Wartości wag reszty krawędzi, których

nie możemy w powyższy sposób wykluczyć zsumowane z wartościami wag krawędzi aktualnej ścieżki tworzą UB.


W tym momencie następuje dokonanie porównania LB z UB. Jeżeli LB < UB to kontynuujemy analizowanie ścieżki, a jeżeli LB > UB to dokonujemy nawrotu wiedząc, że dalsze poszukiwanie nie da lepszego rezultatu niż LB.

Za każdym razem gdy LB > UB wykonywane jest „odcięcie” dzięki któremu pozbywamy się wielu niepotrzebnych i nadmiarowych wywołań rekurencyjnych. O tym ile zyskujemy informować nas testy, które umieszczone są w dalszej części tego opracowania.


Złożoność:

Rozpatrując zagadnienie złożoności tego algorytmu zauważmy, że w najgorszym przypadku

może zajść sytuacja, w której nie dokonamy żadnego „odcięcia” ,a zatem efektywność metody będzie taka sama jak w algorytmie siłowym. Wiedząc natomiast , że badany problem jest NP-zupełny oraz przy założeniu, że P!=NP (czyli że nie istnieje algorytm rozwiązujący ten problem w czasie wielomianowym) wnioskujemy, że najlepszy przypadek działania algorytmu wykorzystującego strategię B&B i rozwiązującego ten problem będzie miał i tak złożoność wykładniczą. Rozważanie to prowadzi do wniosku, że jego złożoność będzie także


równa , a korzyści z wykorzystania strategii branch & bound będą ukryte pod postacią mniejszej stałej zawartej w notacji O.


  1. Algorytm heurystyczny.



Zaproponowany przez nas algorytm heurystyczny zgodnie ze strategią algorytmów zachłannych stosuje zamiast pełnego przeglądu pewne kryterium wyboru , na podstawie którego szuka najdłuższego cyklu. Polega ono na wybieraniu tych wierzchołków jako kolejnych składowych potencjalnego cyklu, do których prowadzi krawędź o największej wartości wagi.


/*wypunktuj poniższa listę żeby wszystkie opisy metod miały ten sam format, będzie ładniej i bardziej spójnie*/

  • Algorytm jest wywoływany dla każdego wierzchołka grafu po kolei. Wierzchołek ten

staje się pierwszym na liście wierzchołków znajdujących się w potencjalnym cyklu.

  • Następnie zgodnie z ideą naszej heurystyki przeglądamy wszystkie incydentne

wierzchołki z naszym wierzchołkiem startowym i wybieramy ten , do którego

prowadzi krawędź o największej wartości wagi.



  • Tak wybrany wierzchołek zostaje dodany do listy wierzchołków znajdujących się

w potencjalnym cyklu, aktualna wartość funkcji celu jest inkrementowana o wagę

krawędzi , którą wybraliśmy, a następnie cała procedura jest rekurencyjnie

powtarzana dla tego wierzchołka.


  • Algorytm „zagłębia” się rekurencyjnie wraz z wybieraniem kolejnych składowych

cyklu , aż do momentu gdy wybór kolejnego wierzchołka nie jest możliwy (brak

incydentnych wierzchołków , które nie wchodzą jeszcze w skład potencjalnego

cyklu).


  • Wówczas algorytm sprawdza czy może „zamknąć” cykl tj. sprawdza czy ostatni wierzchołek na liście jest incydentny z pierwszym. Jeśli to sprawdzenie zakończy się pomyślnie, to algorytm kończy swoje działanie zwracając szukany cykl, a jeśli nie,

wtedy dokonujemy nawrotu opuszczając najbardziej „zagłębioną” rekurencyjnie

procedurę i usuwamy ostatni wierzchołek z listy.



  • W tym momencie następuje zmiana priorytetu działania algorytmu, gdyż nie „zagłębiamy” się wybierając alternatywne wierzchołki lecz ponownie sprawdzamy czy można „zamknąć” cykl. Jeśli także tym razem się to nie uda, to ponownie wykonujemy nawrót itd.

Przykład działania:
Niech dany będzie graf , który w pliku wejściowym zapisany jest następująco:


8
5


1


5

0

1

4
0

0 1 4

0
6

7

8

9
2 7

0


2

3
4 9

0


4

2
5 5

1
2


2 6

1


6

3

5
6 8

2


7
3 2

3 6 2


4 7 5

5 7 3






Algorytm rozpoczyna przeszukiwanie od wierzchołka 0. Wybiera kolejno krawędzie

o wartościach wag: 9,5,3,5 po czym sprawdziwszy ,

że nie ma już innych incydentnych wierzchołków podejmuje udaną próbę „zamknięcia cyklu”.

Powstaje zatem cykl 0-4-7-5-0 o długości 22,

a algorytm kończy swoje działanie dla wierzchołka 0 i przechodzi do kolejnego czyli 1.





Zgodnie ze strategią algorytmu wybierane są kolejno krawędzie

o wartościach wag 8,2,7,9,5,3,5.

W tym momencie jednak algorytm musi dokonać nawrotu, ponieważ nie ma już niewykorzystanych incydentnych wierzchołków, a próba „zamknięcia” cyklu kończy się niepowodzeniem. Na tym etapie

w cyklu potencjalnym znajdują się kolejno wierzchołki: 1-6-3-2-0-4-7-5 , jednakże wykonany nawrót usunie z tej listy wierzchołek 5, a następnie także 7 oraz 4 gdyż dla nich próba „zamknięcia” cyklu także się nie uda.


D


opiero gdy algorytm powróci

do wierzchołka 0 cykl zostanie „zamknięty”, będzie on zawierał wierzchołki 1-6-3-2-0-1 ,

a jego długość będzie wynosić 23. Stanie się

on zatem nowym najdłuższym cyklem.

Analogicznie będzie wyglądał przebieg działania procedury dla kolejnych wierzchołków grafu. Zauważyć jednak należy , że możliwy jest scenariusz, w którym nawroty doprowadzą nas

do wierzchołka startowego. Wówczas procedura zwróci wartość długości cyklu równą zero,



dla danego wierzchołka początkowego.

Złożoność:

Analizując złożoność algorytmu zauważamy na początku, że jest on wywoływany dla każdego wierzchołka z kolei co daje nam już minimalnie n kroków , gdzie n oznacza liczbę wierzchołków. Każde wywołanie może pociągać za sobą kolejnych n wywołań rekurencyjnych w przypadku gdy w cyklu będą się znajdowały wszystkie wierzchołki grafu. Dodatkowo jeśli ostatnie wywołanie rekurencyjne zakończy się nawrotem który będzie kontynuowany aż do wierzchołka startowego to kroków będzie 2n (n „zagłębień” rekurencyjnych i n nawrotów). Ostatecznie zatem w najgorszym przypadku mamy n*2n kroków, a ponieważ czynnik 2 zostanie „ukryty” w notacji O, więc złożoność algorytmu heurystycznego wynosi .


©snauka.pl 2016
wyślij wiadomość