图着色算法

❶ 用c#编码一个图的m-着色问题

给出一个图的m-着色的程序段,回溯法:
/* 图的邻接矩阵Graph[n,n]表示无向连通图G,
1,2,3,..m代表不同的颜色
顶点i所着色用x[i]表示,初始值都赋为0
*/
void NextValue(int k)
{
int j, flag;
do{
x[k] = (x[k]+1) % (m + 1)//分配给x[k]一种新的颜色
if (x[k] == 0)
return; //x[k]的颜色已用完
flag = 1; //x[k]是否可用的标记
for (j = 0; j < n; j++)
if (Graph[k,j] == 1 && x[k] == x[j]){
flag = 0; //x[k]不可用
break;
}
while (flag);
}
void MColoring(int k)
{
while (x[k] < m){ //产生x[k]的合理分配
NextValue(k); //找x[k]的一个合理分配
if (x[k] == 0)
return; //无解,结束调用
if (k == n) { //着完n个顶点,找到完整着色法,输出
Output(x,k) //输出当前解
else
MColoring(k+1)
}
}

/*
递归算法：
void Coloring(区域 n)
1. 令颜色集ClrSet={ 没有被区域n的邻居区域使用的颜色 }.
2. 如果ClrSet是空集，返回.
3. 对ClrSet中的每种颜色c，作循环：
3.1 为区域n着色c。
3.2 如果所有区域都已着色(n是最后一个区域)，那么显示/保存着色结果.
3.3 否则对下一个尚未着色的区域(n+1)，调用Coloring(n+1).
4. 把区域n变为没有着色的区域.
--------------------------------------------------------
*/
template<int node_count = 8>
class CColoring
{
private:
typedef int node_type;
typedef int color_type;
typedef std::set<node_type> node_set;
typedef std::vector<color_type> color_array;

public:
void operator()(const int _Matrix[node_count][node_count])
{
matrix = _Matrix;

colors_of_nodes.resize(node_count, 0);

total_count = 0;

coloring(0);
}

private:
void coloring(node_type n)
{
// 颜色的使用情况
std::vector<bool> used_colors;

node_type m;
color_type c;

// 初始化颜色的使用情况
used_colors.resize(color_count, false);

// 遍历每个与区域n相邻的区域m
for(m = 0; m < node_count; ++m)
{
if(matrix[n][m])
{
// 获取m的颜色
c = colors_of_nodes[m];
// m已着色
if(c != 0)
used_colors[c] = true;
}
}

// 遍历每个未被n的邻居使用的颜色c
for(c = 1; c < color_count; ++c)
{
if(!used_colors[c])
{
// 为n着色c
colors_of_nodes[n] = c;

// 着色完毕
if(n >= node_count - 1)
{
++total_count;

// 输出结果
_tprintf(_T("---------------------\n"));
_tprintf(_T("Method %d:\n"), total_count);
for(m = 0; m < node_count; ++m)
{
_tprintf(_T("node: %d, color: %d\n"), m, colors_of_nodes[m]);
}
}
// 还有区域没有着色
else
{
// 为下一个未着色的区域，调用coloring()
coloring(n + 1);
}
}
}

// 将n设置为没有着色的区域
colors_of_nodes[n] = 0;
}

// 0表示无色，1-4表示4种不同颜色
static const int color_count = 5;
// 邻接矩阵
const int (* matrix)[node_count];
// 各区域对应的颜色
color_array colors_of_nodes;
// 总的着色方案数
int total_count;
};

void main()
{
int Matrix[4][4] =
{
{ 0, 1, 0, 0 },
{ 1, 0, 0, 0 },
{ 0, 0, 0, 1 },
{ 0, 0, 1, 0 },
};

CColoring<4> coloring;
coloring(Matrix);
}

❷ “四色定理”在实际中有什么应用

四色定理是图的着色问题的一个结果。图的着色本质是给图中的顶点贴标签（labeling），但是要满足一定的条件。“色”只是一种标签。

四色定理的描述虽然提到了地图，但是地图绘制并不需要四色定理：他只要着色，不需要用最少的颜色。实际画地图时一般不用四种颜色。

着色问题的应用，主要排程和分配问题上。
比如我有几个任务，每个任务都需要一天。而我知道其中几样任务是冲突的，不能安排在同一天完成。现在我希望四天完成。这就是四色问题了：所用的图以任务为顶点，冲突的任务间连边，用日期做颜色，对图着色。

再比如我有一些员工，我希望把他们分成四个小组。但是我知道其中几个员工互相之间有矛盾，不能安排在同一组。那么这又是四色问题：所用的图以员工为顶点为，矛盾的员工间连边，用组做颜色，对图着色。

四色定理说：如果上面提到的图是平面图（有高效算法判定），那么可能四天完成／可能分成四组。

❸ 求高手帮忙做一套算法分析的题目。做好之后再加100。

如何选择排序、矩阵相乘、树和图算法的时间复杂性计量单位？
排序：排序的循环次数（或递归次数）。
矩阵相乘：做实数乘法的次数。
树：搜索的次数。
图：同树。
算法有几种基本结构？各种结构的时间复杂度的计算规则？
3种
顺序结构：T(n)=O(c)
选择结构：T(n)=O(c)
循环结构：T(n)=O(n)
最坏情况下的时间复杂性和平均情况下的时间复杂性的定义？
在规模n的全部输入中，可以找寻执行一个算法所需的最大时间资源的量，这个量称为对规模n的输入，算法的最坏情况时间复杂性。
对规模都为n的一些有限输入集，执行算法所需的平均时间资源的量称为平均情况下的时间复杂性。
为什么选择时间复杂度的渐进性态评价算法？
因为在规模较小的时候无法客观体现一个算法的效率。
解释f(n)=O(g(n))的意义。
若f(n)和g(n)是定义在正整数集合上的 两个函数，则f(n)=O(g(n))表示存在正的常数C和n0 ,使得当n≥n0时满足0≤f(n)≤C*g(n)。
简述之就是这两个函数当整型自变量n趋向于无穷大时，两者的比值是一个不等于0的常数。
有效算法和无效算法的划分原则？
区分在于问题是否能够精确求解。
用分治法设计算法有什么好处？为什么描述分治算法需要使用递归技术？
分治法可以将问题分为许规模更小的子问题，这些子问题相互独立且与原问题相同。使用递归技术，虽然一些简单的循环结构替代之，但是复杂的问题，比如二阶递归是无法替代的。
归并排序算法和快速排序算法划分子问题和合并子问题的解的方法各是是怎样的？
归并排序算法：
划分子问题：每次分成2个大小大致相同的子集和
合并子问题：将2个排好序的子数组合并为一个数组
快速排序算法：对输入的子数组a[p:r]
划分子问题：划分为a[p:q-1],a[q]和a[q+1:r]使a[p:q-1]任意元素小于a[q]，a[q+1:r] 任意元素大于a[q]
合并子问题：不需要（因为划分过程就已经排序完成了）
简述二分检索（折半查找）算法为什么比顺序查找的效率高？
对于二分搜索 最坏情况为O(logn)时间完成
而顺序查找 需要O(n)次比较
显然二分搜索效率高
贪心法的核心是什么？
贪心算法是通过一系列选择得到问题的解，它所作出的选择都是当前状态下的最佳选择。
背包问题的目标函数是什么？背包问题贪心算法的最优量度是什么？算法是否获得最优解？ 用贪心算法解0/1背包问题是否可获得最优解？
Max=∑Vi*Xi (V是价值X取1，0表示装入或不装)
每次选取单位重量价值最高的
不一定是最优解

情况不妙啊 LZ还要继续否。。。
早知发邮件了。。。

❹ 图着色问题的路线着色问题

道路着色问题（Road Coloring Problem）是图论中最着名的猜想之一。通俗的说，这个猜想认为，可以绘制一张“万能地图”，指导人们到达某一目的地，不管他们原来在什么位置。这个猜想最近被以色列数学家艾夫拉汉· 特雷特曼(Avraham Trahtman)在2007年9月证明。
举个例子。在维基网给出的图例中，如果按图中所示方式将16条边着色，那么不管你从哪里出发，按照“蓝红红蓝红红蓝红红”的路线走9步，你最后一定达到黄色顶点。路线着色定理就是说在满足一定条件的有向图中，这样的着色方式一定存在。严格的数学描述如下。我们首先来定义同步着色。G是一个有限有向图并且G的每个顶点的出度都是k。G的一个同步着色满足以下两个条件：1)G的每个顶点有且只有一条出边被染成了1到k之间的某种颜色；2)G的每个顶点都对应一种走法，不管你从哪里出发，按该走法走，最后都结束在该顶点。有向图G存在同步着色的必要条件是G是强连通而且是非周期的。一个有向图是非周期的是指该图中包含的所有环的长度没有大于1的公约数。路线着色定理这两个条件(强连通和是非周期)也是充分的。也就是说,有向图G存在同步着色当且仅当G是强连通而且是非周期的。
特雷特曼在数学上的这一成果极为令人瞩目，英国《独立报》为此事专门发表了一篇题为“身无分文的移民成了数学超级明星”的文章，给予了高度的评价。
以色列人也为特雷特曼取得的成就感到无比的骄傲。特拉维夫电视台中断了正常的节目播放，以第一时间发布了这一重大消息，连中东其他国家的主流媒体也作了大篇幅的相关报道。
得知特雷特曼解决这一难题的消息后，多年从事路线着色问题研究的加拿大数学家乔尔·弗里德曼说，“路线着色问题的解决令数学共同体非常兴奋。”读过特雷特曼论文的中国数学家和语言学家周海中教授认为，特雷特曼的数学知识非常渊博，解题方法十分巧妙，这一谜题得到破解，无疑是数学史上的一个华彩乐章。 算法描述：color[n]存储n个顶点的着色方案，可以选择的颜色为1到m。
当t=1时，对当前第t个顶点开始着色：若t>n，则已求得一个解，输出着色方案即可。否则，依次对顶点t着色1-m， 若t与所有其它相邻顶点无颜色冲突，则继续为下一顶点着色；否则，回溯，测试下一颜色。 #include<stdio.h>intcolor[100];boolok(intk,intc[][100])//判断顶点k的着色是否发生冲突{inti,j;for(i=1;i<k;i++){if(c[k][i]==1&&color[i]==color[k])returnfalse;}returntrue;}voidgraphcolor(intn,intm,intc[][100]){inti,k;for(i=1;i<=n;i++)color[i]=0;k=1;while(k>=1){color[k]=color[k]+1;while(color[k]<=m)if(ok(k,c))break;elsecolor[k]=color[k]+1;//搜索下一个颜色if(color[k]<=m&&k==n){for(i=1;i<=n;i++)printf(%d,color[i]);printf( );}elseif(color[k]<=m&&k<n)k=k+1;//处理下一个顶点else{color[k]=0;k=k-1;//回溯}}}voidmain(){inti,j,n,m;intc[100][100];//存储n个顶点的无向图的数组printf(输入顶点数n和着色数m: );scanf(%d%d,&n,&m);printf(输入无向图的邻接矩阵: );for(i=1;i<=n;i++)for(j=1;j<=n;j++)scanf(%d,&c[i][j]);printf(着色所有可能的解: );graphcolor(n,m,c);} 利用相交图（interference graph）来表示程序变量的生命期是否相交，将寄存器分配给变量的问题，可以近似地看成是给相交图着色：相交图中，相交的节点不能着同一颜色；每一种颜色对应一个寄存器。Chaitin等人最早提出了基于图着色的寄存器分配方法其着色思路采用了Kempe的着色方法，即，任意一个邻居节点数目少于k的节点，都能够被k着色。判断一个图是否能够被k(k>=3)种颜色着色，即k着色问题，被Karp证明是一个NP-complete问题。
但是，寄存器分配不仅仅是图着色的问题。当寄存器数目不足以分配某些变量时，就必须将这些变量溢出到内存中，该过程成为spill。最小化溢出代价的问题，也是一个NP-complete问题。如果简化该问题——假设所有溢出代价相等，那么最小化溢出代价的问题，等价于k着色问题，仍然是NP-complete问题。
此外，如果两个变量的生命期仅仅因为出现在同一个拷贝指令中而相邻，那么，通过将这两个变量分配到同一个寄存器，就可以消除该拷贝指令，成为coalescing。这个方向的努力在Chaitin的文章以后的1/4个世纪，成为推动寄存器分配的主要动力之一，涌现出了包括aggressive coalescing,conservative coalescing和optimistic coalescing。但是，将两个变量分配到同一个寄存器，等价于将这两个变量合并成同一个变量，生命期合并，因而会加剧相交图的聚簇现象，降低相交图的可着色性。Bouchez等人证明了目前的coalescing问题都是NP-complete的。
为了降低相交图的聚簇现象，提高相交图的可着色性，可以通过将变量拷贝给一个临时变量，并将以后对该变量的使用替换成对该临时变量的使用，从而将一个变量的生命期分解成两个变量的生命期，称为live range splitting。显然，这是一个与coalescing的作用相反的过程。Bouchez等人考虑了该方法的复杂度。
此外，寄存器分配还需要考虑寄存器别名(aliasing)和预着色(pre-coloring)的问题。寄存器别名是指，在某些体系结构中，一个寄存器的赋值可能会影响到另外一个寄存器。比如，在x86中，对AX寄存器的赋值，会影响AL和AH寄存器。预着色是指，某些变量必须被分配到特定的寄存器。比如，许多体系结构会采用特定寄存器来传递函数参数。
George和Appel发展了Chaitin的算法，更好地考虑了coalescing过程和赋值过程，以及各过程之间的迭代，在基于图着色的寄存器分配方法中具有广泛的影响。

