Week 7 Write a program to solve the traveling salesman problems
Write a program to solve water jug problems using Prolog.
In Prolog, lists are a fundamental data structure used to represent ordered sequences of terms.
Examples:
[] (empty list)
[apple, banana, cherry]
[1, 2, 3, 4, 5]
[a, [b, c], d] (lists can contain other lists)
[Head | Tail](A list with a head and a tail)
% calculating the sum of the elements in a list of numbers.
% Base case: The sum of an empty list is 0.
sum_list([], 0).
% Recursive case: The sum of a list is the head plus the sum of the tail.
sum_list([Head | Tail], Sum) :-
sum_list(Tail, TailSum),
Sum is Head + TailSum.
% Example list
my_numbers([1, 2, 3, 4, 5]).
% Example query:
% ?- my_numbers(L), sum_list(L, Result).
% L = [1, 2, 3, 4, 5],
% Result = 15.
----------------------------X-----------------------------------
% Accessing a list element by index (0-based)
element_at(0, [Head | _], Head). % Base case: index 0 is the head
element_at(Index, [_ | Tail], Element) :-
Index > 0,
NewIndex is Index - 1,
element_at(NewIndex, Tail, Element).
% Example list
my_list([a, b, c, d, e]).
% Example queries:
Page 1 of 4
% ?- my_list(L), element_at(2, L, Element).
% L = [a, b, c, d, e],
% Element = c.
% ?- my_list(L), element_at(0, L, Element).
% L = [a, b, c, d, e],
% Element = a.
% ?- my_list(L), element_at(4, L, Element).
% L = [a, b, c, d, e],
% Element = e.
-------------------------------X------------------------------------
%Head and Tail of prolog lists are accessed
% A sample list
my_list([apple, banana, cherry]).
% Accessing the Head
get_head([Head | _], Head).
% Accessing the Tail
get_tail([_ | Tail], Tail).
% Example queries:
% ?- my_list(L), get_head(L, Head).
% L = [apple, banana, cherry],
% Head = apple.
% ?- my_list(L), get_tail(L, Tail).
% L = [apple, banana, cherry],
% Tail = [banana, cherry].
% Combined Head and Tail access:
get_head_and_tail([Head | Tail], Head, Tail).
% ?- my_list(L), get_head_and_tail(L, H, T).
% L = [apple, banana, cherry],
% H = apple,
% T = [banana, cherry].
------------------------------------X-------------------------------------
The Traveling Salesman Problems
The Traveling Salesman Problem (TSP) is a classic computational challenge that asks: "Given a list of cities and the
distances between each pair of them, what is the shortest possible route that visits each city exactly once and returns
to the origin city?"
% Define the edges with their respective costs
edge(a, b, 10).
edge(a, c, 15).
edge(a, d, 20).
edge(b, a, 10).
edge(b, c, 35).
Page 2 of 4
edge(b, d, 25).
edge(c, a, 15).
edge(c, b, 35).
edge(c, d, 30).
edge(d, a, 20).
edge(d, b, 25).
edge(d, c, 30).
% Find all permutations of the cities
tsp(Start, Path, Cost) :-
findall(City, edge(Start, City, _), Cities),
permutation(Cities, PermPath),
complete_path(Start, PermPath, Path, Cost).
% Compute the total cost of a path
complete_path(Start, PermPath, [Start | PermPathWithStart], TotalCost) :-
append(PermPath, [Start], PermPathWithStart),
path_cost([Start | PermPathWithStart], TotalCost).
% Calculate path cost
path_cost([_], 0).
path_cost([A, B | Rest], Cost) :-
edge(A, B, C),
path_cost([B | Rest], RestCost),
Cost is C + RestCost.
% Find the best path with the minimum cost
best_tsp(Start, BestPath, MinCost) :-
findall((Path, Cost), tsp(Start, Path, Cost), Paths),
min_member((BestPath, MinCost), Paths).
% Query example:
% ?- best_tsp(a, Path, Cost).
Write a program to solve water jug problems using Prolog.
% Water Jug Problem in Prolog
% Define possible moves: Fill, Empty, Transfer
move(state(J1, J2), fill(jug1), state(Cap1, J2)) :-
capacity(jug1, Cap1), J1 < Cap1.
move(state(J1, J2), fill(jug2), state(J1, Cap2)) :-
capacity(jug2, Cap2), J2 < Cap2.
move(state(J1, J2), empty(jug1), state(0, J2)) :-
J1 > 0.
Page 3 of 4
move(state(J1, J2), empty(jug2), state(J1, 0)) :-
J2 > 0.
move(state(J1, J2), transfer(jug1, jug2), state(NJ1, NJ2)) :-
capacity(jug2, Cap2), J1 > 0, J2 < Cap2,
Space is Cap2 - J2,
Transfer is min(J1, Space),
NJ1 is J1 - Transfer,
NJ2 is J2 + Transfer.
move(state(J1, J2), transfer(jug2, jug1), state(NJ1, NJ2)) :-
capacity(jug1, Cap1), J2 > 0, J1 < Cap1,
Space is Cap1 - J1,
Transfer is min(J2, Space),
NJ1 is J1 + Transfer,
NJ2 is J2 - Transfer.
% Define capacities of jugs
capacity(jug1, 4).
capacity(jug2, 3).
% Solve the problem using BFS
solve(Quantity) :-
bfs([[state(0, 0)]], Quantity, Solution),
reverse(Solution, Steps),
print_steps(Steps, Quantity).
bfs([[state(J1, J2) | Path] | _], Quantity, [state(J1, J2) | Path]) :-
J1 = Quantity ; J2 = Quantity.
bfs([Path | Rest], Quantity, Solution) :-
extend(Path, NewPaths),
append(Rest, NewPaths, Queue),
bfs(Queue, Quantity, Solution).
extend([State | Path], NewPaths) :-
findall([NewState, State | Path], (move(State, _, NewState), \+ member(NewState, [State | Path])), NewPaths).
print_steps([], _).
print_steps([state(J1, J2) | Rest], Quantity) :-
capacity(jug1, Cap1),
capacity(jug2, Cap2),
write('Jug1 (Capacity: '), write(Cap1), write('L): '), write(J1), write('L, '),
write('Jug2 (Capacity: '), write(Cap2), write('L): '), write(J2), write('L'), nl,
print_steps(Rest, Quantity).
% Example query:
% ?- solve(2).
Page 4 of 4
