快捷導(dǎo)航

Python基于回溯法子集樹(shù)模板解決m著色問(wèn)題示例

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

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

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

問(wèn)題

圖的m-著色判定問(wèn)題

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

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

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

分析

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

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

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

代碼

'''圖的m著色問(wèn)題'''
# 用鄰接表表示圖
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 # 一個(gè)解（n元數(shù)組，長(zhǎng)度固定）注意：解x的下標(biāo)就是a,b,c,d,e!!!
X = []   # 一組解
# 沖突檢測(cè)
def conflict(k):
  global n,graph,x
  # 找出第k個(gè)節(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 # 無(wú)沖突
# 圖的m著色（全部解）
def dfs(k): # 到達(dá)（解x的）第k個(gè)節(jié)點(diǎn)
  global n,m,graph,x,X
  if k == n: # 解的長(zhǎng)度超出
    print(x)
    #X.append(x[:])
  else:
    for color in range(m): # 遍歷節(jié)點(diǎn)k的可涂顏色編號(hào)（狀態(tài)空間），全都一樣
      x[k] = color
      if not conflict(k): # 剪枝
        dfs(k+1)
# 測(cè)試
dfs(a)  # 從節(jié)點(diǎn)a開(kāi)始

效果圖