Witam,
Mam na zajęcia z programowania przeanalizować algorytm Dijkstry w Prologu: http://colin.barker.pagesperso-orange.fr/lpa/dijkstra.htm . Wiem, na czym polega ten algorytm, ale nie mogę zrozumieć do końca tego działania w języku Prolog;/ Mógłby mi ktoś pomóc?
Edit. Gdyby ktoś mi rozpisał działanie pierwszego poziomu rekurencji w dijkstra_1 to by załatwiło sprawę:)
- Rejestracja:prawie 11 lat
- Ostatnio:prawie 11 lat
- Postów:2
0
edytowany 1x, ostatnio: Angela90
- Rejestracja:prawie 16 lat
- Ostatnio:4 miesiące
1
Hm, zakładam że rozumiesz http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm (jeśli nie to najpierw przeczytaj na wiki albo inne wprowadzenie).
A skoro to rozumiesz, to wiesz już wszystko :P.
dijkstra(Vertex0, SS) jest prawdziwe jeśli (cytując) SS jest listą struktur postaci s(Vertex, Dist, Path) gdzie Dist to odległość Vertex0 - Vertex a Path to ścieżka.
Przykład może (obcięte przez prolog bo długie):
1 ?-
| dijkstra(hull, SS).
SS = [s(aberdeen, 336, [hull, york, newcastle, edinburgh, aberdeen]), s(aberystwyth, 219, [hull, sheffield, aberystwyth]), s(birmingham, 138, [hull, nottingham, birmingham]), s(brighton, 278, [hull, nottingham, cambridge, london|...]), s(bristol, 224, [hull, nottingham, birmingham|...]), s(cambridge, 172, [hull, nottingham|...]), s(cardiff, 238, [hull|...]), s(carlisle, 149, [...|...]), s(..., ..., ...)|...].
create(Start, Path, Edge) tworzy taką samą strukturę, ale tylko dla wierzchołków osiągalnych z jednego danego wierzchołka Start i z ustaloną ścieżką (formalnie: start/3 jest prawdziwe (...)).
Przykład:
5 ?- create(hull, some_path, Edges).
Edges = [s(leeds, 58, some_path), s(nottingham, 90, some_path), s(sheffield, 65, some_path), s(york, 37, some_path)].
Kod create:
create(Start, Path, Edges):-
setof(s(Vertex,Edge,Path), e(Start,Vertex,Edge), Edges), !.
create(_, _, []).
Tu nawet chcąc nie ma czego tłumaczyć, wszystko to http://www.swi-prolog.org/pldoc/man?predicate=setof/3
Best(Edges, Edge0, Edge) z kolei działa tak że znajduje najkrótszą krawędź spośród {Edges, Edge0} (nie wiem dlaczego jest to przekazywane w dwóch parametrach, można równie dobrze w jednym), dowód:
7 ?- create(hull, some_path, [Edg|Edges]), best(Edges, Edg, Best).
Edg = s(leeds, 58, some_path),
Edges = [s(nottingham, 90, some_path), s(sheffield, 65, some_path), s(york, 37, some_path)],
Best = s(york, 37, some_path).
Kod:
best([], Best, Best).
best([Edge|Edges], Best0, Best):-
shorter(Edge, Best0), !,
best(Edges, Edge, Best).
best([_|Edges], Best0, Best):-
best(Edges, Best0, Best).
Standardowe rekurencyjne podejście, tylko w prologu. Jeśli Edge jest lepsze od obecnego najlepszego (Best0), odcinamy i bierzemy Edge dalej, inaczej nie zmieniamy nic.
(Takich półfunkcji jak shorter czy lt nawet nie będę wspominał)
delete(A, B, C) z kolei 'usuwa' (jest prawdziwe jeśli (...)) z A wszystkie elementy z B, znowu skopiowane z SWI-prologowego REPL-a:
9 ?- create(hull, some_path, [Edg|Edges]), best(Edges, Edg, Best), delete([Edg|Edges], [Best], AfterDelete).
Edg = s(leeds, 58, some_path),
Edges = [s(nottingham, 90, some_path), s(sheffield, 65, some_path), s(york, 37, some_path)],
Best = s(york, 37, some_path),
AfterDelete = [s(leeds, 58, some_path), s(nottingham, 90, some_path), s(sheffield, 65, some_path)].
(długie sie te wycinki robią).
delete([], _, []). %1
delete([X|Xs], [], [X|Xs]):-!. %2
delete([X|Xs], [Y|Ys], Ds):- %3
eq(X, Y), !,
delete(Xs, Ys, Ds).
delete([X|Xs], [Y|Ys], [X|Ds]):- %4
lt(X, Y), !, delete(Xs, [Y|Ys], Ds).
delete([X|Xs], [_|Ys], Ds):- %5
delete([X|Xs], Ys, Ds).
Hm, to już dłuższe.
- i 2) to przypadki brzegowe kończące rekurencje po prostu
-
- jeśli pierwszy element obu list jest równy, idziemy dalej pomijając je (element X pomijamy bo w ten sposób 'usuwamy' go z wejścia, a Y dlatego że krawędzie się nie powtarzają więc drugi raz taka sytuacja dla tego elementu nie zajdzie)
-
- pierwszy element pierwszej listy < pierwszy element drugiej listy. Listy są posortowane, więc pierwszy element pierwszej listy dołączamy do wyniki
-
- nic z tego nie zachodzi, więc żaden element już nie pasuje do pierwszego elementu drugiej listy. Pomijamy więc pierwszy elem drugiej listy i idziemy dalej.
Dzięki takiemu zapisowi ma to złożoność O(n+m) gdzie n i m to długości odpowiednio pierwszej i drugiej listy.
- nic z tego nie zachodzi, więc żaden element już nie pasuje do pierwszego elementu drugiej listy. Pomijamy więc pierwszy elem drugiej listy i idziemy dalej.
No i mamy jeszcze merge(X, Y, Z).
Merge dostaje ('jest prawdziwe jeśli (...)') dwie listy ścieżek: X i Y, i 'skleja' je w jedną Z. Przy czym jeśli jeden wierzchołek się powtarza dwa razy, do Z trafia ta wersja gdzie jest krótsza ścieżka.
Nie chce mi się już opisywać kodu, pomysł jest bardzo podobny do best delete wszystkich funkcji typowo rekurencyjnych w prologu ;).
Ok, dlaczego to wszystko opisywałem - bo teraz możemy dojść do dijkstra_1 o który pytałeś
dijkstra_1(Possible, Paths, Result) działa tak:
dijkstra_1([], Ss, Ss). % nie ma już żadnych krawędzi do rozważenia
dijkstra_1([D|Ds], Ss0, Ss):-
best(Ds, D, S), % S = najkrótsza ścieżka z [D|DS]
delete([D|Ds], [S], Ds1), % Ds1 = [D|DS] po usunięciu S
S=s(Vertex,Distance,Path), % nazywamy części S -> S to ścieżka do Vertex o długości Distance po Path
reverse([Vertex|Path], Path1),
merge(Ss0, [s(Vertex,Distance,Path1)], Ss1), % dodajemy S do wyniku (mergujemy z Ss0, obecnym stanem)
create(Vertex, [Vertex|Path], Ds2), % teraz patrzymy gdzie się można dostać z Vertex
delete(Ds2, Ss1, Ds3), % pomijamy ściezki do wszystkich wierzchołków które już mamy (czyli Ss1)
incr(Ds3, Distance, Ds4), % Dodajemy Distance do wszystkich ścieżek osiągalnych z Vertex (dodajemy długość ścieżki początek-vertex do poszczególnych ścieżek vertex-osiągalne_coś)
merge(Ds1, Ds4, Ds5), % Już prawie koniec - dodajemy ścieżki osiągalne z Vertex do wyniku...
dijkstra_1(Ds5, Ss1, Ss). % I rozważamy następną ścieżkę!
Hmm, trochę długie te 'wyjaśnienia' wyszły (większość to kod więc nie aż tak źle). Mam nadzieję że pomogą coś w każdym razie ;].
edytowany 1x, ostatnio: msm
Shalom