❺ 急！利用5种不同的算法，为中国地图每个省着色，要求相邻的省份颜色不同，所用的颜色最少！！

这是根据数学史上着名的四色问题，每幅地图都可以用四种颜色着色，使得有共同代表地形的不同！ 颜色不代表什么，主要是为了区分方便，如果用同一种

❻ 地图着色问题C/C++

从一个省开始，给它涂上任意一种颜色1，遍历它旁边的省份，涂上与已经涂色并于他相邻的省份不同的颜色就行了。
理论上4种颜色就够了.地图的四色问题嘛!
可能会有多组解。用递归（dfs)就可以输出所有解了。

地图着色算法C语言源代码
前面我写了一个地图着色（即四色原理）的C源代码。

写完以后想了一下，感觉还不完善，因为从实际操作的角度来考虑，四种可用的颜色放在旁边，不同的人可能会有不同的选择顺序，另外，不同的人可能会选择不同的城市作为着色的起点，而当时的程序没有考虑这个问题。于是，把程序修改为下面的样子，还请同行分析并指出代码中的不足之处：

＃i nclude <stdio.h>
#define N 21
int allcolor[4];/*可用的颜色*/

int ok(int metro[N][N],int r_color[N],int current)
{/*ok函数和下面的go函数和原来的一样,保留用来比较两种算法*/
int j;
for(j=1;j<current;j++)
if(metro[current][j]==1&&r_color[j]==r_color[current])
return 0;
return 1;
}

