以基於貪婪法的房間配置演算法解決點著色問題

  • 黃 建國

Student thesis: Master's Thesis

Abstract

  在這篇論文中,我們從房間配置的角度探討與解決點著色問題。在房間配置中,點與點之間的著色情形對應到一張「旅館表(Hotel table)」,每個點就稱之為一個「顧客(Customer)」。表格的行稱為「樓層(Stair)」,一行就代表圖中一個連通子圖(Connected sub-graph)。表格的列稱為「房間(Room)」。一列代表一種顏色。圖中顏色相同的點就放在同一列。   旅館表可以看到較具體的點與點互動情形,而所使用的房間數量即是著色問題所使用的顏色數。因此如何找到最小點著色數的問題,可直接相等於如何求得最少的房間數。本文的前半段簡介點著色問題,並且討論旅館表的特性。接著以透過顧客與顧客之間的「溝通(Communication)」來盡量減少房間數完成配置。我們所提出的方法為「房間配置演算法(Room-allocation algorithm)」。其中包含了以鄰居關係順序配置房間的「基本法」、「隨機法」、「剝殼法」,以及以顧客順序配置房間的「三合院法」。前三種方法可以計算任意圖的著色解,而三合院法只能判斷是否為3 可著色。論文最後測試一些隨機產生的圖,討論並分析測試結果。   令N和M為圖G的點數量與邊數量、Δ(G)為圖G所有點中相鄰點數量最多的相鄰點數量、stepmax為隨機法中設定的最大迭代次數,則「基本法」、「隨機法」、「剝殼法」的時間複雜度依序為O(M)+O(Δ(G))、O(M)+O(stepmax·(Δ(G))^2)、O(M)+O((Δ(G))^3),對於二分圖保證能得到兩種顏色的著色,但對於最小著色數大於2的圖形,著色數有時比貪婪法好,有時則非;「三合院法」的時間複雜度為O(N^2)至O(N^3·2^N),根據Ratio=MN和G的最小著色數的不同決定複雜度,當圖的最小著色數大於3,「三合院法」只需要小於O(N^2) 的複雜度判斷G不為3可著色;令min(TQH)為三合院法的最小分界值、max(TQH)為三合院法的最大分界值,當圖的最小著色數為3且Ratio <min(TQH),則「三合院法」需要O(N^3)的複雜度;當圖的最小著色數為3且Ratio>max(TQH),則「三合院法」需要O(N^2)的複雜度;當圖的最小著色數為3且min(TQH)?Ratio?max(TQH),則「三合院法」需要O(N^3·2^N)的複雜度。當圖的最小著色數為2,「三合院法」會得到一個不大於3的著色解,但不保證得到著色數為2的解,當圖的最小著色數為3,「三合院法」保證得到一個著色數為3的解。
Date of Award2017 Jul 28
Original languageChinese
SupervisorYu-Chen Shu (Supervisor)

Cite this

以基於貪婪法的房間配置演算法解決點著色問題
建國, 黃. (Author). 2017 Jul 28

Student thesis: Master's Thesis