- 浏览: 259249 次
- 性别:
- 来自: 深圳
文章分类
- 全部博客 (88)
- JAVA / base (26)
- JAVA / web (12)
- JAVA / Lib-tools (5)
- SERVER / tomcat (4)
- DB / mysql (4)
- DB / mongodb (2)
- DB / memcached (2)
- DB / redis (2)
- WEB / Front-end (3)
- WEB / security (4)
- WEB / css (2)
- WEB / js (4)
- OS / linux (3)
- IT / Architecture (4)
- IT / other (2)
- Android (9)
- Go (1)
- Other (1)
- OS / Mac (2)
最新评论
-
Zero2Max:
哈哈,马士兵老师也发现了。
java实现接口的bug -
xly1981:
能像CSRF攻击一样带个图就更棒了
XSS跨站攻击 -
xmong:
df274119386 写道在javascript中看到下面的 ...
CSRF攻击与防御策略 -
df274119386:
在javascript中看到下面的语句 e.value = t ...
CSRF攻击与防御策略 -
xmong:
<div class="quote_title ...
Tomcat集群
图着色问题
目录
1 图着色问题 1
1.1 问题背景 1
1.2 问题解析 1
1.3 问题解决 2
1.4 着色应用 5
1 图着色问题
1.1 问题背景
图的着色问题是由地图的着色问题引申而来的:用m种颜色为地图着色,使得地图上的每一个区域着一种颜色,且相邻区域颜色不同。
问题处理:如果把每一个区域收缩为一个顶点,把相邻两个区域用一条边相连接,就可以把一个区域图抽象为一个平面图。
1.2 问题解析
可以给定无向连通图G和m种不同的颜色。用这些颜色为图G的各顶点着色,每个顶点着一种颜色。是否有一种着色法使G中每条边的2个顶点着不同颜色。如果有则称这个图是m可着色,否则称这个图不是m可着色。若一个图最少需要k种颜色才能使图中每条边连接的2个顶点着不同颜色,则称这个数k为该图的色数。如下图:
可以用一下邻接矩阵来表示
邻接矩阵中通常用二维数组来存放边之间的关系,用一维数组来存放顶点的信息。所以在接下来的求解问题中我们将用到二维数组a来存放两边是否相邻,用一维数组x来存放每个顶点的颜色;x[i]=j表示第i个节点图第j中颜色。
根据矩阵我们要求出矩阵的色数K和着色方案?
1.3 问题解决
我们可以用贪心法给图着色,选择第一种颜色,以任意顶点作为开始顶点,依次考察图中的未被着色的每个顶点,如果第一个顶点可以用颜色1着色,换言之,该顶点的邻接点都还未被着色,则用颜色1为该顶点着色,当没有顶点能以这种颜色着色时,增加第二种颜色,选择颜色2和一个未被着色的顶点作为开始顶点,用第二种颜色为尽可能多的顶点着色,如果还有未着色的顶点,则选取颜色3并为尽可能多的顶点着色,依此类推。
代码实现:
输出结果:
1.4 着色应用
1,学校共有n门功课需要进行期末考试,因为不少学生不止选修一门课,所以不能把一个同学选修的两门课安排在同一场次进行考试。问学期的期末考试最少需要多少场次才能完成?
• 问题处理:我们以每门功课为一个顶点,当且仅当两门功课被同一个学生选修时,在响应两个顶点之间连一条边,得到一个图G。我们将n门功课划分成k个子集U1,U2,…,UK两两子集的功课都不相同。
• 每个子集Ui(1≤i≤k)的顶点两两子集不相邻,即子集内的任意两门功课都不能被一个学生选修。能这种要求划分的子集数K必须最少,即不能划分成k-1个子集。然后我们对每个子集内的顶点涂一种颜色。
• 同色顶点对应的课程安排在同一场次考试,颜色数即为学期考试所需要的最少场次数。
目录
1 图着色问题 1
1.1 问题背景 1
1.2 问题解析 1
1.3 问题解决 2
1.4 着色应用 5
1 图着色问题
1.1 问题背景
图的着色问题是由地图的着色问题引申而来的:用m种颜色为地图着色,使得地图上的每一个区域着一种颜色,且相邻区域颜色不同。
问题处理:如果把每一个区域收缩为一个顶点,把相邻两个区域用一条边相连接,就可以把一个区域图抽象为一个平面图。
1.2 问题解析
可以给定无向连通图G和m种不同的颜色。用这些颜色为图G的各顶点着色,每个顶点着一种颜色。是否有一种着色法使G中每条边的2个顶点着不同颜色。如果有则称这个图是m可着色,否则称这个图不是m可着色。若一个图最少需要k种颜色才能使图中每条边连接的2个顶点着不同颜色,则称这个数k为该图的色数。如下图:
可以用一下邻接矩阵来表示
{{1,1,1,1,0,0}, {1,1,1,1,1,0}, {1,1,1,1,0,0}, {1,1,1,1,1,0}, {0,1,0,1,1,1}, {0,0,0,0,1,1}};
邻接矩阵中通常用二维数组来存放边之间的关系,用一维数组来存放顶点的信息。所以在接下来的求解问题中我们将用到二维数组a来存放两边是否相邻,用一维数组x来存放每个顶点的颜色;x[i]=j表示第i个节点图第j中颜色。
根据矩阵我们要求出矩阵的色数K和着色方案?
1.3 问题解决
我们可以用贪心法给图着色,选择第一种颜色,以任意顶点作为开始顶点,依次考察图中的未被着色的每个顶点,如果第一个顶点可以用颜色1着色,换言之,该顶点的邻接点都还未被着色,则用颜色1为该顶点着色,当没有顶点能以这种颜色着色时,增加第二种颜色,选择颜色2和一个未被着色的顶点作为开始顶点,用第二种颜色为尽可能多的顶点着色,如果还有未着色的顶点,则选取颜色3并为尽可能多的顶点着色,依此类推。
代码实现:
package com.tuzhese; public class TestTuzhese { int n = 0; /** * 着色方法 */ public void color(){ /** * 关系图矩阵,1代表连接关系,0代表无连接关系。 */ int[][] x = new int[][]{ {1,1,1,1,0,0}, {1,1,1,1,1,0}, {1,1,1,1,0,0}, {1,1,1,1,1,0}, {0,1,0,1,1,1}, {0,0,0,0,1,1}}; /** * 着图颜色,初始颜色为0代表第一种颜色,1代表第二种颜色,以此类推。 */ int c = 0; /** * 存储着色方案 */ int[] k = new int[x.length]; /** * 为每个顶点着色 */ setColor(x, 0, c, k); } /** * * 为第i个顶点x着色, * 当x着色成功后递归向下一个顶点着色,直到所以顶点都着色完成。 * 将每一种着色方案存储并打印 * * @param x 着色矩阵 * @param i 第几个着色顶点 * @param c 当前最大颜色值 * @param k 颜色存储方案 */ public void setColor(int[][] x, int i, int c, int[] k){ boolean fc = false;//当前已有颜色值是否够用 if(i<x.length){ /** * 用现有的所有颜色依次为第i个顶点着色,判断是否存在着色冲突。 */ for (int t = 0; t <= c; t++) { /** * 颜色t不存在冲突着可以给该顶点着色,继续为下一个顶点着色。 */ if(checkColor(x, i, t, k)){ fc = true; k[i] = t; setColor(x, i+1, c, k); } } /** * 如果现有的颜色值都发生冲突,不可着色。 * 现有颜色c自增,添加一种新颜色值,并用该颜色值为第i个顶点着色,继续为下一顶点着色 */ if(!fc){ c++; k[i] = c; i++; setColor(x, i, c, k); } }else{ /** * 输出着色方案 */ n++; System.out.println("着色方案"+n+":"); for (int j = 0; j < k.length; j++) { System.out.print(k[j]+","); } System.out.println(); } } /** * * 判断现有的颜色是否可以着色,即是否存在着色冲突。 * 用颜色t给第i个顶点着色,判断该色值是否存在着色冲突, * 如果存在冲突返回false,即该颜色不可以为该顶点着色。 * 如果没有发生冲突则放回true,即该颜色可以为该顶点着色。 * * @param x 着色顶点 * @param i 第i个着色顶点 * @param t 着色值 * @param k 着色方案 * @return */ public boolean checkColor(int[][] x, int i, int t, int[] k){ for (int j = 0; j < i; j++) { /** * 着色冲突的判断条件, * 与该顶点连接的其他顶点的颜色值是否与该着色值t冲突 */ if(x[i][j] == 1 && k[j] == t){ return false; } } return true; } public static void main(String[] args) { TestTuzhese tt = new TestTuzhese(); tt.color(); } }
输出结果:
着色方案1: 0,1,2,3,0,1, 着色方案2: 0,1,2,3,0,2, 着色方案3: 0,1,2,3,0,3, 着色方案4: 0,1,2,3,2,0, 着色方案5: 0,1,2,3,2,1, 着色方案6: 0,1,2,3,2,3,
1.4 着色应用
1,学校共有n门功课需要进行期末考试,因为不少学生不止选修一门课,所以不能把一个同学选修的两门课安排在同一场次进行考试。问学期的期末考试最少需要多少场次才能完成?
• 问题处理:我们以每门功课为一个顶点,当且仅当两门功课被同一个学生选修时,在响应两个顶点之间连一条边,得到一个图G。我们将n门功课划分成k个子集U1,U2,…,UK两两子集的功课都不相同。
• 每个子集Ui(1≤i≤k)的顶点两两子集不相邻,即子集内的任意两门功课都不能被一个学生选修。能这种要求划分的子集数K必须最少,即不能划分成k-1个子集。然后我们对每个子集内的顶点涂一种颜色。
• 同色顶点对应的课程安排在同一场次考试,颜色数即为学期考试所需要的最少场次数。
发表评论
-
Java validation(java验证器实现)
2014-03-18 11:45 3641Java validation 1. java验证器 在 ... -
Memo class备注类信息
2014-03-18 09:52 813Memo Class 1. 什么是Memo Class Mem ... -
java annotation注解
2014-01-24 18:01 9161. Annotation的声明方式 An ... -
Java RMI
2013-03-28 15:12 1650Java Rmi 目录 1 JAVA RMI 1 ... -
java内部类
2013-03-19 16:25 999Java内部类 目录 1 JAVA ... -
java多线程设计模式之订单模式
2013-03-11 14:00 2623Java多线程实现订单模式: 客户端线程向服务端发起请求后, ... -
java多线程设计模式之线程池处理请求
2013-03-08 17:50 1788Java实现线程池处理请求: 客户端线程发出请求,请求存入请 ... -
java多线程设计模式之异步处理请求
2013-03-08 12:36 4489Java实现多线程异步处理请求: Java实现多线程异步处理 ... -
java多线程设计模式之读写文件模式
2013-03-07 17:56 1547Java实现多线程读写数据 ... -
java多线程设计模式之生产者与消费者
2013-03-07 11:34 1006Java实现多线程生产者与消费者: 生产者线程负责生产产品 ... -
java多线程设计模式之文件保存
2013-03-06 16:16 1549Java实现多线程保存文件:两线程去保存文件,一个保存线程定时 ... -
java多线程设计模式之队列通信
2013-03-06 13:51 2439Java实现多线程处理队列请求通信:客户端线程向请求队列中不断 ... -
Java读linux系统文件文件名乱码
2012-12-06 17:01 90751,问题描述 web应用想通过Java读取linux系统文件显 ... -
Java安全加密
2012-11-28 10:24 1925安全加密 目录 1 加密安全 1 1.1 应用的安全 1 ... -
JDK6新特性
2012-07-03 23:24 2867JDK6的新特性 JDK6的新特性之一_Desktop类 ... -
JDK7新特性
2012-07-03 15:39 3472JDK7新特性 一 JDK7新特性简介 准备 JDK7下载 ... -
JDK5新特性
2012-07-03 10:23 73JDK5.0新特性 1.自动封箱和自动解封(简单类型和封装类 ... -
java多线程
2012-06-15 15:12 1516Java多线程 目录 1 线 ... -
代理模式
2012-06-13 14:12 1321代理模式 目录 1 代理 ... -
java垃圾回收机制
2012-06-11 11:30 2531Java内存回收 目录 1 JAVA内存STACK和HE ...
相关推荐
利用模拟退火算法解决GCP图着色问题,matlab编写
算法(c++)——地图着色问题
地图四着色问题,对于相邻矩阵,利用堆栈实现地图颜色的测试,解决回溯问题
这是用C++语言写的一个关于图着色的问题。对于初学算法的人有帮助。
图着色问题(Graph Coloring Problem, GCP) 又称着色问题,是最著名的NP-完全问题之一。 这里展示可以选择中国地图和美国地图进行染色,同时可选择4-7种颜色进行染色。 采用了队列方法解决问题。
主要介绍了蚁群算法的基本思想,及其在图着色方面的应用
网上绝无仅有的东西 我因为做课程设计的原因在网上找了好久都没有连通图着色问题的程序或者报告,现在我做完了,拿出来和大家分享一下,希望能够帮助到你
一、问题描述 设计地图着色软件,对江西地图中11个地级市进行着色,要求相邻地级市使用不同的颜色,并保证使用的颜色最少。 二、基本要求 1.地图采用图型数据结构,每个地级市为一个节点,边表示对应的两个地级市...
1、设计数据结构,表示各省与各省间邻接关系 2、设计染色算法 3、根据染色算法的运行结果对地图进行染色,将染色过程制作视频,最终 染色结果呈现写在报告了,鼓励用计算机实现染色过程,也可以手工根 据染色方案...
(1) 数据结构的设计:地图可以采用图的数据结构,每个省为一个节点,边表示对应的两个省相邻。 (2) 算法设计:设计着色算法,保证邻接点不是同一种颜色。 (3) 地图数据的输入采取从文件中读取。 (4) 结果...
图着色问题(Graph Coloring Problem, GCP) 又称着色问题,是最著名的NP-完全问题之一。 模拟退火算法实现最优。
图着色问题
针对图着色对顶点划分的本质特征,提出了基于度的种群初始化方法...在此基础上,提出了图着色问题的一种新的混合遗传算法,对10个标准算例的仿真结果表明,新混合遗传算法可以获得问题高质量的解,是一种有潜力的算法。
对于图着色问题几个算法,希望对大家有帮助
cpp文件,此程序是初级中的初级,只要学过C都可以用来应付大作业,课程设计一类的
数据结构课程设计,对地图或者图的上色问题,运用了C语言,实验报告
C语言是一门通用计算机编程语言,广泛应用于底层开发。C语言的设计目标是提供一种能以简易的方式编译、处理低级存储器、产生少量的机器码
基于Matlab实现的蚁群算法结合RLF求解图着色问题源码+程序说明+超详细注释(课程作业).zip基于Matlab实现的蚁群算法结合RLF求解图着色问题源码+程序说明+超详细注释(课程作业).zip基于Matlab实现的蚁群算法结合RLF...
C语言是一门通用计算机编程语言,广泛应用于底层开发。C语言的设计目标是提供一种能以简易的方式编译、处理低级存储器、产生少量的机器码
图着色局部搜索图着色问题(Graph Coloring Problem GCP) 又称着色问题,是最著名的NP-完全问题之一。道路着色问题(Road Coloring Problem)是图论中最著名的猜想之一。数学定义:给定一个无向图G=(V E),其中V...