地圖著色演算法

㈠ 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個結點，製作為無向圖數據結構，採用廣度遍歷，考慮從最邊緣的省份起著色。使用遞歸演算法。
你學過數據結構嗎？不學過也不好說。