Performance Shortest path in GNU PROLOG-CodePudding

I have homework in PROLOG - I did software that knows how to calculate the shortest route and record all the nodes where it passed. But there is a serious performance problem if there are more than 5 nodes to the software it takes years to calculate (I have an 11th generation processor). I would be happy if you could advise how to modify the code so it would work faster divide the code into 2 so that calculating a route was one query and calculating all the points would be another query.

path(X, Y, N, Path) :- path(X, Y, N, [], Path).

path(X, Y, N, Seen, [X]) :-
    \  check_member(X, Seen),
    edge(X, Y, N).
path(X, Z, N, Seen, [X|T]) :-
    \  check_member(X, Seen),
    edge(X, Y, N0),
    path(Y, Z, N1, [X|Seen], T),
    \  check_member(X, T),
    N is N0   N1.
    
check_member(X, L) :- once(ismember(X, L)).
ismember(X, [X|_]).
ismember(X, [_|Xs]) :- ismember(X, Xs).

water_shortest_path(X, Y, MinCost, Path) :-
    path(X, Y, MinCost, Path), 
    \  (path(X, Y, LowerCost, OtherPath), 
        OtherPath \= Path, 
        LowerCost =< MinCost).
        
edge(l,l,0).
edge(r,r,0).
edge(l,p10,0).
edge(p10,j10,0).
edge(r,p335,1231).
edge(p335,j61,0).
edge(t3,j20,99).
edge(t1,j40,99).
edge(t2,j50,99).
edge(r,j60,1231).
edge(j10,j101,14200).
edge(j101,j103,1350).
edge(j101,j105,2540).
edge(j105,j107,1470).
edge(j103,j109,3940).
edge(j109,j111,2000).
edge(j111,j115,1160).
edge(j111,j113,1680).
edge(j113,j115,2000).
edge(j107,j115,1950).
edge(j113,j193,1660).
edge(j105,j263,2725).
edge(j115,j117,2180).
edge(j120,j119,730).
edge(j117,j120,1870).
edge(j120,j121,2050).
edge(j121,j119,2000).
edge(j121,j123,1500).
edge(j121,j125,930).
edge(j125,j127,3240).
edge(j127,j20,785).
edge(j127,j129,900).
edge(j129,j131,6480).
edge(j129,j139,2750).
edge(j139,j141,2050).
edge(j141,j143,1400).
edge(j15,j143,1650).
edge(j141,j145,3510).
edge(j145,j147,2200).
edge(j147,j149,880).
edge(j149,j151,1020).
edge(j151,j153,1170).
edge(j153,j125,4560).
edge(j151,j119,3460).
edge(j119,j157,2080).
edge(j157,j159,2910).
edge(j159,j161,2000).
edge(j161,j163,430).
edge(j163,j164,150).
edge(j164,j166,490).
edge(j265,j169,590).
edge(j169,j167,60).
edge(j187,j204,99.9).
edge(j169,j171,1270).
edge(j171,j173,50).
edge(j171,j271,760).
edge(j181,j35,30).
edge(j181,j177,30).
edge(j177,j179,30).
edge(j179,j183,210).
edge(j179,j40,1190).
edge(j185,j184,99.9).
edge(j185,j183,510).
edge(j184,j205,4530).
edge(j185,j204,1325).
edge(j189,j183,1350).
edge(j187,j189,500).
edge(j169,j269,646).
edge(j191,j187,2560).
edge(j267,j189,1230).
edge(j191,j193,520).
edge(j193,j195,360).
edge(j195,j161,2300).
edge(j197,j191,1150).
edge(j111,j197,2790).
edge(j173,j199,4000).
edge(j199,j201,630).
edge(j201,j203,120).
edge(j199,j273,725).
edge(j205,j207,1200).
edge(j207,j206,450).
edge(j207,j275,1430).
edge(j206,j208,510).
edge(j208,j209,885).
edge(j209,j211,1210).
edge(j211,j213,990).
edge(j213,j215,4285).
edge(j215,j217,1660).
edge(j217,j219,2050).
edge(j217,j225,1560).
edge(j213,j229,2200).
edge(j229,j231,1960).
edge(j211,j237,2080).
edge(j237,j229,790).
edge(j237,j239,510).
edge(j239,j241,35 ).
edge(j241,j243,2200).
edge(j241,j247,445).
edge(j239,j249,430).
edge(j247,j249,10).
edge(j247,j255,1390).
edge(j255,j50,925).
edge(j255,j253,1100).
edge(j255,j251,1100).
edge(j251,j249,1450).
edge(j257,j120,645).
edge(j259,j257,350).
edge(j259,j263,1400).
edge(j257,j261,1400).
edge(j161,j117,645).
edge(j261,j263,350).
edge(j267,j265,1580).
edge(j267,j163,1170).
edge(j189,j269,646).
edge(j181,j271,260).
edge(j273,j275,2230).
edge(j205,j273,645).
edge(j265,j163,1200).
edge(j201,j275,300).
edge(j269,j271,1290).
edge(j61,j123,45500).
edge(j60,j601,1).
edge(j601,j61,1).
edge(p10,l,0).
edge(j10,p10,0).
edge(p335,r,1231).
edge(j61,p335,0).
edge(j20,t3,99).
edge(j40,t1,99).
edge(j50,t2,99).
edge(j60,r,1231).
edge(j101,j10,14200).
edge(j103,j101,1350).
edge(j105,j101,2540).
edge(j107,j105,1470).
edge(j109,j103,3940).
edge(j111,j109,2000).
edge(j115,j111,1160).
edge(j113,j111,1680).
edge(j115,j113,2000).
edge(j115,j107,1950).
edge(j193,j113,1660).
edge(j263,j105,2725).
edge(j117,j115,2180).
edge(j119,j120,730).
edge(j120,j117,1870).
edge(j121,j120,2050).
edge(j119,j121,2000).
edge(j123,j121,1500).
edge(j125,j121,930).
edge(j127,j125,3240).
edge(j20,j127,785).
edge(j129,j127,900).
edge(j131,j129,6480).
edge(j139,j129,2750).
edge(j141,j139,2050).
edge(j143,j141,1400).
edge(j143,j15,1650).
edge(j145,j141,3510).
edge(j147,j145,2200).
edge(j149,j147,880).
edge(j151,j149,1020).
edge(j153,j151,1170).
edge(j125,j153,4560).
edge(j119,j151,3460).
edge(j157,j119,2080).
edge(j159,j157,2910).
edge(j161,j159,2000).
edge(j163,j161,430).
edge(j164,j163,150).
edge(j166,j164,490).
edge(j169,j265,590).
edge(j167,j169,60).
edge(j204,j187,99.9).
edge(j171,j169,1270).
edge(j173,j171,50).
edge(j271,j171,760).
edge(j35,j181,30).
edge(j177,j181,30).
edge(j179,j177,30).
edge(j183,j179,210).
edge(j40,j179,1190).
edge(j184,j185,99.9).
edge(j183,j185,510).
edge(j205,j184,4530).
edge(j204,j185,1325).
edge(j183,j189,1350).
edge(j189,j187,500).
edge(j269,j169,646).
edge(j187,j191,2560).
edge(j189,j267,1230).
edge(j193,j191,520).
edge(j195,j193,360).
edge(j161,j195,2300).
edge(j191,j197,1150).
edge(j197,j111,2790).
edge(j199,j173,4000).
edge(j201,j199,630).
edge(j203,j201,120).
edge(j273,j199,725).
edge(j207,j205,1200).
edge(j206,j207,450).
edge(j275,j207,1430).
edge(j208,j206,510).
edge(j209,j208,885).
edge(j211,j209,1210).
edge(j213,j211,990).
edge(j215,j213,4285).
edge(j217,j215,1660).
edge(j219,j217,2050).
edge(j225,j217,1560).
edge(j229,j213,2200).
edge(j231,j229,1960).
edge(j237,j211,2080).
edge(j229,j237,790).
edge(j239,j237,510).
edge(j241,j239,35 ).
edge(j243,j241,2200).
edge(j247,j241,445).
edge(j249,j239,430).
edge(j249,j247,10).
edge(j255,j247,1390).
edge(j50,j255,925).
edge(j253,j255,1100).
edge(j251,j255,1100).
edge(j249,j251,1450).
edge(j120,j257,645).
edge(j257,j259,350).
edge(j263,j259,1400).
edge(j261,j257,1400).
edge(j117,j161,645).
edge(j263,j261,350).
edge(j265,j267,1580).
edge(j163,j267,1170).
edge(j269,j189,646).
edge(j271,j181,260).
edge(j275,j273,2230).
edge(j273,j205,645).
edge(j163,j265,1200).
edge(j275,j201,300).
edge(j271,j269,1290).
edge(j123,j61,45500).
edge(j601,j60,1).
edge(j61,j601,1).

