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