'''旅行商問題（Traveling Salesman Problem,TSP）'''
# 用鄰接表表示帶權(quán)圖
n = 5 # 節(jié)點(diǎn)數(shù)
a,b,c,d,e = range(n) # 節(jié)點(diǎ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) # 一個(gè)解（n+1元數(shù)組，長(zhǎng)度固定）
X = []     # 一組解
best_x = [0]*(n+1) # 已找到的最佳解（路徑）
min_cost = 0    # 最小旅費(fèi)
# 沖突檢測(cè)
def conflict(k):
  global n,graph,x,best_x,min_cost
  # 第k個(gè)節(jié)點(diǎn)，是否前面已經(jīng)走過
  if k < n and x[k] in x[:k]:
    return True
  # 回到出發(fā)節(jié)點(diǎn)
  if k == n and x[k] != x[0]:
    return True
  # 前面部分解的旅費(fèi)之和超出已經(jīng)找到的最小總旅費(fèi)
  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): # 到達(dá)（解x的）第k個(gè)節(jié)點(diǎn)
  global n,a,b,c,d,e,graph,x,X,min_cost,best_x
  if k > n: # 解的長(zhǎng)度超出，已走遍n+1個(gè)節(jié)點(diǎn) （若不回到出發(fā)節(jié)點(diǎn)，則 k==n）
    cost = sum([graph[node1][node2] for node1,node2 in zip(x[:-1], x[1:])]) # 計(jì)算總旅費(fèi)
    if min_cost == 0 or cost < min_cost:
      best_x = x[:]
      min_cost = cost
      #print(x)
  else:
    for node in graph[x[k-1]]: # 遍歷節(jié)點(diǎn)x[k-1]的鄰接節(jié)點(diǎn)（狀態(tài)空間）
      x[k] = node
      if not conflict(k): # 剪枝
        tsp(k+1)
# 測(cè)試
x[0] = c # 出發(fā)節(jié)點(diǎn)：路徑x的第一個(gè)節(jié)點(diǎn)（隨便哪個(gè)）
tsp(1)  # 開始處理解x中的第2個(gè)節(jié)點(diǎn)
print(best_x)
print(min_cost)