圖著色演算法
❶ 用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();
}