This code requires the Simulated Annealing package.
% Finds a route through all of the 25 towns in the table below.
% The optimal path has a length equal to 1989.
alltowns:-
Towns=[aberdeen, aberystwyth, brighton, birmingham, bristol, cambridge,
cardiff, carlisle, dover, edinburgh, exeter, glasgow, hull, leeds,
liverpool, manchester, newcastle, nottingham, oxford, penzance,
portsmouth, sheffield, swansea, york, london],
towns(Towns).
% e.g. towns([leeds,dover,aberystwyth,london,cardiff,hull]).
towns(Towns):-
retractall(town(_, _)),
retractall(e(_, _, _)),
towns_integers(Towns, 1),
forall((member(Town1, Towns), member(Town2, Towns), d(Town1, Town2, D)),
(town(Town1, I), town(Town2, J), assert(e(I, J, D)))),
length(Towns, NumberOfTowns),
retractall(size(_)),
asserta(size(NumberOfTowns)),
anneal.
% e.g. towns_integers([leeds,bristol,york,london,hull], 1).
towns_integers([], _).
towns_integers([Town|Towns], I):-
assert(town(Town, I)),
I1 is I + 1,
towns_integers(Towns, I1).
% Towns are not ordered in e/3
dist(X, Y, D):-e(X, Y, D), !.
dist(X, Y, D):-e(Y, X, D), !.
% Called from anneal.pl
perturb(Xs, As):-
rand_int(0, 3, R),
/* Do a "reverse" three times more often than a "move" */
R = 0, !,
/* MOVE: */
/* The list As is the same as the list Xs except that two pseudo- */
/* randomly chosen adjacent sublists are swapped. */
/* N.B. L+M=Size rotates the whole list, which, for TSP, is redundant. */
/* Choose random X in 1..Size-1, random K in 0..X-1 and random Y in */
/* X+1..Size. Then L=X-K and M=Y-X. */
/* L is the length of the first sublist and K is its offset */
/* (base-0) from the start of the list. M is the length of the */
/* second sublist, and it immediately follows the first sublist. */
size(Size),
Size1 is Size - 1,
rand_int(1, Size1, X),
X1 is X - 1,
rand_int(0, X1, K),
X2 is X + 1,
rand_int(X2, Size, Y),
L is X - K,
M is Y - X,
split([K,L,M], Xs,[], [As,Cs, Bs,Ds, Cs,Bs, Ds,[]]).
perturb(Xs, As):-
/* REVERSE: */
/* The list As is the same as the list Xs except that a pseudo-randomly */
/* chosen sublist is reversed. */
/* N.B. Avoid L=0 and L=1, which would reverse nothing. */
/* K=0, L=Size reverses the whole list, which, for TSP, is */
/* redundant. */
/* Choose random K,X in 0..Size such that K < X-1. Then L=X-K. */
/* L is the length of the sublist to reverse and K is its offset */
/* (base-0) from the start of the list. */
size(Size),
repeat,
rand_int(0, Size, K),
rand_int(0, Size, X),
K < X - 1, !,
L is X - K,
split([K,L], Xs,[], [As,Bs, Es,_, Cs,[]]),
rev(L, Es, Bs,Cs).
/* rand_int(I, J, K) is true if K is a pseudo-random integer in the range */
/* I..J. */
rand_int(I, J, K):-K is int(rand(J - I + 1)) + I.
/* rev(N, Xs, Ys,Zs) is true if the difference list Ys,Zs is the result of */
/* reversing the first N elements of the list Xs. */
/* e.g. rev(3, [1,2,3,4,5], [3,2,1,5,6], [5,6]). */
rev(0, _, Ys,Ys):-!.
rev(N, [X|Xs], YsZs,Zs):-
N1 is N - 1,
rev(N1, Xs, YsZs,[X|Zs]).
/* split(Ns, Xs,Ys, Zss) splits the difference list Xs,Ys into a list of */
/* difference lists Zss according to the lengths given in Ns. */
/* e.g. split([2,2,1], [1,2,3,4,5,6,7],[], [[1,2,3,4,5,6,7],[3,4,5,6,7], */
/* [3,4,5,6,7],[5,6,7], */
/* [5,6,7],[6,7], */
/* [6,7],[]]). */
split([], Xs,As, [Xs,As]).
split([N|Ns], Xs,As, [Ys,Bs|Yss]):-
split_1(N, Xs,As, Ys,Bs, Zs,Cs),
split(Ns, Zs,Cs, Yss).
% e.g. split_1(2, [1,2,3,4,5],[], [1,2,3,4,5],[3,4,5], [3,4,5],[]).
split_1(0, Xs,As, Ys,Ys, Xs,As):-!.
split_1(N, [X|Xs],As, [X|Ys],Bs, Zs,Cs):-
N1 is N - 1,
split_1(N1, Xs,As, Ys,Bs, Zs,Cs).
% Called from anneal.pl
energy(List, Energy):-distance(List, Energy).
/* distance(Towns, Length) is true if Length is the length, as defined by */
/* dist/3, of the route going through all the Towns (including returning */
/* to the first town from the last town). */
distance([Start|Towns], Length):-
distance_1(Towns, Start, Start, 0, Length).
distance_1([], End, Start, Length0, Length):-
dist(End, Start, Length1),
Length is Length0 + Length1.
distance_1([Town|Towns], Town0, Start, Length0, Length):-
dist(Town0, Town, Length1),
Length2 is Length0 + Length1,
distance_1(Towns, Town, Start, Length2, Length).
% Called from anneal.pl
output(_, Xs, Energy):-
integers_towns(Xs, Path),
write(`Path: `), write(Path), nl,
write(`Length: `), write(Energy), nl.
% e.g. integers_towns([3,1,5,2,4], Towns).
integers_towns([], []).
integers_towns([I|Is], [Town|Towns]):-
town(Town, I), !,
integers_towns(Is, Towns).
/* length(Xs, L) is true if L is the number of elements in the list Xs. */
% length(Xs, L):-length_1(Xs, 0, L).
/* length_1(Xs, L0, L) is true if L is equal to L0 plus the number of */
/* elements in the list Xs. */
% length_1([], L, L).
% length_1([_|Xs], L0, L):-L1 is L0 + 1, length_1(Xs, L1, L).
% This is the data from LPA Win-Prolog Examples\Salesman.pl
d( aberdeen, aberystwyth, 427 ).
d( aberdeen, birmingham, 403 ).
d( aberdeen, brighton, 547 ).
d( aberdeen, bristol, 480 ).
d( aberdeen, cambridge, 443 ).
d( aberdeen, cardiff, 484 ).
d( aberdeen, carlisle, 206 ).
d( aberdeen, dover, 573 ).
d( aberdeen, edinburgh, 115 ).
d( aberdeen, exeter, 555 ).
d( aberdeen, glasgow, 142 ).
d( aberdeen, hull, 336 ).
d( aberdeen, leeds, 306 ).
d( aberdeen, liverpool, 327 ).
d( aberdeen, manchester, 326 ).
d( aberdeen, newcastle, 221 ).
d( aberdeen, nottingham, 370 ).
d( aberdeen, oxford, 464 ).
d( aberdeen, penzance, 663 ).
d( aberdeen, portsmouth, 550 ).
d( aberdeen, sheffield, 338 ).
d( aberdeen, swansea, 502 ).
d( aberdeen, york, 299 ).
d( aberdeen, london, 488 ).
d( aberystwyth, birmingham, 114 ).
d( aberystwyth, brighton, 249 ).
d( aberystwyth, bristol, 121 ).
d( aberystwyth, cambridge, 211 ).
d( aberystwyth, cardiff, 108 ).
d( aberystwyth, carlisle, 219 ).
d( aberystwyth, dover, 284 ).
d( aberystwyth, edinburgh, 312 ).
d( aberystwyth, exeter, 196 ).
d( aberystwyth, glasgow, 313 ).
d( aberystwyth, hull, 216 ).
d( aberystwyth, leeds, 166 ).
d( aberystwyth, liverpool, 100 ).
d( aberystwyth, manchester, 126 ).
d( aberystwyth, newcastle, 254 ).
d( aberystwyth, nottingham, 154 ).
d( aberystwyth, oxford, 156 ).
d( aberystwyth, penzance, 304 ).
d( aberystwyth, portsmouth, 218 ).
d( aberystwyth, sheffield, 154 ).
d( aberystwyth, swansea, 75 ).
d( aberystwyth, york, 190 ).
d( aberystwyth, london, 212 ).
d( birmingham, brighton, 159 ).
d( birmingham, bristol, 86 ).
d( birmingham, cambridge, 97 ).
d( birmingham, cardiff, 100 ).
d( birmingham, carlisle, 198 ).
d( birmingham, dover, 181 ).
d( birmingham, edinburgh, 291 ).
d( birmingham, exeter, 162 ).
d( birmingham, glasgow, 292 ).
d( birmingham, hull, 122 ).
d( birmingham, leeds, 109 ).
d( birmingham, liverpool, 99 ).
d( birmingham, manchester, 80 ).
d( birmingham, newcastle, 198 ).
d( birmingham, nottingham, 48 ).
d( birmingham, oxford, 63 ).
d( birmingham, penzance, 271 ).
d( birmingham, portsmouth, 141 ).
d( birmingham, sheffield, 75 ).
d( birmingham, swansea, 125 ).
d( birmingham, york, 125 ).
d( birmingham, london, 110 ).
d( brighton, bristol, 136 ).
d( brighton, cambridge, 106 ).
d( brighton, cardiff, 183 ).
d( brighton, carlisle, 354 ).
d( brighton, dover, 81 ).
d( brighton, edinburgh, 432 ).
d( brighton, exeter, 165 ).
d( brighton, glasgow, 448 ).
d( brighton, hull, 224 ).
d( brighton, leeds, 250 ).
d( brighton, liverpool, 250 ).
d( brighton, manchester, 240 ).
d( brighton, newcastle, 328 ).
d( brighton, nottingham, 178 ).
d( brighton, oxford, 96 ).
d( brighton, penzance, 277 ).
d( brighton, portsmouth, 49 ).
d( brighton, sheffield, 216 ).
d( brighton, swansea, 236 ).
d( brighton, york, 250 ).
d( brighton, london, 52 ).
d( bristol, cambridge, 151 ).
d( bristol, cardiff, 44 ).
d( bristol, carlisle, 276 ).
d( bristol, dover, 187 ).
d( bristol, edinburgh, 369 ).
d( bristol, exeter, 76 ).
d( bristol, glasgow, 370 ).
d( bristol, hull, 206 ).
d( bristol, leeds, 195 ).
d( bristol, liverpool, 163 ).
d( bristol, manchester, 161 ).
d( bristol, newcastle, 284 ).
d( bristol, nottingham, 141 ).
d( bristol, oxford, 71 ).
d( bristol, penzance, 184 ).
d( bristol, portsmouth, 97 ).
d( bristol, sheffield, 161 ).
d( bristol, swansea, 89 ).
d( bristol, york, 211 ).
d( bristol, london, 116 ).
d( cambridge, cardiff, 177 ).
d( cambridge, carlisle, 260 ).
d( cambridge, dover, 125 ).
d( cambridge, edinburgh, 330 ).
d( cambridge, exeter, 216 ).
d( cambridge, glasgow, 354 ).
d( cambridge, hull, 124 ).
d( cambridge, leeds, 143 ).
d( cambridge, liverpool, 185 ).
d( cambridge, manchester, 159 ).
d( cambridge, newcastle, 226 ).
d( cambridge, nottingham, 82 ).
d( cambridge, oxford, 80 ).
d( cambridge, penzance, 329 ).
d( cambridge, portsmouth, 126 ).
d( cambridge, sheffield, 116 ).
d( cambridge, swansea, 216 ).
d( cambridge, york, 149 ).
d( cambridge, london, 54 ).
d( cardiff, carlisle, 277 ).
d( cardiff, dover, 232 ).
d( cardiff, edinburgh, 370 ).
d( cardiff, exeter, 119 ).
d( cardiff, glasgow, 371 ).
d( cardiff, hull, 227 ).
d( cardiff, leeds, 209 ).
d( cardiff, liverpool, 164 ).
d( cardiff, manchester, 176 ).
d( cardiff, newcastle, 298 ).
d( cardiff, nottingham, 162 ).
d( cardiff, oxford, 106 ).
d( cardiff, penzance, 227 ).
d( cardiff, portsmouth, 141 ).
d( cardiff, sheffield, 175 ).
d( cardiff, swansea, 45 ).
d( cardiff, york, 232 ).
d( cardiff, london, 161 ).
d( carlisle, dover, 373 ).
d( carlisle, edinburgh, 93 ).
d( carlisle, exeter, 352 ).
d( carlisle, glasgow, 94 ).
d( carlisle, hull, 149 ).
d( carlisle, leeds, 117 ).
d( carlisle, liverpool, 118 ).
d( carlisle, manchester, 120 ).
d( carlisle, newcastle, 58 ).
d( carlisle, nottingham, 187 ).
d( carlisle, oxford, 260 ).
d( carlisle, penzance, 455 ).
d( carlisle, portsmouth, 338 ).
d( carlisle, sheffield, 148 ).
d( carlisle, swansea, 284 ).
d( carlisle, york, 112 ).
d( carlisle, london, 302 ).
d( dover, edinburgh, 451 ).
d( dover, exeter, 246 ).
d( dover, glasgow, 467 ).
d( dover, hull, 243 ).
d( dover, leeds, 269 ).
d( dover, liverpool, 269 ).
d( dover, manchester, 260 ).
d( dover, newcastle, 347 ).
d( dover, nottingham, 197 ).
d( dover, oxford, 128 ).
d( dover, penzance, 355 ).
d( dover, portsmouth, 130 ).
d( dover, sheffield, 235 ).
d( dover, swansea, 271 ).
d( dover, york, 269 ).
d( dover, london, 71 ).
d( edinburgh, exeter, 445 ).
d( edinburgh, glasgow, 44 ).
d( edinburgh, hull, 221 ).
d( edinburgh, leeds, 195 ).
d( edinburgh, liverpool, 211 ).
d( edinburgh, manchester, 213 ).
d( edinburgh, newcastle, 104 ).
d( edinburgh, nottingham, 258 ).
d( edinburgh, oxford, 357 ).
d( edinburgh, penzance, 548 ).
d( edinburgh, portsmouth, 435 ).
d( edinburgh, sheffield, 229 ).
d( edinburgh, swansea, 377 ).
d( edinburgh, york, 184 ).
d( edinburgh, london, 380 ).
d( exeter, glasgow, 446 ).
d( exeter, hull, 282 ).
d( exeter, leeds, 271 ).
d( exeter, liverpool, 239 ).
d( exeter, manchester, 237 ).
d( exeter, newcastle, 360 ).
d( exeter, nottingham, 217 ).
d( exeter, oxford, 136 ).
d( exeter, penzance, 112 ).
d( exeter, portsmouth, 126 ).
d( exeter, sheffield, 237 ).
d( exeter, swansea, 165 ).
d( exeter, york, 287 ).
d( exeter, london, 172 ).
d( glasgow, hull, 243 ).
d( glasgow, leeds, 211 ).
d( glasgow, liverpool, 212 ).
d( glasgow, manchester, 214 ).
d( glasgow, newcastle, 148 ).
d( glasgow, nottingham, 281 ).
d( glasgow, oxford, 355 ).
d( glasgow, penzance, 549 ).
d( glasgow, portsmouth, 433 ).
d( glasgow, sheffield, 242 ).
d( glasgow, swansea, 378 ).
d( glasgow, york, 206 ).
d( glasgow, london, 396 ).
d( hull, leeds, 58 ).
d( hull, liverpool, 122 ).
d( hull, manchester, 90 ).
d( hull, newcastle, 117 ).
d( hull, nottingham, 90 ).
d( hull, oxford, 164 ).
d( hull, penzance, 396 ).
d( hull, portsmouth, 242 ).
d( hull, sheffield, 65 ).
d( hull, swansea, 266 ).
d( hull, york, 37 ).
d( hull, london, 172 ).
d( leeds, liverpool, 73 ).
d( leeds, manchester, 41 ).
d( leeds, newcastle, 89 ).
d( leeds, nottingham, 72 ).
d( leeds, oxford, 170 ).
d( leeds, penzance, 378 ).
d( leeds, portsmouth, 248 ).
d( leeds, sheffield, 34 ).
d( leeds, swansea, 229 ).
d( leeds, york, 23 ).
d( leeds, london, 198 ).
d( liverpool, manchester, 35 ).
d( liverpool, newcastle, 162 ).
d( liverpool, nottingham, 100 ).
d( liverpool, oxford, 165 ).
d( liverpool, penzance, 343 ).
d( liverpool, portsmouth, 243 ).
d( liverpool, sheffield, 70 ).
d( liverpool, swansea, 166 ).
d( liverpool, york, 96 ).
d( liverpool, london, 198 ).
d( manchester, newcastle, 130 ).
d( manchester, nottingham, 71 ).
d( manchester, oxford, 143 ).
d( manchester, penzance, 344 ).
d( manchester, portsmouth, 221 ).
d( manchester, sheffield, 38 ).
d( manchester, swansea, 188 ).
d( manchester, york, 64 ).
d( manchester, london, 189 ).
d( newcastle, nottingham, 155 ).
d( newcastle, oxford, 253 ).
d( newcastle, penzance, 468 ).
d( newcastle, portsmouth, 331 ).
d( newcastle, sheffield, 123 ).
d( newcastle, swansea, 318 ).
d( newcastle, york, 80 ).
d( newcastle, london, 276 ).
d( nottingham, oxford, 98 ).
d( nottingham, penzance, 322 ).
d( nottingham, portsmouth, 176 ).
d( nottingham, sheffield, 38 ).
d( nottingham, swansea, 173 ).
d( nottingham, york, 80 ).
d( nottingham, london, 126 ).
d( oxford, penzance, 250 ).
d( oxford, portsmouth, 78 ).
d( oxford, sheffield, 136 ).
d( oxford, swansea, 145 ).
d( oxford, york, 178 ).
d( oxford, london, 57 ).
d( penzance, portsmouth, 242 ).
d( penzance, sheffield, 348 ).
d( penzance, swansea, 273 ).
d( penzance, york, 398 ).
d( penzance, london, 281 ).
d( portsmouth, sheffield, 214 ).
d( portsmouth, swansea, 186 ).
d( portsmouth, york, 256 ).
d( portsmouth, london, 72 ).
d( sheffield, swansea, 196 ).
d( sheffield, york, 52 ).
d( sheffield, london, 164 ).
d( swansea, york, 248 ).
d( swansea, london, 200 ).
d( york, london, 198 ).
% End of list of distances