節點塗色問題為一傳統網路問題，其問題在給定一不具方向性網路，以最 小的顏色數量塗滿所有節點，但有節線相連的節點對則不可塗同樣的顏色。節點 塗色問題在數學上可歸類為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 colors that color all nodes, where there is no node pair with the same color. NCP has been proven NP-hard in terms of optimization. When problem sizes become large, it is difficult to exactly solve NCP. Therefore, most researchers in the past developed heuristic algorithms, usually using greedy approaches or local improvements, to solve NCP. Some of meta-heuristics, such as tabu search, simulated annealing, neural network and genetic algorithm, have been applied to solve NCP. This research attempts to combine design techniques of traditional algorithms and newly meta-heuristics, together with a new concept of randomly changing search direction, to develop efficient solution algorithms for NCP. Computational tests show that our solution algorithms are superior to Aho's greedy algorithm, Dsatur algorithm and simulated annealing algorithm in terms of computational efficiency and solution quality.