組合優(yōu)化中的命題邏輯——以圖頂點(diǎn)染色問題為研究介質(zhì).pdf

1、組合優(yōu)化作為優(yōu)化問題的一個(gè)分支，同時(shí)也是計(jì)算機(jī)科學(xué)與運(yùn)籌學(xué)中的核心問題。組合優(yōu)化問題可看作是可行解集為離散型或可轉(zhuǎn)化為離散型的優(yōu)化問題，其目的在于從可行解集中找到最優(yōu)解。組合優(yōu)化問題有著諸多的實(shí)際應(yīng)用，如作業(yè)車間調(diào)度、規(guī)劃、資源分配、車輛路徑問題、整數(shù)規(guī)劃以及下料問題等。組合優(yōu)化問題的解意味著在最小資源消耗的同時(shí)實(shí)現(xiàn)利益的最大化，這不僅能為經(jīng)濟(jì)活動(dòng)者提高競(jìng)爭(zhēng)力，同時(shí)也可將對(duì)環(huán)境的負(fù)面影響降到最低，其重要性不言而喻。
　　 組合優(yōu)

2、化問題在通常情況下都是NP 難的。這也就是說，即使對(duì)于那些很小的問題，全局最優(yōu)解的尋找也會(huì)帶來相當(dāng)?shù)挠?jì)算復(fù)雜度。在許多實(shí)際應(yīng)用中，人們所采用的都是簡(jiǎn)單直觀的解，而這些解卻可能和最優(yōu)解相距甚遠(yuǎn)。對(duì)這一類問題解的微小地改進(jìn)，都能在實(shí)際應(yīng)用中帶來巨大的效應(yīng)。此外，許多組合優(yōu)化問題都相互聯(lián)系，因此在某一個(gè)問題上的進(jìn)展就能夠直接或間接地促進(jìn)其他問題的求解。
　　 命題邏輯可滿足性問題（SAT）是第一個(gè)被證明的NP 完全問題。SAT 問題作

3、為所有NP 完全問題的原型，吸引了人們對(duì)其的研究長(zhǎng)達(dá)60年之久。國(guó)際上有專門針對(duì)SAT 問題的研究小組，并且每年都舉辦SAT 問題的A 類會(huì)議。但是SAT 問題的實(shí)際應(yīng)用很有限，其本質(zhì)在于命題邏輯推理是一種相當(dāng)?shù)图?jí)的推理。此外，轉(zhuǎn)化后的SAT 實(shí)例往往丟失了原問題中結(jié)構(gòu)化的信息，從而使得求解過程更為困難。
　　 與之相反，圖染色（VCP）及其變種問題，比SAT 問題更加適合描述組合優(yōu)化問題中的外在性質(zhì)及結(jié)構(gòu)聯(lián)系。但目前對(duì)圖染色問

4、題的研究卻遠(yuǎn)不及SAT 問題那樣深入。圖染色問題作為一個(gè)經(jīng)典的具有NP 難度的組合優(yōu)化問題，不僅在實(shí)際生產(chǎn)中有著諸多應(yīng)用（調(diào)度、時(shí)間表安排、寄存器分配、網(wǎng)絡(luò)通信等），更在可計(jì)算理論中有著巨大理論價(jià)值，因此受到許多研究者的關(guān)注。
　　 本文提出了一種新的基于命題邏輯的圖染色完備求解算法：首先介紹了目前最好的SAT 求解器中的重要技術(shù)；隨后針對(duì)圖染色完備算法提出了若干改進(jìn)；最后通過在算例集上的實(shí)驗(yàn)計(jì)算，論證了將命題邏輯引入到圖染色求