void go(int metro[N][N],int r_color[N],int sum,int current)
{
int i;
if(current<=sum)
for(i=1;i<=4;i++)
{
r_color[current]=i;
if(ok(metro,r_color,current))
{
go(metro,r_color,sum,current+1);
return;
}
}
}

void color(int metro[N][N],int r_color[N],int sum,int start)
{
int i,j,k;
r_color[start]=allcolor[0];
for(i=start+1;i!=start;i=(i+1)%(sum+1))/*把所有编号看作一个环*/
if(i==0)/*城市号从1开始编号,故跳过0编号*/
continue;
else
for(j=0;j<4;j++)
{
r_color[i]=allcolor[j];/*选取下一种颜色,根据allcolor中颜色顺序不同，结果不同*/
for(k=1;k<i;k++)/*检查是否有冲突，感觉还可以改进，如使用禁忌搜索法*/
if(metro[i][k]==1&&r_color[k]==r_color[i])
break;
if(k>=i)
break;
}
}

void main()
{
int r_color[N]={0};
int t_color[N]={0};
int i;
int start;/*着色的起点*/
int metro[N][N]={{0},
{0,1,1,1,1,1,1},
{0,1,1,1,1},
{0,1,1,1,0,0,1},
{0,1,1,0,1,1},
{0,1,0,0,1,1,1,0,0,1,0,0,0,0,0,0,1},
{0,1,0,1,0,1,1,1,1,1},
{0,0,0,0,0,0,1,1,1},
{0,0,0,0,0,0,1,1,1,1,0,0,1},
{0,0,0,0,0,1,1,0,1,1,0,0,1,1,1,0,1},
{0,0,0,0,0,0,0,0,0,0,1,1,0,1,0,1,0,0,0,1},
{0,0,0,0,0,0,0,0,0,0,1,1,1,1,0,0,0,0,0,1},
{0,0,0,0,0,0,0,0,1,1,0,1,1,1,0,0,0,0,0,1,1},
{0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1},
{0,0,0,0,0,0,0,0,0,1,0,0,0,1,1,1,1},
{0,0,0,0,0,0,0,0,0,0,1,0,0,1,1,1,1,1,0,1},
{0,0,0,0,1,0,0,0,1,0,0,0,0,1,1,1,1},
{0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1},
{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1},
{0,0,0,0,0,0,0,0,0,0,1,1,1,0,0,1,0,0,1,1,1},
{0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1,1}};
allcolor[0]=1;allcolor[1]=2;allcolor[2]=3;allcolor[3]=4;/*选色顺序，顺序不同，结果不同*/
start=1;
/* clrscr();*/
printf("\nAll color is:\n");
for(i=0;i<4;i++)/*当前选色顺序*/
printf("%d ",allcolor[i]);
go(metro,r_color,20,1);
printf("\nFirst method:\n");
for(i=1;i<=20;i++)
printf("%3d",r_color[i]);
color(metro,t_color,20,start);
printf("\nSecond method:\n");
printf("\nAnd the start metro is:%d\n",start);
for(i=1;i<=20;i++)
printf("%3d",t_color[i]);
}

