南開大學(xué)計算機(jī)算法設(shè)計與分析

1、ABC每個盤子有三個位置,n個共有3n 共有共有 13條路線：條路線：ab , ac , adba , bc , bdda , db , dcea , eb , ec , ed1.1.3 圖著色問題 已知：已知：n點無向圖點無向圖G = , |V| = n 。求：G的最小色數(shù)的最小色數(shù)(color number)k，使得用，使得用k種顏色對種顏色對G的的頂點著色，可令任二相鄰頂點著色不同。頂點著色，可令任二相鄰頂點著色不同。 地圖著色問題，交通信號燈問題都可以歸結(jié)為圖的頂點著色問題地圖著色問題，交通信號燈問題都可以歸結(jié)為圖的頂點著色問題無向圖頂點著色問無向圖頂點著色問題：題：頂點，邊頂點，邊最

2、小色數(shù)最小色數(shù)k k地圖著色問題：地圖著色問題：國家，相鄰國家，相鄰關(guān)系關(guān)系最小色數(shù)最小色數(shù)k k交通信號燈問題：交通信號燈問題： 路線，交叉路線，交叉關(guān)系關(guān)系最小相位（組）最小相位（組）數(shù)數(shù)k k2.圖著色圖著色(Graph Coloring）問題）問題 圖著色問題圖著色問題是一個經(jīng)典的組合算法問題，源于地圖是一個經(jīng)典的組合算法問題，源于地圖著色問題。著色問題。 在繪制地圖時，總是要求相鄰的國家著上不同的在繪制地圖時，總是要求相鄰的國家著上不同的顏色以示區(qū)別。顏色以示區(qū)別。1852年一位英國大學(xué)生古德里年一位英國大學(xué)生古德里（F.Guthrie）提出了一個猜測：為了給任一個平面）提出了一個猜

3、測：為了給任一個平面地圖著色，并使任何有公共邊界的區(qū)域顏色不同，地圖著色，并使任何有公共邊界的區(qū)域顏色不同，至多需要四種顏色。這就是至多需要四種顏色。這就是四色問題四色問題，又稱，又稱四色猜四色猜想想。古德里僅僅是提出了這個猜想，他和他的老師。古德里僅僅是提出了這個猜想，他和他的老師未能證明。未能證明。圖著色圖著色(Graph Coloring）問題）問題 二十幾年后的二十幾年后的1878年，著名數(shù)學(xué)家凱萊（年，著名數(shù)學(xué)家凱萊（A.Kayley）發(fā)表了一篇發(fā)表了一篇“論地圖著色論地圖著色”的文章，雖然仍沒有解決這的文章，雖然仍沒有解決這個問題，卻掀起了四色猜想的研究熱。個問題，卻掀起了四色猜想

4、的研究熱。 經(jīng)過一百年的探索，美國伊利諾大學(xué)的哈肯（經(jīng)過一百年的探索，美國伊利諾大學(xué)的哈肯（W.Haken）與阿佩爾（與阿佩爾（K.Appel）通過改進(jìn)算法，借助計算機(jī)（共）通過改進(jìn)算法，借助計算機(jī)（共用了用了1200個機(jī)時）終于在個機(jī)時）終于在1976年完成了四色猜想的證年完成了四色猜想的證明。當(dāng)?shù)氐泥]局在寄出的信上除了通常的郵戳明。當(dāng)?shù)氐泥]局在寄出的信上除了通常的郵戳(postmark)外，還要加蓋外，還要加蓋“四色是足夠的四色是足夠的”一句話以一句話以表示自豪。表示自豪。. 圖著色圖著色(Graph Coloring）問題）問題 當(dāng)把地圖當(dāng)把地圖(Map)上的一個國家與圖上的一個國家與圖

5、(Graph)上的一個頂上的一個頂點對應(yīng)，兩個國家的相鄰關(guān)系對應(yīng)于無向圖上的邊，點對應(yīng)，兩個國家的相鄰關(guān)系對應(yīng)于無向圖上的邊，于是，上面關(guān)于地圖的于是，上面關(guān)于地圖的“四色問題四色問題”實際上是無向圖實際上是無向圖的頂點著色問題的特例。的頂點著色問題的特例。 無向圖的頂點無向圖的頂點著色問題是一個有名的著色問題是一個有名的NP完全問題完全問題，這，這類問題屬于類問題屬于“計算機(jī)難解計算機(jī)難解”問題，關(guān)于著色問題算法問題，關(guān)于著色問題算法的研究已有許多學(xué)者的大量成果。的研究已有許多學(xué)者的大量成果。 c例如例如Fig.1.3中的中的5點無向圖，用貪點無向圖，用貪心法著色需要用紅心法著色需要用紅(R

6、)、黃、黃(Y)、藍(lán)、藍(lán)(B)三種顏色，但實際上，這不是三種顏色，但實際上，這不是該圖的最小色數(shù)，顯然，兩種顏該圖的最小色數(shù)，顯然，兩種顏色已可滿足要求。即：頂點色已可滿足要求。即：頂點1、3、4著紅色，頂點著紅色，頂點2、5著黃色。著黃色。(不同不同編號順序編號順序) cv3.算法設(shè)計討論 算法的研究與許多實際應(yīng)用問題直接相關(guān)，它不僅是個理論問題； 一些典型的算法問題的研究，如著色問題、旅行商問題、背包問題等等，常常在應(yīng)用算法的設(shè)計中發(fā)揮作用； 用來解一個問題，可以有多種不同的算法，它們的效果可能差別很大，如何設(shè)計有效的算法是算法理論的主要目標(biāo)。 04710904223048760W抽象級抽

7、象級更新速度更新速度算法算法程序設(shè)計方法程序設(shè)計方法程序設(shè)計語言程序設(shè)計語言編程工具編程工具A B CA B C算法B有條件優(yōu)于算法A：在實際應(yīng)用中問題規(guī)模是給定的 nDI) I ( t ) I (P)n(A1)I(PnDI n)q1()1n(2qn)q1(inq)I ( t )I (P)n(An1i1n1iii 1k, 2)2n(T)2n(T1k,10k,0)n(T22n32222)2(T22)2)4n(T2(22)2n(T2)n(Tk1k1k1ii1k K=log2n 22/n32/n)1n()1n(SS)n(T51ii61ii nnk1ii )n(g)n(TC)n(Tk1iii )n(g

8、)n(TC)n(Tk1iii 1a)n(logO1a)n(O)n(Tbalogb)n(logO)n(logOb ba)n(Oba)nlogn(Oba)n(O)n(Talogb)n(O)n(O)n(T2log2 第一章完第一章完int GColor(E)int i,j,k =1,colorn+1;color1 =1;for (i =2; i =n; i+) colori =0;/2開始所有點為未著色開始所有點為未著色 do /用色用色k為盡可能多點著色為盡可能多點著色 for (i =2; i 0) continue; /該點已著色則下一點該點已著色則下一點 for (j =1; j i; j+) if (colorj=k)&(E) break;/如果有點著此色如果有點著此色 且與點且與點i相鄰相鄰,則則i不能著色不能著色k if (j = i) colori =k; j =2;while (color