You selected tsp0.pl
% TSP: traveling salesperson problem
% 21 Aug 2003.
% main: search_all_route/0.
% example.
% the problem of covered wagon against attacks.
% (Ref. [1]. See also [2, p.35])
% Reference:
% [1] H.M. Wagner. Principles of Operations Reserch.
% Prentice-Hall, 1969.
% [2] T. Fujita and H. Kumada. Ishi-Kettei no Kagaku
% (Decision Sciences). Senbundo, 1996. (Japanese)
% The original has showed as an example of the shortest path
% algorithm using Dynamic Programming technique.
% We will see City 10 is same as City 1.
cities([1,2,3,4,5,6,7,8,9,10]).
city(S):- cities(SS), member(S,SS).
route(from(1),to(2),insurrance_premium(2)).
route(from(1),to(3),insurrance_premium(5)).
route(from(1),to(4),insurrance_premium(1)).
route(from(2),to(5),insurrance_premium(10)).
route(from(2),to(6),insurrance_premium(12)).
route(from(3),to(5),insurrance_premium(5)).
route(from(3),to(6),insurrance_premium(10)).
route(from(3),to(7),insurrance_premium(7)).
route(from(4),to(6),insurrance_premium(15)).
route(from(4),to(7),insurrance_premium(13)).
route(from(5),to(7),insurrance_premium(7)).
route(from(5),to(8),insurrance_premium(5)).
route(from(6),to(8),insurrance_premium(3)).
route(from(6),to(9),insurrance_premium(4)).
route(from(7),to(8),insurrance_premium(7)).
route(from(7),to(9),insurrance_premium(1)).
route(from(8),to(10),insurrance_premium(1)).
route(from(9),to(10),insurrance_premium(4)).
% enable the return trip.
route_1(from(X),to(Y),insurrance_premium(C)):-
route(from(X),to(Y),insurrance_premium(C)).
route_1(from(X),to(Y),insurrance_premium(C)):-
route(from(Y),to(X),insurrance_premium(C)).
% generate routes and aggregate the route costs.
% ----------------------------------------------------------- %
total_cost(ROUTE,COSTS,Total):-
% fix city 1 as the start point.
cities([S|NODES]),
len([S|NODES],N),
len([S|ROUTE],N),
trace_costs_of_route([S|ROUTE],COSTS,Total),
update_tsp_data([S|ROUTE],COSTS,Total).
trace_costs_of_route([End],[C],C):-
city(End),
cities([S|_]),
route_1(from(End),to(S),insurrance_premium(C)).
trace_costs_of_route([X|[Y|R]],[C|RC],TC):-
cities(NODES),
kth(K,NODES,_),
len([X|[Y|R]],K),
trace_costs_of_route([Y|R],RC,TC0),
route_1(from(X),to(Y),insurrance_premium(C)),
\+ member(X,R),
TC is TC0 + C.
:- dynamic tsp_data /4.
update_tsp_data(ROUTE,COSTS,Total):-
time_stamp(no,Time),
DATA = tsp_data(
time(Time),
route(ROUTE),
costs(COSTS),
total(Total)
),
%nl,write(DATA),
assert(DATA),
!.
% main routine for searching routes.
% ----------------------------------------------------------- %
search_all_route :-
nl,write('abolish all previous search data ? >'),
read(y),
abolish(tsp_data/4),
nl,write('go ahead ? >'),
read(y),
findall(city(S),city(S),[city(_)|LABEL1]),
findall(cost(S1->S),(city(S),S > 1,S1 is S - 1),LABEL2),
update_tsp_data([start_search|LABEL1],[cost(last->1)|LABEL2],999999),
fail.
search_all_route :-
total_cost(_,_,_),
fail.
search_all_route :-
tsp_data(_,route([start_search|LABEL1]),LABEL2,_),
update_tsp_data([end_search|LABEL1],LABEL2,999999),
show_best_route,
nl,write('save results into file ? (tsp0_out.txt in the current directory) ? >'),
read(y),
save_tsp_data_to_file.
show_best_route:-
nl,write('the best route as follows:'),
max(-X,
tsp_data(_,_,_,total(X))
),
findall(R,(tsp_data(_,R,_,TC),TC=@=total(X)),BEST),
forall(member(R,BEST),
(
nl,
write( (R,total(X)) )
)
).
save_tsp_data_to_file:-
tell_goal('tsp0_out.txt',
forall_such_that,
DATA,
(
tsp_data(
time([date(Date),time(Time)]),
route(ROUTE),
costs(COSTS),
total(Total)
),
append([Total],ROUTE,DATA1),
append(DATA1,COSTS,DATA2),
append(DATA2,[Date,Time],DATA)
)
).
% an alternative, rather mess way using ordering/3.
% ----------------------------------------------------------- %
total_costs_1(ROUTE,COSTS,Total):-
cities([S|_NODES1]),
% Hamilton cycle with arc cost
len([S|_NODES1],N),
rev([S|_NODES1],NODES),
ordering_of_length([S|ROUTE],NODES,N),
trace_costs_of_route_1([S|ROUTE],COSTS,Total).
trace_costs_of_route_1([End],[C],C):-
city(End),
cities([S|_]),
route_1(from(End),to(S),insurrance_premium(C)).
trace_costs_of_route_1([X|[Y|R]],[C|RC],infinite):-
trace_costs_of_route_1([Y|R],RC,TC0),
TC0 = infinite,
route_1(from(X),to(Y),insurrance_premium(C)).
trace_costs_of_route_1([X|[Y|R]],[infinite|RC],infinite):-
trace_costs_of_route_1([Y|R],RC,TC0),
TC0 = infinite,
\+ route_1(from(X),to(Y),insurrance_premium(_)).
trace_costs_of_route_1([X|[Y|R]],[C|RC],TC):-
trace_costs_of_route_1([Y|R],RC,TC0),
TC0 \= infinite,
route_1(from(X),to(Y),insurrance_premium(C)),
TC is TC0 + C.
trace_costs_of_route_1([X|[Y|R]],[infinte|RC],infinite):-
trace_costs_of_route_1([Y|R],RC,TC0),
TC0 \= infinite,
\+ route_1(from(X),to(Y),insurrance_premium(_)).
% ordering/3
% ----------------------------------------------------------- %
ordering_of_length([],_A,0).
ordering_of_length([C|B],A,N1):-
\+var(A),
len(A,L),
anum_seq(Q,L),
member(N,Q),
len(B,N),
ordering_of_length(B,A,N),
N1 is N + 1,
member(C,A),
\+ member(C,B).
% len/2 : alternative to the length/2
% ----------------------------------------------------------- %
len(A,B):-
len_0(A,B).
% length/2 of SWI-prolog fails at the case of both unbound variables.
len_0(A,B):-
var(A),
var(B),
!,
fail.
len_0([],0).
len_0([_|A],N):-
((integer(N),N>0)->N0 is N -1; true),
len_0(A,N0),
((integer(N0))->true; !,fail),
N is N0 + 1.
% kth/3 : alternative to the nth1/3
% ----------------------------------------------------------- %
nth_0(K,Y,X):-
kth_member(K0,Y,X),
K is K0 - 1.
nth_1(K,Y,X):-
kth_member(K,Y,X).
kth(K,Y,X):-
kth_member(K,Y,X).
kth_member(1,[X|_],X).
kth_member(K,[_|Y],X):-
kth_member(K1,Y,X),
K is K1 + 1.
% rev/2 : alternative to the reverse/2
% ----------------------------------------------------------- %
rev(A,B):-
len(A,L),
len(B,L),
rev(A,[],B),
!.
rev(A,A,[]):-!.
rev(A,B,[C|D]):-
rev(A,[C|B],D).
% descending/ascending natural number sequence less than N.
% ----------------------------------------------------------- %
dnum_seq([],N):-N<0,!.
dnum_seq([0],1).
dnum_seq([A|Q],N):-
A is N - 1,
len(Q,A),
dnum_seq(Q,A).
anum_seq(Aseq,N):-
dnum_seq(Dseq,N),
sort(Dseq,Aseq).
dnum_seq1(Q,N):-
M is N + 1,
dnum_seq(Q0,M),
subtract(Q0,[0],Q).
anum_seq1(Q,N):-
M is N + 1,
anum_seq(Q0,M),
subtract(Q0,[0],Q).
% a solver : maximization of goal wrt arguments
% ----------------------------------------------------------- %
min(X,Goal):-
max(Y,(Goal,Y = -1 * X)).
max(X,Goal):-
% X: the objective variable,
% Goal: the objective function and constraints,
setof((X,Goal),Goal,Z),
member((X,Goal),Z),
\+ (
member((Y,_),Z),
Y > X
).
/*
% mess
max(X,Goal):-
% X: the objective variable,
% Goal: the objective function and constraints,
setof((X,Goal),Goal,Z),
(max_1(X,Z);max_2(X,Z)).
max_1(X,Z):-
\+ ( member((AA,_),Z), \+ number(AA) ,write(AA)),
member((X,_Goal),Z),
\+ (
member((Y,_),Z),
Y > X
).
max_2(X,Z):-
member((AA,_Goal),Z),
\+ number(AA),
sort(Z,Z1),
rev(Z1,[(X,_)|_]).
*/
% redirect to file
%--------------------------------
tell_goal(File,G):-
(current_stream(File,write,S0)->close(S0);true),
open(File,write,S),
tell(File),
nl,
time_stamp('% file output start time ',_),
nl,
write('%---------- start from here ------------%'),
nl,
G,
nl,
write('%---------- end of data ------------%'),
nl,
time_stamp('% file output end time ',_),
tell(user),
close(S),
% The following is to cope with the duplicated stream problem.
(current_stream(File,write,S1)->close(S1);true).
% 成功するゴールをすべて保存
%--------------------------------
tell_goal(File,forall,G):-
G0 = (nl,write(G),write('.')),
G1 = forall(G,G0),
tell_goal(File,G1).
tell_goal(File,forall_such_that,G,Condition):-
% G should be occurred in the Condition.
WRITE = (nl,write(G),write('.')),
G1 = forall(Condition,WRITE),
tell_goal(File,G1).
% time stamp
%--------------------------------
time_stamp(no,T):-
get_time(U),
convert_time(U,A,B,C,D,E,F,_G),
T = [date(A/B/C), time(D:E:F)].
time_stamp(Word,T):-
\+ var(Word),
Word \= no,
get_time(U),
convert_time(U,A,B,C,D,E,F,_G),
T = [date(A/B/C), time(D:E:F)],
% format('~`.t~t~a~30|~`.t~t~70|~n',[Word]),
write((Word,T)),
nl.
:- search_all_route.
return to front page.