说是人性化着色，其实还有一个问题没有考虑，那就是操作员跳跃式着色，就像大家玩“扫雷”游戏一样。其实也容易实现，可以像定义选色顺序一样定义着色顺序。

❼ 组合优化问题

从广义上讲，组合优化问题是涉及从有限的一组对象中找到"最佳"对象的问题 。“最佳”是通过给定的评估函数来测量的，该函数将对象映射到某个分数或者成本，目标是找到最高评估分数和最低成本的对象。组合优化往往涉及排序、分类、筛选等问题。以离散的COP问题来讲，目标就是从所有可行解中寻找一个集合、一个排列或者一个图。

旅行商问题 （Traveling Salesman Problem - TSP)
加工调度问题 （Scheling Problem，如Flow-Shop，Job-Shop）
0-1背包问题 （Knapsack Problem）
装箱问题 （Bin Packing Problem）
图着色问题 （Graph Coloring Problem）
聚类问题 （Clustering Problem）
着名的旅行商问题（TSP）：假设有一个旅行商人要拜访n个城市，他必须选择所要走的路径，路径的限制是每个城市只能拜访一次，而且最后要回到原来出发的城市。路径的选择目标是要求得的路径长度为所有路径之中的最小值。TSP是一个典型的组合优化问题，且是一个NP完全难题，关于NP的这个概念本文就不做详细介绍了，但简单的说就是：TSP问题目前尚不能找到一个多项式时间复杂度的算法来求解。例如，下图显示了美国所有州所在城市的最佳旅游：

