Artificial Intelligence – Real-World Examples of CSPs

Solving Traveling Sales Problem with CSP Algorithms

The Traveling Salesperson Problem (TSP) is to find the shortest path that travels through each city exactly once and returns to the starting city. As a Constraint Satisfaction Problem the variables, domains, and constraints of Traveling Sales Problem are listed below −

• Variables: The Cities (nodes) are variables in the graph.
• Domain: Any city that a salesperson visits except those cities already visited.
• Constraints: Each city is visited exactly once. The traveler returns back to the start city with minimized total travel distance.

Backtracking

Backtracking is a deep-search method which is used to find a solution for complex problems. First we assign a value to the variable from its domain by following the constraint step by step and if we find the constraint is violated we go back and try a different value for previous variables.

This code utilizes backtracking to find valid paths and decide which solution is best given the following constraints.

Step 1: Define the Problem

The graph is represented as a distance matrix. Here, graph[i][j] indicates the distance between City i and City j. For example, if graph[0][1] = 12, then the distance between City 1 and City 2 is 12 units.

Here, n refers to the total number of cities, and start_node refers to the city through which the algorithm begins searching for possible routes. This structure can be seen as a basic path-finding for solving Constraint Satisfaction Problem (CSP) approaches.

# The first step is to define the graph with nodes and edges representing cities and their distances.# Graph represented as a distance matrix
graph =[[0,12,17,22],# Distances from node 1[12,0,27,38],# Distances from node 2[17,27,0,32],# Distances from node 3[22,38,32,0]# Distances from node 4]
n =len(graph)# Number of nodes
start_node =0# Starting from node 1 (index 0)

Step 2: Define the TSP Solver Class

The TSP solver uses backtracking to explore all possible paths and find the optimal solution.

The graph and start_node are stored, and variables are initialized to track the best path and minimum cost (best_path and min_cost).

classTSP:def__init__(self, graph, start_node):
      self.graph = graph
      self.start_node = start_node
      self.best_path =None
      self.min_cost =float('inf')defsolve(self):
      visited =[False]*len(self.graph)
      visited[self.start_node]=True
      self.backtrack([self.start_node],0, visited)return self.best_path, self.min_cost
   
   defbacktrack(self, path, current_cost, visited):# Base case: All nodes visited, return to the startiflen(path)==len(self.graph):
         total_cost = current_cost + self.graph[path[-1]][self.start_node]if total_cost < self.min_cost:
            self.min_cost = total_cost
            self.best_path = path +[self.start_node]return# Try all possible next nodesfor next_node inrange(len(self.graph)):ifnot visited[next_node]and self.graph[path[-1]][next_node]>0:
            visited[next_node]=True
            self.backtrack(path +[next_node], current_cost + self.graph[path[-1]][next_node], visited)
            visited[next_node]=False

Step 3: Solve the TSP Problem

We create an instance of the TSP class and call the solve method.

The solver (solve method) is then invoked to compute the optimal path and minimum cost, starting from the specified node and traversing the graph using backtracking logic.

tsp = TSP(graph, start_node)
best_path, min_cost = tsp.solve()# Output the resultsprint("Optimal Path:",[node +1for node in best_path])# Convert to 1-based indexingprint("Minimum Cost:", min_cost)

Complete Code

The Traveling Sales Problem (TSP) solver’s complete implementation is shown below, which uses backtracking to determine the optimal path with the lowest cost.

# Graph represented as a distance matrix
graph =[[0,12,17,22],[12,0,27,38],[17,27,0,32],[22,38,32,0]]
n =len(graph)  
start_node =0classTSP:def__init__(self, graph, start_node):
      self.graph = graph
      self.start_node = start_node
      self.best_path =None
      self.min_cost =float('inf')defsolve(self):
      visited =[False]*len(self.graph)
      visited[self.start_node]=True
      self.backtrack([self.start_node],0, visited)return self.best_path, self.min_cost
   
   defbacktrack(self, path, current_cost, visited):iflen(path)==len(self.graph):
         total_cost = current_cost + self.graph[path[-1]][self.start_node]if total_cost < self.min_cost:
             self.min_cost = total_cost
             self.best_path = path +[self.start_node]returnfor next_node inrange(len(self.graph)):ifnot visited[next_node]and self.graph[path[-1]][next_node]>0:
            visited[next_node]=True
            self.backtrack(path +[next_node], current_cost + self.graph[path[-1]][next_node], visited)
            visited[next_node]=False
         
tsp = TSP(graph, start_node)
best_path, min_cost = tsp.solve()# Output the resultsprint("Optimal Path:",[node +1for node in best_path])print("Minimum Cost:", min_cost)

Following is the output of the above code −

Optimal Path: [1, 2, 3, 4, 1]
Minimum Cost: 93