meilleure structure Graphique pour implémenter Dijkstra dans prolog

Question

La question est simple. Comment structurer mon graphe dans un prologue SWI pour implémenter l'algorithme de Dijkstra?

J'ai trouvé this mais c'est trop lent pour mon travail.

Answer 1

Cette mise en œuvre est pas si mal:

?- time(dijkstra(penzance, Ss)). 
% 3,778 inferences, 0,003 CPU in 0,003 seconds (99% CPU, 1102647 Lips) 
Ss = [s(aberdeen, 682, [penzance, exeter, bristol, birmingham, manchester, carlisle, edinburgh|...]), s(aberystwyth, 352, [penzance, exeter, bristol, swansea, aberystwyth]), s(birmingham, 274, [penzance, exeter, bristol, birmingham]), s(brighton, 287, [penzance, exeter, portsmouth, brighton]), s(bristol, 188, [penzance, exeter, bristol]), s(cambridge, 339, [penzance, exeter|...]), s(cardiff, 322, [penzance|...]), s(carlisle, 474, [...|...]), s(..., ..., ...)|...]. 

offres SWI-Prolog attribué des variables, alors this answer pourrait être pertinent pour vous. J'espère que je posterai plus tard aujourd'hui une implémentation de dijkstra/2 en utilisant des variables d'attribut.

éditer bien, je dois dire que la première programmation avec variables d'attribut n'est pas trop facile.

J'utilise la suggestion de la réponse par @Mat j'ai lié ci-dessus, en abusant des variables d'attribut pour obtenir l'accès à temps constant aux propriétés attachées aux données comme requis de l'algorithme. Je suis (aveuglément) mis à exécution les wikipedia algorithm, voici mon effort:

/* File: dijkstra_av.pl 
    Author: Carlo,,, 
    Created: Aug 3 2012 
    Purpose: learn graph programming with attribute variables 
*/ 

:- module(dijkstra_av, [dijkstra_av/3]). 

dijkstra_av(Graph, Start, Solution) :- 
    setof(X, Y^D^(member(d(X,Y,D), Graph) 
      ;member(d(Y,X,D), Graph)), Xs), 
    length(Xs, L), 
    length(Vs, L), 
    aggregate_all(sum(D), member(d(_, _, D), Graph), Infinity), 
    catch((algo(Graph, Infinity, Xs, Vs, Start, Solution), 
      throw(sol(Solution)) 
     ), sol(Solution), true). 

algo(Graph, Infinity, Xs, Vs, Start, Solution) :- 
    pairs_keys_values(Ps, Xs, Vs), 
    maplist(init_adjs(Ps), Graph), 
    maplist(init_dist(Infinity), Ps), 
    ord_memberchk(Start-Sv, Ps), 
    put_attr(Sv, dist, 0), 
    time(main_loop(Vs)), 
    maplist(solution(Start), Vs, Solution). 

solution(Start, V, s(N, D, [Start|P])) :- 
    get_attr(V, name, N), 
    get_attr(V, dist, D), 
    rpath(V, [], P). 

rpath(V, X, P) :- 
    get_attr(V, name, N), 
    ( get_attr(V, previous, Q) 
    -> rpath(Q, [N|X], P) 
    ; P = X 
    ). 

init_dist(Infinity, N-V) :- 
    put_attr(V, name, N), 
    put_attr(V, dist, Infinity). 

init_adjs(Ps, d(X, Y, D)) :- 
    ord_memberchk(X-Xv, Ps), 
    ord_memberchk(Y-Yv, Ps), 
    adj_add(Xv, Yv, D), 
    adj_add(Yv, Xv, D). 

adj_add(X, Y, D) :- 
    ( get_attr(X, adjs, L) 
    -> put_attr(X, adjs, [Y-D|L]) 
    ; put_attr(X, adjs, [Y-D]) 
    ). 

main_loop([]). 
main_loop([Q|Qs]) :- 
    smallest_distance(Qs, Q, U, Qn), 
    put_attr(U, assigned, true), 
    get_attr(U, adjs, As), 
    update_neighbours(As, U), 
    main_loop(Qn). 

smallest_distance([A|Qs], C, M, [T|Qn]) :- 
    get_attr(A, dist, Av), 
    get_attr(C, dist, Cv), 
    ( Av < Cv 
    -> (N,T) = (A,C) 
    ; (N,T) = (C,A) 
    ), 
    !, smallest_distance(Qs, N, M, Qn). 
smallest_distance([], U, U, []). 

update_neighbours([V-Duv|Vs], U) :- 
    ( get_attr(V, assigned, true) 
    -> true 
    ; get_attr(U, dist, Du), 
     get_attr(V, dist, Dv), 
     Alt is Du + Duv, 
     ( Alt < Dv 
     -> put_attr(V, dist, Alt), 
     put_attr(V, previous, U) 
     ; true 
     ) 
    ), 
    update_neighbours(Vs, U). 
update_neighbours([], _). 

:- begin_tests(dijkstra_av). 

test(1) :- 
    nl, 
    time(dijkstra_av([d(a,b,1),d(b,c,1),d(c,d,1),d(a,d,2)], a, L)), 
    maplist(writeln, L). 

test(2) :- 
    open('salesman.pl', read, F), 
    readf(F, L), 
    close(F), 
    nl, 
    dijkstra_av(L, penzance, R), 
    maplist(writeln, R). 

readf(F, [d(X,Y,D)|R]) :- 
    read(F, dist(X,Y,D)), !, readf(F, R). 
readf(_, []). 

:- end_tests(dijkstra_av). 

Pour être vrai, je préfère le code lié à la question. Il y a un point évident à optimiser, smallest_distance/4 utilise maintenant un balayage linéaire muet, en utilisant un rbtree le runtime devrait être meilleur. Mais les variables attribuées doivent être manipulées avec soin.

temps/1 montrent apparemment une amélioration

% 2,278 inferences, 0,003 CPU in 0,003 seconds (97% CPU, 747050 Lips) 
s(aberdeen,682,[penzance,exeter,bristol,birmingham,manchester,carlisle,edinburgh,aberdeen]) 
.... 

mais le graphique est trop petit pour toute affirmation définitive. Laissez-nous savoir si cet extrait réduit le temps requis pour votre programme.

Le fichier salesman.pl contient dist/3 faits, il est pris textuellement du lien dans la question.