地图着色算法

㈠ java地图着色问题

建议网络搜索地图着色问题，这是一个数学问题，印象中应该是个图的问题，所以你要先会用数学方式解决，其次才是用程序代码描述出来。

㈡ 地图着色问题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]);
}

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

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

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

㈣ c# 地图四染色

很麻烦的算法题，分有点少........

啧，分还是少........算了，给你写个简单的把

using System;
using System.Collections.Generic;

namespace 四色猜想
{
public class FourColor
{
public static void Run(int aeraNumeric)
{
//为了偷懒，没有使用二维矩阵而是直接用了栈，即X的最大相邻数为2即X-1和X+1，实际上2个颜色就够用了....
//实例化栈
Stack<Aera> AeraStack = new Stack<Aera>(aeraNumeric);
//演示算法，使用随机颜色
Random RandomColor = new System.Random();

for (int i = 0; i < aeraNumeric; i++)
{
//初始化Aera并入栈
Aera MyAera = new Aera((i + 1).ToString(), (Publicenum.FourColor)(RandomColor.Next(4)));
//入栈
if (AeraStack.Count == 0)
{
AeraStack.Push(MyAera);
continue;
}
Aera TestAera = AeraStack.Peek();
if (TestAera.AeraColor == MyAera.AeraColor)
{
int j = 0;
while (j < 5)
{
if (j == 4)
{
throw new InvalidOperationException("超出4色范围!");
}
Publicenum.FourColor TestColor = (Publicenum.FourColor)j;
if (TestAera.AeraColor == TestColor)
{
j++;
continue;
}
else
{
MyAera.AeraColor = TestColor;
break;
}

}
}
AeraStack.Push(MyAera);
}

//输出结果
while (AeraStack.Count != 0)
{
Aera OutputAera = AeraStack.Pop();
Console.WriteLine("Name:{0},Color:{1}", OutputAera.AeraName, OutputAera.AeraColor);
}
Console.ReadLine();
}
}

public class Aera
{
public string AeraName { get; set; }
public Publicenum.FourColor AeraColor { get; set; }

public Aera(string aeraName, Publicenum.FourColor aeraColor)
{
AeraName = aeraName;
AeraColor = aeraColor;
}
}

public class Publicenum
{
public enum FourColor
{
A, B, C, D
}
}
}

控制台程序，调用时输入区域个数如 FourColor.Run(73);

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

道路着色问题（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过程和赋值过程，以及各过程之间的迭代，在基于图着色的寄存器分配方法中具有广泛的影响。

㈥ C++给中国地图着色，用四种颜色时如何采用不同的方案怎样计算地图着色效率

这是图的遍历，可以先把各省抽象为N个结点，制作为无向图数据结构，采用广度遍历，考虑从最边缘的省份起着色。使用递归算法。
你学过数据结构吗？不学过也不好说。