快捷導(dǎo)航

Python基于回溯法子集樹模板解決m著色問題示例

更新時間：2017年09月07日 10:44:41 作者：羅兵

這篇文章主要介紹了Python基于回溯法子集樹模板解決m著色問題,簡單描述了m著色問題并結(jié)合實(shí)例形式分析了Python使用回溯法子集樹模板解決m著色問題的具體步驟與相關(guān)操作注意事項(xiàng),需要的朋友可以參考下

本文實(shí)例講述了Python基于回溯法子集樹模板解決m著色問題。分享給大家供大家參考，具體如下：

問題

圖的m-著色判定問題

給定無向連通圖G和m種不同的顏色。用這些顏色為圖G的各頂點(diǎn)著色，每個頂點(diǎn)著一種顏色，是否有一種著色法使G中任意相鄰的2個頂點(diǎn)著不同顏色?

圖的m-著色優(yōu)化問題

若一個圖最少需要m種顏色才能使圖中任意相鄰的2個頂點(diǎn)著不同顏色，則稱這個數(shù)m為該圖的色數(shù)。求一個圖的最小色數(shù)m的問題稱為m-著色優(yōu)化問題。

分析

解的長度是固定的，n。若x為本問題的一個解，則x[i]表示第i個節(jié)點(diǎn)的涂色編號。

可以將m種顏色看作每個節(jié)點(diǎn)的狀態(tài)空間。每到一個節(jié)點(diǎn)，遍歷所有顏色，剪枝，回溯。

不難看出，可以套用回溯法子集樹模板。

代碼

'''圖的m著色問題'''
# 用鄰接表表示圖
n = 5 # 節(jié)點(diǎn)數(shù)
a,b,c,d,e = range(n) # 節(jié)點(diǎn)名稱
graph = [
  {b,c,d},
  {a,c,d,e},
  {a,b,d},
  {a,b,c,e},
  {b,d}
]
m = 4 # m種顏色
x = [0]*n # 一個解（n元數(shù)組，長度固定）注意：解x的下標(biāo)就是a,b,c,d,e!!!
X = []   # 一組解
# 沖突檢測
def conflict(k):
  global n,graph,x
  # 找出第k個節(jié)點(diǎn)前面已經(jīng)涂色的鄰接節(jié)點(diǎn)
  nodes = [node for node in range(k) if node in graph[k]]
  if x[k] in [x[node] for node in nodes]: # 已經(jīng)有相鄰節(jié)點(diǎn)涂了這種顏色
    return True
  return False # 無沖突
# 圖的m著色（全部解）
def dfs(k): # 到達(dá)（解x的）第k個節(jié)點(diǎn)
  global n,m,graph,x,X
  if k == n: # 解的長度超出
    print(x)
    #X.append(x[:])
  else:
    for color in range(m): # 遍歷節(jié)點(diǎn)k的可涂顏色編號（狀態(tài)空間），全都一樣
      x[k] = color
      if not conflict(k): # 剪枝
        dfs(k+1)
# 測試
dfs(a)  # 從節(jié)點(diǎn)a開始

效果圖