高效的圖染色近似型求解算法.pdf

1、圖染色問題是一個典型的NP問題，求解圖染色問題的方法主要分為完備型算法和近似型算法，完備型算法通過有序的遍歷所有解空間來求解，近似型算法使用啟發(fā)式策略選取有效的解空間來搜索進行求解，近似型算法由于其高效性被廣泛使用。
　　 圖染色問題的研究重點是快速的選取結(jié)點進行有效的染色。論文通過將圖染色問題轉(zhuǎn)化成命題邏輯滿足的問題，將命題邏輯滿足問題中的概念和方法引入到圖染色問題中，并將圖染色問題轉(zhuǎn)化后的邏輯表達式數(shù)值化，建立數(shù)值化的評價方

2、法來求解。
　　 在求解圖染色的過程中，使用完全子圖的特殊結(jié)構(gòu)，將完全子圖從原圖中剝離出來，確定性的對圖的完全子圖進行染色，搜索余下圖的可行解，使得圖染色過程搜索的空間大幅度降低，減輕了算法的搜索負擔(dān)。同時，將命題邏輯問題中下降變元的概念首次引入到圖染色問題的求解中，通過定義圖染色中的下降變元，加快了搜索有效解空間的速度，增強了算法的求解能力。在選取結(jié)點時，算法使用了次優(yōu)先選擇策略和噪音技術(shù)相結(jié)合的方法，優(yōu)化了算法選取結(jié)點的能力