prolog - mas - mejor estructura Gráfico para implementar Dijkstra en prólogo

camino mas corto grafos java

Question

La pregunta es simple. ¿Cómo puedo estructurar mi Gráfico en SWI prolog para implementar el algoritmo de Dijkstra?

He encontrado esto, pero es demasiado lento para mi trabajo.

Answer 1

Esa implementación no es tan mala:

?- 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(..., ..., ...)|...].

SWI-Prolog ofrece variables atribuidas, entonces esta respuesta podría ser relevante para usted. Espero publicar más tarde hoy una implementación de dijkstra / 2 usando variables de atributos.

edite bien, debo decir que la programación por primera vez con variables de atributo no es demasiado fácil.

Estoy usando la sugerencia de la respuesta de @Mat I vinculada anteriormente, abusando de las variables de los atributos para obtener acceso constante al tiempo a las propiedades adjuntas a los datos según lo requerido por el algoritmo. Implementé (ciegamente) el algoritmo de wikipedia , aquí mi esfuerzo:

/* 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).

Para ser verdad, prefiero el código que has vinculado en la pregunta. Hay un punto obvio para optimizar, smallest_distance / 4 ahora usa un escaneo lineal tonto, usando un rbtree el tiempo de ejecución debería ser mejor. Pero las variables atribuidas deben manejarse con cuidado.

time / 1 aparentemente muestra una mejora

% 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])
....

pero el gráfico es demasiado pequeño para cualquier afirmación definitiva. Permítanos saber si este fragmento reduce el tiempo requerido para su programa.

El archivo salesman.pl contiene dist / 3 hechos, se toma textualmente del enlace en la pregunta.