对项目的想法 ：
BIOS配置寻优也可以理解为组合优化问题，是一个NP-hard问题，具有高维的离散动作空间。

参考 组合优化问题求解算法思路的整理

贪婪算法、局部搜索算法、松弛算法、动态规划法 等都可用于构建近似算法求解。

启发式算法可分为传统启发式算法和元启发式算法，传统启发式算法包括 构造性方法、局部搜索算法、松弛方法、解空间缩减算法等

元启发式算法包括 禁忌搜索算法、模拟退火算法、遗传算法、蚁群算法、粒子群算 法、人工神经网络等 。

参考 相关资料汇总与点评部分

❽ 图的M着色问题，期望大师给完整的算法解释包括程序，用Pascal语言

program Exam38; //程序名

const n=7; //定义一个常量 n 值为7

var a,b,c,t: integer; //声明四个整形变量

Begin //程序入口，开始

t:=0; //给t赋值，使t为0

for a:=1 to n do //以下语句执行n次，即7次

for b:=1 to n do //以下语句执行n次，即7次，因为上面要求循环7次，所以实际是49次

for c:=1 to n do //以下语句执行n次，即7次，因为上面要求循环49次，所以下面的语句一共执行了343次

if (a-b) * (b-c) * (a-c) < >0 then //如果(a-b) * (b-c) * (a-c)满足不等于零这个条件，就执行一对begin 和 end 之间的代码

