Prolog - algorytm Dijkstry

0

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ę:)

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.

  1. 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.

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 ;].

0

Dzięki, o takie wyjaśnienie mi chodziło:)

1 użytkowników online, w tym zalogowanych: 0, gości: 1