Python基于回溯法子集树模板解决m着色问题示例

本文实例讲述了Python基于回溯法子集树模板解决m着色问题。分享给大家供大家参考，具体如下：

问题

图的m-着色判定问题

给定无向连通图G和m种不同的颜色。用这些颜色为图G的各顶点着色，每个顶点着一种颜色，是否有一种着色法使G中任意相邻的2个顶点着不同颜色?

图的m-着色优化问题

若一个图最少需要m种颜色才能使图中任意相邻的2个顶点着不同颜色，则称这个数m为该图的色数。求一个图的最小色数m的问题称为m-着色优化问题。

分析

解的长度是固定的，n。若x为本问题的一个解，则x[i]表示第i个节点的涂色编号。

可以将m种颜色看作每个节点的状态空间。每到一个节点，遍历所有颜色，剪枝，回溯。

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

代码

'''图的m着色问题'''
# 用邻接表表示图
n = 5 # 节点数
a,b,c,d,e = range(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元数组，长度固定）注意：解x的下标就是a,b,c,d,e!!!
X = []   # 一组解
# 冲突检测
def conflict(k):
  global n,graph,x
  # 找出第k个节点前面已经涂色的邻接节点
  nodes = [node for node in range(k) if node in graph[k]]
  if x[k] in [x[node] for node in nodes]: # 已经有相邻节点涂了这种颜色
    return True
  return False # 无冲突
# 图的m着色（全部解）
def dfs(k): # 到达（解x的）第k个节点
  global n,m,graph,x,X
  if k == n: # 解的长度超出
    print(x)
    #X.append(x[:])
  else:
    for color in range(m): # 遍历节点k的可涂颜色编号（状态空间），全都一样
      x[k] = color
      if not conflict(k): # 剪枝
        dfs(k+1)
# 测试
dfs(a)  # 从节点a开始

效果图

更多关于Python相关内容可查看本站专题：《Python数据结构与算法教程》、《Python Socket编程技巧总结》、《Python函数使用技巧总结》、《Python字符串操作技巧汇总》、《Python入门与进阶经典教程》及《Python文件与目录操作技巧汇总》

希望本文所述对大家Python程序设计有所帮助。

赞 (0)

相关推荐

  • Python基于回溯法子集树模板解决数字组合问题实例

    Python基于回溯法子集树模板解决数字组合问题实例

    本文实例讲述了Python基于回溯法子集树模板解决数字组合问题.分享给大家供大家参考,具体如下: 问题 找出从自然数1.2.3.....n中任取r个数的所有组合. 例如,n=5,r=3的所有组合为: 1,2,3 1,2,4 1,2,5 1,3,4 1,3,5 1,4,5 2,3,4 2,3,5 2,4,5 3,4,5 分析 换个角度,r=3的所有组合,相当于元素个数为3的所有子集.因此,在遍历子集树的时候,对元素个数不为3的子树剪枝即可. 注意,这里不妨使用固定长度的解. 直接套用子集树模板.

  • Python使用回溯法子集树模板解决爬楼梯问题示例

    Python使用回溯法子集树模板解决爬楼梯问题示例

    本文实例讲述了Python使用回溯法子集树模板解决爬楼梯问题.分享给大家供大家参考,具体如下: 问题 某楼梯有n层台阶,每步只能走1级台阶,或2级台阶.从下向上爬楼梯,有多少种爬法? 分析 这个问题之前用分治法解决过.但是,这里我要用回溯法子集树模板解决它. 祭出元素-状态空间分析大法:每一步是一个元素,可走的步数[1,2]就是其状态空间.不难看出,元素不固定,状态空间固定. 直接上代码. 代码 '''爬楼梯''' n = 7 # 楼梯阶数 x = [] # 一个解(长度不固定,1-2数组,表示

  • Python基于回溯法子集树模板解决选排问题示例

    Python基于回溯法子集树模板解决选排问题示例

    本文实例讲述了Python基于回溯法子集树模板解决选排问题.分享给大家供大家参考,具体如下: 问题 从n个元素中挑选m个元素进行排列,每个元素最多可重复r次.其中m∈[2,n],r∈[1,m]. 如:从4个元素中挑选3个元素进行排列,每个元素最多可重复r次. 分析 解x的长度是固定的,为m. 对于解x,先排第0个位置的元素x[0],再排第1个位置的元素x[1].我们把后者看作是前者的一种状态,即x[1]是x[0]的一种状态!! 一般地,把x[k]看作x[k-1]的状态空间a中的一种状态,我们要做

  • Python基于回溯法子集树模板解决旅行商问题（TSP）实例

    Python基于回溯法子集树模板解决旅行商问题（TSP）实例

    本文实例讲述了Python基于回溯法子集树模板解决旅行商问题(TSP).分享给大家供大家参考,具体如下: 问题 旅行商问题(Traveling Salesman Problem,TSP)是旅行商要到若干个城市旅行,各城市之间的费用是已知的,为了节省费用,旅行商决定从所在城市出发,到每个城市旅行一次后返回初始城市,问他应选择什么样的路线才能使所走的总费用最短? 分析 此问题可描述如下:G=(V,E)是带权的有向图,找到包含V中每个结点一个有向环,亦即一条周游路线,使得这个有向环上所有边成本之和最小

  • Python基于回溯法子集树模板解决全排列问题示例

    Python基于回溯法子集树模板解决全排列问题示例

    本文实例讲述了Python基于回溯法子集树模板解决全排列问题.分享给大家供大家参考,具体如下: 问题 实现 'a', 'b', 'c', 'd' 四个元素的全排列. 分析 这个问题可以直接套用排列树模板. 不过本文使用子集树模板.分析如下: 一个解x就是n个元素的一种排列,显然,解x的长度是固定的,n. 我们这样考虑:对于解x,先排第0个元素x[0],再排第1个元素x[1],...,当来到第k-1个元素x[k-1]时,就将剩下的未排的所有元素看作元素x[k-1]的状态空间,遍历之. 至此,套用子

  • Python使用回溯法子集树模板解决迷宫问题示例

    Python使用回溯法子集树模板解决迷宫问题示例

    本文实例讲述了Python使用回溯法解决迷宫问题.分享给大家供大家参考,具体如下: 问题 给定一个迷宫,入口已知.问是否有路径从入口到出口,若有则输出一条这样的路径.注意移动可以从上.下.左.右.上左.上右.下左.下右八个方向进行.迷宫输入0表示可走,输入1表示墙.为方便起见,用1将迷宫围起来避免边界问题. 分析 考虑到左.右是相对的,因此修改为:北.东北.东.东南.南.西南.西.西北八个方向.在任意一格内,有8个方向可以选择,亦即8种状态可选.因此从入口格子开始,每进入一格都要遍历这8种状态.

  • Python基于回溯法子集树模板实现8皇后问题

    Python基于回溯法子集树模板实现8皇后问题

    本文实例讲述了Python基于回溯法子集树模板实现8皇后问题.分享给大家供大家参考,具体如下: 问题 8×8格的国际象棋上摆放八个皇后,使其不能互相攻击,即任意两个皇后都不能处于同一行.同一列或同一斜线上,问有多少种摆法. 分析 为了简化问题,考虑到8个皇后不同行,则每一行放置一个皇后,每一行的皇后可以放置于第0.1.2.....7列,我们认为每一行的皇后有8种状态.那么,我们只要套用子集树模板,从第0行开始,自上而下,对每一行的皇后,遍历它的8个状态即可. 代码: ''' 8皇后问题 '''

  • Python基于回溯法子集树模板解决0-1背包问题实例

    Python基于回溯法子集树模板解决0-1背包问题实例

    本文实例讲述了Python基于回溯法子集树模板解决0-1背包问题.分享给大家供大家参考,具体如下: 问题 给定N个物品和一个背包.物品i的重量是Wi,其价值位Vi ,背包的容量为C.问应该如何选择装入背包的物品,使得放入背包的物品的总价值为最大? 分析 显然,放入背包的物品,是N个物品的所有子集的其中之一.N个物品中每一个物品,都有选择.不选择两种状态.因此,只需要对每一个物品的这两种状态进行遍历. 解是一个长度固定的N元0,1数组. 套用回溯法子集树模板,做起来不要太爽!!! 代码 '''0-

  • Python基于回溯法子集树模板解决取物搭配问题实例

    Python基于回溯法子集树模板解决取物搭配问题实例

    本文实例讲述了Python基于回溯法子集树模板解决取物搭配问题.分享给大家供大家参考,具体如下: 问题 有5件不同的上衣,3条不同的裤子,4顶不同的帽子,从中取出一顶帽子.一件上衣和一条裤子作为一种搭配,问有多少种不同的搭配? 分析 换个角度看,现有头.身.腿三个元素,每个元素都有各自的几种状态. 头元素有['帽1', '帽2', '帽3', '帽4']共4种状态,身元素有['衣1', '衣2', '衣3', '衣4', '衣5']共5种状态,腿元素有['裤1', '裤2', '裤3']共3种状

  • python回溯法实现数组全排列输出实例分析

    本文实例讲述了python回溯法实现数组全排列输出的方法.分享给大家供大家参考.具体分析如下: 全排列解释:从n个不同元素中任取m(m≤n)个元素,按照一定的顺序排列起来,叫做从n个不同元素中取出m个元素的一个排列.当m=n时所有的排列情况叫全排列. from sys import stdout #code from http://www.jb51.net/ def perm(li, start, end): if(start == end): for elem in li: stdout.wr

  • Python基于回溯法子集树模板实现图的遍历功能示例

    Python基于回溯法子集树模板实现图的遍历功能示例

    本文实例讲述了Python基于回溯法子集树模板实现图的遍历功能.分享给大家供大家参考,具体如下: 问题 一个图: A --> B A --> C B --> C B --> D B --> E C --> A C --> D D --> C E --> F F --> C F --> D 从图中的一个节点E出发,不重复地经过所有其它节点后,回到出发节点E,称为一条路径.请找出所有可能的路径. 分析 将这个图可视化如下: 本问题涉及到图,那首

随机推荐