Begin //上述条件满足，执行

inc (t);// t增加1

writeln (a:3, b:3, c:3) //使a为3，b为3，c为3？？这句不太明白

End; //条件部分结束

writeln ( total:, t :5); //

readln //输入一个字符

End.//程序结束

❾ 图的着色4个顶点 给了3种颜色 如何给4个顶点着色 使之有连边关系的顶点颜色不同有多少种着色方法 编程解决

设计说明：
1 四个顶点用 0,1,2，3表示，三种颜色用A，B，C表示。
2 输出结果 0 -- ABAC ，表示 从0 顶点向1,2,3 方向着色方案为0-A，1-B，2-A，3-C。有连边 关系但顶点不同颜色。
3 用 char c[4][5]={{'A','B','A','C','\0'},{'B','A','B','C','\0'},{'C','A','C','B','\0'}};
先给出连边不同色三种基本方案，用以简化问题。
4 用三重循环分别模拟确定第一点、输出方案、改变着色方案三个事件。
5 用
t=c[i][i];c[i][i]=c[i][(i+1)%4];c[i][(i+1)%4]=c[i][(i+2)%4];c[i][(i+2)%4]=c[i][(i+3)%4];c[i][(i+3)%4]=t;
实现 ABAC-->BACA 转换，巧妙地解决了‘连边不同色’的算法难题。
程序如下：
#include <stdio.h>
main(void)
{
int i,j,k,n=0;
char c[4][5]={{'A','B','A','C','\0'},{'B','A','B','C','\0'},{'C','A','C','B','\0'}};
char t;
for(i=0;i<3;i++)
for(j=0;j<4;j++)
{
for(k=0;k<4;k++)
{ printf("%d -- %s\t",k,c[i]); /*(k+3)%4,c[(k+3)%4]);*/
n++; }
printf("\n");
t=c[i][i];c[i][i]=c[i][(i+1)%4];c[i][(i+1)%4]=c[i][(i+2)%4];c[i][(i+2)%4]=c[i][(i+3)%4];c[i][(i+3)%4]=t;
}
printf("\n total = %d",n);
getchar();
}