역추적 하위 집합 트리 템플릿을 기반으로 하는 TSP(여행하는 세일즈맨 문제)에 대한 Python의 솔루션을 설명하는 예

이 기사에서는 주로 역추적 방법 하위 집합 트리 템플릿을 기반으로 여행하는 외판원 문제(TSP)를 해결하기 위해 Python을 소개합니다. 여행하는 외판원 문제를 간략하게 설명하고 역추적 방법 하위 집합 트리 템플릿을 사용하여 Python의 관련 구현 단계 및 구현 단계를 분석합니다. 여행하는 외판원 문제를 예제 형식으로 해결하세요. 운영 능력이 필요한 친구들이 참고할 수 있습니다

이 글에서는 역추적 방법 하위 집합 트리 템플릿을 기반으로 이동하는 외판원 문제(TSP)를 해결하는 Python의 예를 설명합니다. 참고를 위해 모든 사람과 공유하세요. 세부 사항은 다음과 같습니다.

Problem

Traveling Salesman Problem(TSP)은 여러 도시를 여행하고 싶어하는 여행하는 세일즈맨이며 각 도시 간 비용이 알려져 있습니다. 여행하는 세일즈맨은 비용을 절약하기 위해 자신이 위치한 도시에서 출발하여 각 도시를 한 번 여행한 다음 원래 도시로 돌아오는 경로를 선택하여 총 비용을 최소화하기로 결정했습니다.

Analytics

이 문제는 다음과 같이 설명할 수 있습니다. G=(V,E)는 V의 각 노드를 포함하는 방향성 링, 즉 다음과 같은 경로를 찾는 것입니다. 이 방향성 링의 모든 에지 비용의 합을 최소화합니다.

이 질문과 이전 기사 http://www.jb51.net/article/122933.htm의 차이점은 이 질문은 가중치가 부여된 그림이라는 것입니다. 약간의 수정만 하면 됩니다.

해의 길이는 n+1로 고정됩니다.

그래프의 모든 노드에는 인접한 노드가 있습니다. 노드의 경우 모든 인접 노드는 노드의 상태 공간을 구성합니다. 경로가 이 노드에 도달하면 해당 상태 공간을 통과합니다.

결국 최적의 솔루션은 반드시 발견될 것입니다!

분명히 역추적 방법 부분 집합 트리 템플릿을 계속해서 적용해 보세요! ! !

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

위 내용은 역추적 하위 집합 트리 템플릿을 기반으로 하는 TSP(여행하는 세일즈맨 문제)에 대한 Python의 솔루션을 설명하는 예의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!