在序言中实现Dijkstra的最佳结构图 [英] best structure Graph to implement Dijkstra in prolog
问题描述
问题很简单。
如何在SWI序言中构造图以实现Dijkstra的算法?
The question is simple. How can I struct my Graph in SWI prolog to implement the Dijkstra's algorithm?
我发现这,但是对于我的工作来说太慢了。
I have found this but it's too slow for my job.
推荐答案
该实现还不错:
?- 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提供属性变量,然后此答案可能与您有关。
我希望我今天晚些时候发布使用属性变量的dijkstra / 2实现。
SWI-Prolog offers attributed variables, then this answer could be relevant to you. I hope I will post later today an implementation of dijkstra/2 using attribute variables.
edit 好,我必须说第一次使用属性变量编程并不是一件容易的事。
edit well, I must say that first time programming with attribute variables is not too much easy.
我正在使用上面链接的@Mat的答案中的建议,滥用属性变量以获得<根据算法的要求,em>恒定时间访问附加到数据的属性。我(盲目地)实现了 Wikipedia算法,这是我的努力:
I'm using the suggestion from the answer by @Mat I linked above, abusing of attribute variables to get constant time access to properties attached to data as required of algorithm. I've (blindly) implemented the wikipedia algorithm, here my 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).
说实话,我更喜欢您在问题中链接的代码。有一个明显的要优化点,minimum_distance / 4现在使用哑线性扫描,使用rbtree运行时应该更好。但是属性变量必须谨慎处理。
To be true, I prefer the code you linked in the question. There is an obvious point to optimize, smallest_distance/4 now use a dumb linear scan, using an rbtree the runtime should be better. But attributed variables must be handled with care.
时间/ 1显然表现出了改善
time/1 apparently show an improvement
% 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])
....
但是该图对于任何确定的断言来说都太小了。让我们知道此代码段是否减少了您的程序所需的时间。
but the graph is too small for any definitive assertion. Let we know if this snippet reduce the time required for your program.
文件 salesman.pl 包含dist / 3个事实,它是逐字记录的问题中的链接。
File salesman.pl contains dist/3 facts, it's taken verbatim from the link in the question.
这篇关于在序言中实现Dijkstra的最佳结构图的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!