Embedded Files
今天的任務是由一個故事衍生而來的，請大家幫助一個地圖繪製師，因為他非常貧困，無法負擔太多顏料的費用，他必須為地圖中所有國家上色，每個國家上的顏色不重要，只要相鄰的國家不同顏色就可以了。
問題練習
問題練習
挑戰題目：
挑戰題目：
請設計一張需要使用五種顏色來完成的地圖。
這個任務在說什麼？
這個任務在說什麼？
地圖著色問題屬於圖形著色問題(graph coloring)的一種類別。
上一節最小生成樹是討論邊(edge)的最小總長度，這一節是討論相鄰節點(node)間不同顏色的最小值。
解決著色問題所需的電腦時間與圖形大小成指數性成長，若有n個國家就有4^n種組合，即使電腦也要花很多時間來算。
真實生活中有很多問題往往無法很快很容易的找到最佳解，因此找到非完美的接近最佳解是可以接受的。
Report abuse