節點塗色問題求解演算法之研究

An AIgorithm for the Node Coloring Problem

節點塗色問題為一傳統網路問題，其問題在給定一不具方向性網路，以最小的顏色數量塗滿所有節點，但有節線相連的節點對則不可塗同樣的顏色。節點塗色問題在數學上可歸類為NP-hard的問題，其最佳化的求解時間，隨問題規模的增大可能成指數的增加。由於在面臨大型問題時，甚難保證可求得最佳解，因此學界從以前至今大都發展啟發解以求解實際的大型問題。至於以往大都以貪婪方式、局部搜尋改善方式等設計啟發解，近來則有利用新近Meta-heuristics中之禁制搜尋法、模擬降溫法、類神經網路與遺傳演算法求解。本研究融合傳統與新近啟發解法，發展有效的求解演算法。其做法首先產生一較佳之初始解。之後，再融合改良傳統啟發解及新近meta-heuristics中部分的設計原理，建立一新式隨機變動搜尋方向之啟發解法，以求解節點塗色問題。為測試演算法的績效，本研究以隨機方式產生測試網路，並以固定及隨機變動方向式區域搜尋法，與三種解法作一測試比較。測試結果顯示，針對本研究設計的隨機網路而言，本研究發展的演算法無論在求解效率及品質上，均較Aho貪婪法、Dsatur algorithm及模擬降溫法等為佳。

The node coloring problem (NCP) is a traditional network problem.Given an undirected network, NCP aims to find a set of minimum number of colorsthat color all nodes, where there is no node pair with the same color. NCP hasbeen proven NP-hard in terms of optimization. When problem sizes become large,it is difficult to exactly solve NCP. Therefore, most researchers in the pastdeveloped heuristic algorithms, usually using greedy approaches or localimprovements, to solve NCP. Some of meta-heuristics, such as tabu search,simulated annealing, neural network and genetic algorithm, have been applied tosolve NCP. This research attempts to combine design techniques of traditionalalgorithms and newly meta-heuristics, together with a new concept of randomlychanging search direction, to develop efficient solution algorithms for NCP.Computational tests show that our solution algorithms are superior to Aho'sgreedy algorithm, Dsatur algorithm and simulated annealing algorithm in terms ofcomputational efficiency and solution quality.