Travelling Salesman Problem

[sophryu99]

Travelling Salesman Problem

Problem: Given a set of cities and distance between every pair of cities, the problem is to find the shortest possible route that visits every city exactly once and returns to the starting point.

• A TSP tour in the graph is 1-2-4-3-1. The cost of the tour is 10+25+30+15 which is 80.

[sophryu99]

Naive Approach

1. Consider city 1 as the starting and ending point.
2. Generate all (n-1)! Permutations of cities.
3. Calculate cost of every permutation and keep track of minimum cost permutation.
4. Return the permutation with minimum cost.

Time Complexity: O(n!)

# Python3 program to implement traveling salesman
# problem using naive approach.
from sys import maxsize
from itertools import permutations
V = 4

# implementation of traveling Salesman Problem
def travellingSalesmanProblem(graph, s):

	# store all vertex apart from source vertex
	vertex = []
	for i in range(V):
		if i != s:
			vertex.append(i)

	# store minimum weight Hamiltonian Cycle
	min_path = maxsize
	next_permutation=permutations(vertex)
	for i in next_permutation:

		# store current Path weight(cost)
		current_pathweight = 0

		# compute current path weight
		k = s
		for j in i:
			current_pathweight += graph[k][j]
			k = j
		current_pathweight += graph[k][s]

		# update minimum
		min_path = min(min_path, current_pathweight)
		
	return min_path


# Driver Code
if __name__ == "__main__":

	# matrix representation of graph
	graph = [[0, 10, 15, 20], [10, 0, 35, 25],
			[15, 35, 0, 30], [20, 25, 30, 0]]
	s = 0
	print(travellingSalesmanProblem(graph, s))

Output: 80

[sophryu99]

Dynamic Programming

• Consider 1 as starting and ending point of output.
• For every other vertex i, find the minimum cost path with 1 as the starting point, i as the ending point.
• Let the cost of this path be cost(i), cost will be updated by traversing through cycles; cost(i) + dist(i, 1), where dist(i, 1) is the distance from i to 1.
• Return the minimum of all [cost(i) + dist(i, 1)] values.

If size of S is 2, then S must be {1, i}, 
C(S, i) = dist(1, i) 
Else if size of S is greater than 2.
C(S, i) = min {C(S-{i}, j) + dis(j, i)} where j belongs to S, j != i and j != 1.

# Python3 implementation of the approach
V = 4
answer = []

# Function to find the minimum weight
# Hamiltonian Cycle
def tsp(graph, v, currPos, n, count, cost):

	# If last node is reached and it has
	# a link to the starting node i.e
	# the source then keep the minimum
	# value out of the total cost of
	# traversal and "ans"
	# Finally return to check for
	# more possible values
	if (count == n and graph[currPos][0]):
		answer.append(cost + graph[currPos][0])
		return

	# BACKTRACKING STEP
	# Loop to traverse the adjacency list
	# of currPos node and increasing the count
	# by 1 and cost by graph[currPos][i] value
	for i in range(n):
		if (v[i] == False and graph[currPos][i]):
			
			# Mark as visited
			v[i] = True
			tsp(graph, v, i, n, count + 1,
				cost + graph[currPos][i])
			
			# Mark ith node as unvisited
			v[i] = False

# Driver code

# n is the number of nodes i.e. V
if __name__ == '__main__':
	n = 4
	graph= [[ 0, 10, 15, 20 ],
			[ 10, 0, 35, 25 ],
			[ 15, 35, 0, 30 ],
			[ 20, 25, 30, 0 ]]

	# Boolean array to check if a node
	# has been visited or not
	v = [False for i in range(n)]
	
	# Mark 0th node as visited
	v[0] = True

	# Find the minimum weight Hamiltonian Cycle
	tsp(graph, v, 0, n, 1, 0)

	# ans is the minimum weight Hamiltonian Cycle
	print(min(answer))

# This code is contributed by mohit kumar