Prolog Implementation of Traveling Salesperson Problem

This document presents two distinct approaches to solving the Traveling Salesperson Problem (TSP) using Prolog: an exact, brute-force method and a heuristic-based Nearest Neighbor algorithm. Both implementations are demonstrated with code and sample queries.

Exact Solver: Brute-Force TSP Algorithm

This section details a Prolog program that finds the optimal (shortest) path for the Traveling Salesperson Problem by generating and evaluating all possible tours. This method guarantees the optimal solution but can be computationally intensive for larger sets of cities.

Defining City Distances in Prolog

The distances between cities are defined using dist/3 facts. The predicate is made symmetric to ensure that dist(X,Y,D) implies dist(Y,X,D).

dist(a,b,10).
dist(a,c,15).
dist(a,d,20).

dist(b,c,35).
dist(b,d,25).

dist(c,d,30).

dist(X,Y,D) :- dist(Y,X,D). % Ensures symmetry in distances

Calculating Tour Path Cost

The path_cost/2 predicate recursively calculates the total cost of a given tour path by summing the distances between consecutive cities.

path_cost([_],0).
path_cost([A,B|T],Cost) :-
    dist(A,B,D),
    path_cost([B|T],C),
    Cost is D+C.

Generating All Possible TSP Tours

The tsp/3 predicate generates all possible tours starting and ending at a specified Start city. It uses Prolog's built-in select/3 and permutation/2 predicates to explore all permutations of the remaining cities.

tsp(Start,Path,Cost) :-
    Cities = [a,b,c,d],
    select(Start,Cities,Rest),
    permutation(Rest,Perm),
    append([Start|Perm],[Start],Path),
    path_cost(Path,Cost).

Identifying the Shortest TSP Tour

The shortest_tsp/3 predicate finds the tour with the minimum cost. It collects all possible tours and their costs using findall/3 and then sorts them to retrieve the shortest one.

shortest_tsp(Start,BestPath,MinCost) :-
    findall((P,C),tsp(Start,P,C),List),
    sort(2,@=<,List,[(BestPath,MinCost)|_]).

Sample Query & Output: Exact TSP Solver

Here is an example query to find the shortest path starting from city 'a' using the exact solver, along with its expected output:

?- shortest_tsp(a,Path,Cost).

Path = [a, b, d, c, a],
Cost = 80.

Heuristic Solver: Nearest Neighbor TSP

For larger problems, an exact solver can be too slow. Heuristic algorithms provide a faster, though not always optimal, solution. The Nearest Neighbor algorithm is a common choice for its simplicity and efficiency.

Nearest Neighbor Heuristic Explanation

• Approach: At each step, the algorithm picks the closest unvisited city from the current city.
• Efficiency: Significantly faster than a full search (brute-force) as it does not explore all possible paths.
• Optimality: May not always yield the globally optimal path, but often provides a good approximation.

Prolog Code for Nearest Neighbor TSP

This Prolog implementation of the Nearest Neighbor heuristic constructs a tour by iteratively selecting the closest unvisited city. Note that reverse/2 is assumed to be available (e.g., from library(lists)).

nearest_neighbor(Start,Path,TotalCost) :-
    Cities = [a,b,c,d],
    select(Start,Cities,Rest),
    nn(Start,Rest,[Start],PathReversed,0,Cost1), % PathReversed will be [LastVisited, ..., Start]
    reverse(PathReversed, PathOrdered), % PathOrdered will be [Start, ..., LastVisited]
    append(PathOrdered,[Start],Path), % Final Path: [Start, ..., LastVisited, Start]
    last(PathOrdered,Last), % Last city visited before returning to Start
    dist(Last,Start,BackCost),
    TotalCost is Cost1 + BackCost.

% Nearest neighbor helper predicate
nn(_,[],Path,Path,Cost,Cost).
nn(Current,CitiesLeft,AccPath,FinalPath,AccCost,FinalCost) :-
    nearest(Current,CitiesLeft,Next,Dist),
    select(Next,CitiesLeft,NewLeft),
    NewCost is AccCost + Dist,
    nn(Next,NewLeft,[Next|AccPath],FinalPath,NewCost,FinalCost).

% Find nearest city from Current among Cities
nearest(Current,Cities,Nearest,Dist) :-
    findall((C,D),(member(C,Cities),dist(Current,C,D)),List),
    sort(2,@=<,List,[(Nearest,Dist)|_]).

Sample Queries for Both TSP Methods

You can compare the results of the exact and heuristic solvers using these queries:

% Query for the exact shortest path:
?- shortest_tsp(a,Path,Cost).

% Query for the path found by the Nearest Neighbor heuristic:
?- nearest_neighbor(a,Path,Cost).