Examples to explain Python's solution to the Traveling Salesman Problem (TSP) based on the backtracking subset tree template

This article mainly introduces Python to solve the traveling salesman problem (TSP) based on the backtracking method subset tree template. It briefly describes the traveling salesman problem and analyzes the related implementation of Python using the backtracking method subset tree template to solve the traveling salesman problem in the form of examples. For steps and operating techniques, friends in need can refer to

This article describes how Python solves the Traveling Salesman Problem (TSP) based on the backtracking subset tree template. Share it with everyone for your reference. The details are as follows:

Problem

The Traveling Salesman Problem (TSP) is the problem of traveling salesmen to Traveling to several cities, the cost between each city is known. In order to save costs, the travel salesman decided to start from the city where he was, travel to each city once and then return to the original city, and asked him what route he should choose to get all the places. The shortest total cost of walking?

Analysis

This problem can be described as follows: G=(V,E) is weighted For a directed graph, find a directed ring containing each node in V, that is, a traveling route that minimizes the sum of the costs of all edges on this directed ring.

The difference between this question and the previous article http://www.jb51.net/article/122933.htm is that this question is a weighted picture. Just a small modification is all it takes.

The length of the solution is fixed n+1.

Every node in the graph has its own adjacent nodes. For a node, all its adjacent nodes constitute the node's state space. When the path reaches this node, its state space is traversed.

In the end, the optimal solution must be found!

Obviously, continue to apply the backtracking method subset tree template! ! !

Code

'''旅行商问题（Traveling Salesman Problem,TSP）'''
# 用邻接表表示带权图
n = 5 # 节点数
a,b,c,d,e = range(n) # 节点名称
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) # 一个解（n+1元数组，长度固定）
X = []     # 一组解
best_x = [0]*(n+1) # 已找到的最佳解（路径）
min_cost = 0    # 最小旅费
# 冲突检测
def conflict(k):
  global n,graph,x,best_x,min_cost
  # 第k个节点，是否前面已经走过
  if k < n and x[k] in x[:k]:
    return True
  # 回到出发节点
  if k == n and x[k] != x[0]:
    return True
  # 前面部分解的旅费之和超出已经找到的最小总旅费
  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 # 无冲突
# 旅行商问题（TSP）
def tsp(k): # 到达（解x的）第k个节点
  global n,a,b,c,d,e,graph,x,X,min_cost,best_x
  if k > n: # 解的长度超出，已走遍n+1个节点 （若不回到出发节点，则 k==n）
    cost = sum([graph[node1][node2] for node1,node2 in zip(x[:-1], x[1:])]) # 计算总旅费
    if min_cost == 0 or cost < min_cost:
      best_x = x[:]
      min_cost = cost
      #print(x)
  else:
    for node in graph[x[k-1]]: # 遍历节点x[k-1]的邻接节点（状态空间）
      x[k] = node
      if not conflict(k): # 剪枝
        tsp(k+1)
# 测试
x[0] = c # 出发节点：路径x的第一个节点（随便哪个）
tsp(1)  # 开始处理解x中的第2个节点
print(best_x)
print(min_cost)

Rendering

The above is the detailed content of Examples to explain Python's solution to the Traveling Salesman Problem (TSP) based on the backtracking subset tree template. For more information, please follow other related articles on the PHP Chinese website!