查詢結果分析
來源資料
相關文獻
- 節點塗色問題求解演算法之研究
- Solving the Capacitated Clustering Problem with Genetic Algorithms
- 交通建設計畫評選模式及其解法之研究--以中小型交通建設計畫的評選為例
- Controlled Rounding Problem--Problem Modelling and Balanced Rounding Heuristic
- On Single-Machine Scheduling with Release Times to Minimize Total Weighted Completion Time
- 應用基因演算法於運鈔車護運作業排程規劃
- 軍方清淤水庫作業路面機具指派最佳化之研究
- 防災避難疏散排程規劃之研究
- 橋樑定期檢測作業排程最佳化模式之研究
- 混合確定與隨機需求下捷運車廂檢修長期人力供給規劃下之研究
頁籤選單縮合
題 名 | 節點塗色問題求解演算法之研究=An Algorithm for the Node Coloring Problem |
---|---|
作 者 | 顏上堯; 杜宇平; 黃韋凱; | 書刊名 | 運輸學刊 |
卷 期 | 13:4 2001.12[民90.12] |
頁 次 | 頁51-69 |
分類號 | 557.17 |
關鍵詞 | 節點塗色問題; 啟發解; 隨機變動搜尋方向; Node coloring problem; Heuristic; Randomly changing search direction; |
語 文 | 中文(Chinese) |
中文摘要 | 節點塗色問題為一傳統網路問題,其問題在給定一不具方向性網路,以最 小的顏色數量塗滿所有節點,但有節線相連的節點對則不可塗同樣的顏色。節點 塗色問題在數學上可歸類為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. |
本系統中英文摘要資訊取自各篇刊載內容。