CodePudding user response：

It's the best so far:

findPath(_Limit, [Goal | Rest], Goal, Temp, Temp, [Goal | Rest]) :- !.

findPath(Limit, [A | Rest], Goal, Cost, Temp, Path) :-
    edge(A,B,C),
    \ member(B, Rest),
    NewCosts is (Temp   C),
    NewCosts < Limit,
    findPath(Limit, [B, A | Rest], Goal, Cost, NewCosts, Path).

%test ?- searchPath(l, j101, Path, Length).

searchPath(Start, Goal, Path_to_goal, L) :-
    S = path_len([], 200000),
    arg(2, S, Limit),
    (   findPath(Limit, [Start], Goal, Cost, 0, Path)
    ->  (   Cost < Limit
        ->  setarg(1, S, Path),
        setarg(2, S, Cost),
        true
        )
    ;   fail
    ),
    arg(1, S, Rev),
    reverse(Rev, Path_to_goal),
    arg(2, S, L).

CodePudding user response：

Taking advantage of backtracking:

% path_best(l, r, Cost, Path).
path_best(Start, End, Cost, Path) :-
    assert_new_best_path(Start, End, notfound, _),
    path_best_(Start, End, Cost, Path).

path_best_(Start, End, Cost, Path) :-
    % Find a good path
    path_edge_to_edge_good(Start, End, Cost, Path),
    % Record it
    assert_new_best_path(Start, End, Cost, Path),
    % Keep searching via backtracking for an even better path
    fail.

