示范校建设 成果网站,wordpress图片分页插件,重庆公司章程在哪里打印,wordpress抓取文章目录问题描述说明性描述操作性描述图着色问题图着色算法算法精化和python描述算法细节处理#xff1a;python实现讨论问题描述
说明性描述
说明性描述说明了需要解决的问题是什么#xff0c;针对什么样的问题#xff0c;期望什么样的解 这是一个5条路的交叉口#x…
文章目录问题描述说明性描述操作性描述图着色问题图着色算法算法精化和python描述算法细节处理python实现讨论问题描述
说明性描述
说明性描述说明了需要解决的问题是什么针对什么样的问题期望什么样的解 这是一个5条路的交叉口其中两条是单行线。这个图本身已经是实际问题的抽象与行驶方向无关的因素如道路方位、宽度、车流量等都已被抽象去除。要求设计红绿灯按不同方向行驶的车辆不能相互冲突依次通过在此基础上要求红绿灯轮转次数最少。 现在基本想法是对行驶方向分组
同属一组的各个方向行驶的车辆均可以同时行驶不出现相互交错的行驶路线所做的分组应该尽可能大
操作性描述
操作性描述说明通过怎样的操作过程可以得到所要的解 采用图来进一步抽象问题其中顶点集VVV中的顶点元素表示所有可能可行方向不难列出本例一共13个AB, AC, AD, BA, BC, BD, DA, DB, DC, EA, EB, EC, ED。边集EEE中的元素表示两个顶点所代表的可行方向有冲突。 有了冲突图寻找安全分组的问题就可以换一种说法为冲突图中的顶点确定一种分组保证属于同一组的顶点互不邻接。
要解决的问题进一步抽象为图数据结构上的顶点分组。
图着色问题
以非相邻为条件的最佳顶点分组问题其实对应于有名的图最佳着色问题把顶点看成区域把相邻看成两个顶点有边界把不同分组看做给相邻顶点以不同颜色着色。著名的四色问题表明对于任一方式分割为区域的平面图只需要4种颜色着色就能保证相邻区域都具有不同颜色。
但是从交叉路口构造出的冲突图可能不是平面图因此完全可能需要更多的颜色。
图着色算法
现有的最佳着色算法基本相当于枚举所有可能的着色方案从中选出使用颜色最少的方案。 下面考虑使用贪婪算法或称贪心法。其基本思想是根据当时掌握的信息尽可能地向得到解的方向前进直到不能继续再换一个方向。这样做通常不能得到最优解但能找到“可接受的”解即给出一种较好的算法。 算法梗概伪代码如下
输入图G #记录图中的顶点连接关系
集合verts保存G中的所有顶点 #建立初始状态
设置集合groups为空集 #记录得到的分组元素是顶点集合
while 存在未着色的顶点: #每次迭代用贪心法找一个新分组选一种颜色在未着色顶点中给尽量多的无互连边的点着色(构建一个分组)记录新分组的顶点组# 算法结束时groups里记录着一种分组方式
# 算法细节还需要进一步考虑上面算法还有重要的细节要考虑一种新颜色的着色处理。具体
图G保存需着色图中顶点的邻接信息集合verts是图中所有尚未着色的顶点集合用另一个变量new_group记录正在构造的用当前新颜色着色的顶点一个顶点在上面算法的每次迭代中重新构造每次重新分组时将这个集合重新设置为空集。 # 进一步整理着色问题。
new_group 空集
for v in verts:if v与new_group中所有的顶点之间都没有边:从verts中去掉v把v加入new_group # 循环结束时new_group中是可以用一种颜色着色的顶点集合。
# 用这段代码代替前面程序框架中主循环体里的一部分。检查上面的算法可以看到算法涉及一些集合操作和图操作。
构造空集从集合中删除元素向集合中加入元素顺序获取集合里的各个元素使用for循环获取图中所有顶点判断两个顶点是否相邻
算法精化和python描述
算法细节处理
如何表示颜色 顺序整数如何记录得到的分组用集合表示分组把构造好的分组集合加入groups作为元素如何表示图结构
python的集合操作 10. 判断集合vs是否空集not vs 11. 设置一个集合为空vs set() 12. 从集合中去掉一个元素vs.remove(v) 13. 向集合中增加一个元素vs.add(v)
python的集合数据类型不支持遍历需要从当时的集合verts生成一个表然后对表做遍历。 算法中需要的图操作依赖于如何在python中实现图数据结构这里假定两个与图有关的操作
函数vertices(G)得到G中所有顶点的集合谓词 not_adjacent_with_set(v, group, G)检查顶点v与顶点集group中各顶点在图G中是否有边连接。
有了以上假设就可以写程序
python实现
def coloring(G): #做图G的着色color 0groups set()verts vertices(G) #取得G图的所有顶点,依赖于图的表示while verts:new_group set()for v in list(verts):if not_adjacent_with_set(v, newgroup, G):new_group.add(v)verts.remove(v)group.add((color, new_group))color 1return groups这个python函数能对任何一个图算出顶点分组。其中欠缺的细节就是图的表示以及函数里设计的两个图操作
讨论
对于给定的交叉路口实例可行的分组可能不唯一。算法给出的解是确定的依赖于算法中选择顶点的具体策略以及对图中顶点的遍历顺序即**list(verts)**给出的顶点序列中的顺序。 回顾前面从问题出发做出一个python程序的工作过程
有关工作开始于交叉路口的抽象图示首先枚举出所有允许通行方向根据通行方向和冲突的定义画出冲突图把通行方向分组问题归结为冲突图中不相邻顶点的划分问题。
问题是这样的结果满足原交叉路口实例的需要吗
仔细分析上面算法中采取的定义不统一
算法给出的结果是各分组互不相交每个顶点只属于一个分组而工作实际是只要求同属一组的顶点是互不冲突的即允许顶点属于不同分组的情况。
需要将之前得到的分组尽可能扩充加入与已有分组不冲突的方向如何修改前面算法使之能给出这样分组
