最佳結構圖在序言中實現Dijkstra

Question

問題很簡單。 如何在SWI prolog中構建我的圖來實現Dijkstra算法？

我發現this但它對我的工作來說太慢了。

Answer 1

該實現並不是那麼糟糕：

?- 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的報價歸因變量，那麼this answer可能是與你有關的。 我希望我今天晚些時候會發佈一個使用屬性變量的dijkstra/2的實現。

編輯好吧，我必須說，第一次用屬性變量編程並不太容易。

我正在使用來自@Mat的回答中的建議，我上面鏈接了，濫用屬性變量以獲得恆定時間訪問到算法所需的附加到數據的屬性。我（盲目）實施wikipedia algorithm，在這裏我的努力：

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

是真實的，我更喜歡你在問題中鏈接的代碼。有一個明顯的優化點，smallest_distance/4現在使用啞線性掃描，使用rbtree，運行時應該更好。但歸因變量必須小心處理。

次/ 1明顯顯示出改善

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

但圖太小，任何明確的說法。讓我們知道這段代碼是否會縮短程序所需的時間。

文件salesman.pl包含dist/3事實，它是逐字從問題中的鏈接。