% Finally, return path with best cost
path_best_(Start, End, Cost, Path) :-
    path_best_upto(Cost, [Start, End, Path]).


% "Good" because it backtracks if going over the current-best cost
path_edge_to_edge_good(Start, End, Cost, Path) :-
    path_edge_to_edge_(Start, End, 0, Cost, [Start], Seen),
    reverse(Seen, Path).

path_edge_to_edge_(End, End, Cost, Cost, Seen, Seen).
path_edge_to_edge_(PathStart, PathEnd, CostUpto, Cost, SeenUpto, Seen) :-
    edge(PathStart, EdgeEnd, EdgeCost),
    % Prevent infinite loops
    \  member(EdgeEnd, SeenUpto),
    CostUpto1 is CostUpto   EdgeCost,
    % Fail quickly if this is worse than the already-known best-so-far path cost
    cost_under_best(CostUpto1),
    path_edge_to_edge_(EdgeEnd, PathEnd, CostUpto1, Cost, [EdgeEnd|SeenUpto], Seen).


cost_under_best(CostUpto1) :-
    path_best_upto(BestCost, _),
    (BestCost = notfound -> true ; CostUpto1 < BestCost).


:- dynamic path_best_upto/2.

assert_new_best_path(Start, End, Cost, Path) :-
    retractall(path_best_upto(_, _)),
    asserta(path_best_upto(Cost, [Start, End, Path])).

Result after 12 seconds (in swi-prolog, but should be identical in gprolog):

?- path_best(l, r, Cost, Path).
Cost = 72141,
Path = [l,p10,j10,j101,j105,j263,j259,j257,j120,j121,j123,j61,p335,r].

It would however be more efficient to always select alternatives based on their lower cost, and then stop at the first path found, which by definition will be the lowest cost (or joint lowest with other paths).