[SOLVED] Performance Shortest path in GNU PROLOG

Issue

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

Solution

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

Answered By – brebs

Answer Checked By – Pedro (BugsFixing Volunteer)

Leave a Reply

Your email address will not be published. Required fields are marked *