This article example describes Python based backtracking method subset tree templates to solve the Traveler's Problem (TSP). It is shared for your reference as follows:
concern
Traveling Salesman Problem (TSP) is a traveler who wants to travel to a number of cities, the cost between cities is known, in order to save money, the traveler decides to start from the city where he is, travel to each city once and then return to the initial city, ask him what route should be chosen in order to make the total cost of the traveled the shortest?
analyze
The problem can be described as follows: G=(V,E) is a weighted directed graph, find a directed ring containing every node in V, i.e., a peripatetic route that minimizes the sum of the costs of all the edges on this directed ring.
This question is related to the previous posthttps:///article/The difference is that this question is a graph with weights. Just a little minor modification is all that is needed.
The length of the solution is fixed at n + 1.
For each node in the graph, it has its own neighboring nodes. For a given node, all its neighboring nodes form the state space of this node. When a path reaches this node, traverse its state space.
Eventually, the optimal solution can surely be found!
Obviously, keep applying the backtracking method subset tree template!!!!
coding
'''Traveling Salesman Problem (TSP)'''
# Representation of weighted graphs with adjacency tables
n = 5 # of nodes
a,b,c,d,e = range(n) # Node name
graph = [
{b:7, c:6, d:1, e:3},
{a:7, c:3, d:7, e:8},
{a:6, b:3, d:12, e:11},
{a:1, b:7, c:12, e:2},
{a:3, b:8, c:11, d:2}
]
x = [0]*(n+1) # A solution (n+1 tuple of fixed length)
X = [] # A set of solutions
best_x = [0]*(n+1) # Best solution found (path)
min_cost = 0 # Minimum travel costs
# Conflict detection
def conflict(k):
global n,graph,x,best_x,min_cost
# The kth node, whether or not it's been traveled before
if k < n and x[k] in x[:k]:
return True
# Back to the departure node
if k == n and x[k] != x[0]:
return True
# The sum of the travel costs of the previous partial solutions exceeds the smallest total travel cost found.
cost = sum([graph[node1][node2] for node1,node2 in zip(x[:k], x[1:k+1])])
if 0 < min_cost < cost:
return True
return False # Conflict-free
# Traveler issues (TSP)
def tsp(k): # Reach the kth node (of solution x)
global n,a,b,c,d,e,graph,x,X,min_cost,best_x
if k > n: # length of solution exceeded, n+1 nodes traveled (k==n if not returning to starting node)
cost = sum([graph[node1][node2] for node1,node2 in zip(x[:-1], x[1:])]) # Calculate total travel costs
if min_cost == 0 or cost < min_cost:
best_x = x[:]
min_cost = cost
#print(x)
else:
for node in graph[x[k-1]]: # Traverse the neighbors of node x[k-1] (state space)
x[k] = node
if not conflict(k): # Pruning
tsp(k+1)
# Testing
x[0] = c # Departure node: first node of path x (whichever)
tsp(1) # The 2nd node in x at the beginning of the comprehension
print(best_x)
print(min_cost)
rendering (visual representation of how things will turn out)
More about Python related content can be viewed on this site topic: thePython Data Structures and Algorithms Tutorial》、《Python Socket Programming Tips Summary》、《Summary of Python function usage tips》、《Summary of Python string manipulation techniques》、《Python introductory and advanced classic tutorialsand theSummary of Python file and directory manipulation techniques》
I hope that what I have said in this article will help you in Python programming.