第一章概述與組合優(yōu)化概念續(xù)

1、第一章概述與組合優(yōu)化概念續(xù)P,NP,NPC,NP-hard啟發(fā)式算法算法基礎(chǔ)問題、實例與輸入規(guī)模問題、實例與輸入規(guī)模問題復(fù)雜性概念：復(fù)雜性的研究是從區(qū)分“問題”和“實例”并定義實例的“輸入規(guī)模”開始的。對于一個給定的組合優(yōu)化問題，當問題中的參數(shù)賦予具體值時，稱為問題的一個實例如表1。這些具體值稱為數(shù)據(jù)，這些數(shù)據(jù)輸入計算機所占的空間稱為實例的輸入長度或輸入規(guī)模如表2。表1問題問題實例實例TSPTSP例題中各參數(shù)為：100個城市，城市間距離 已知背包問題背包例題中各參數(shù)為：4個物品，大小分別為4,3,2,2，價值分別為8,7,5,7，包的大小為6.整數(shù)線性規(guī)劃整數(shù)規(guī)劃例題中n，A,b，c已知。ij

2、d表2數(shù)據(jù)數(shù)據(jù)二進制編碼二進制編碼輸入長度輸入長度11121021010104641 000 0007k2log1k 一個實例完全由它的數(shù)據(jù)決定，給定一個問題的數(shù)據(jù)，即給定一個實例，我們可以用一種已知的計算機上的方法去求解。這種計算機上的求解方法稱為算法。算法不僅僅局限于每一個實例，而是求解問題的統(tǒng)一程序。評價算法的一個主要指標是計算所耗用的時間。迄今為止，許多的組合優(yōu)化問題都沒有找到求最優(yōu)解的多項式時間算法。比多項式問題類可能更廣泛的一個問題類是非確定多項式時間（nondeterministic polynomial，NP）問題，NP的概念是由判斷問題引入的。如果一個問題的每一個實例只有“是

3、”或“否”兩種答案，則稱這個問題為判斷問題。稱有肯定答案的實例為“是”實例，稱答案為“否”的實例為“否”實例或非“是”實例。優(yōu)化問題與判定問題優(yōu)化問題與判定問題 在研究組合優(yōu)化問題復(fù)雜性時，處理的方法是對給定的一類優(yōu)化問題，將其轉(zhuǎn)化為判定問題，使對每一個實例只有“是”或“否”的回答。下面給出幾個優(yōu)化問題對應(yīng)的判定問題。將LP（目標函數(shù)為求最小）轉(zhuǎn)化為LP判定問題P P類問題類問題 給定每個問題的實例，我們有多項式時間算法得出答案是是還是不是。NPNP問題問題 如果X是判定問題的一個答案為“是”的實例，則存在一個對X 的一個多項式時間為界驗證，使得能在多項式時間內(nèi)驗證這個證明的真實性；定理： 即

4、P是NP的子集。多項式時間歸納法多項式時間歸納法（轉(zhuǎn)換）兩個判定問題 ，如果 多項式歸結(jié)到 ，則當 有多項式算法時， 也有多項式時間算法。12,A A1A2A2A1A所有的P類問題都是屬于NP問題.P是否等于NP?這個問題至今還未解決NP問題不一定都是難解的問題，比如簡單的數(shù)組排序問題是P類問題，但是P屬于NP，所以也是NP問題.現(xiàn)在還不知道是否有P=NP或者PNP，但是后來人們發(fā)現(xiàn)還有一系列的特殊NP問題，這類問題的特殊性質(zhì)使得很多人相信PNP，只不過現(xiàn)在還無法證明。這類特殊的NP問題就是NP完全問題NPNPCompleteComplete（NP完備類）常見的常見的NPNP完備問題完備問題有

5、成千上萬個NP完備問題，如：整數(shù)線性規(guī)劃、團、貨郎擔問題、適定性問題、點覆蓋、獨立集、哈密頓圈問題、01背包問題。事實上要證明一個問題是NP完備的轉(zhuǎn)化為要證明： 1）該問題是NP的 2）有一個已知的NP完備問題可以多項式時間轉(zhuǎn)化為該問題。NPNP困難問題困難問題PNPNPCNPH一個問題的最優(yōu)算法求得該問題每個實例的最優(yōu)解，啟發(fā)式算法是對應(yīng)最優(yōu)算法提出的。定義為：一個基于直觀和經(jīng)驗的短發(fā)，在可接受的花費下給出待解決組合最優(yōu)化問題每一個實例的一個可行解，改可行解與最優(yōu)解的偏離程度不一定事先可以預(yù)計。在某些情況下，特別是實際問題中，最優(yōu)算法的計算時間使人無法忍受或因問題的難度事情計算時間隨實例規(guī)模

6、的增加以指數(shù)速度增加。如TSP枚舉算法。背包問題的貪婪算法Step1 對物品以 從大到小排列，不妨把排列記成1,2，,n, k=1.Step2 若 則 ，否則 k=k+1；當k=n+1時，停止；否則，重復(fù) Step2 。 為貪婪算法的解，單位尺寸價值比越大越先裝包。 iica11,kiikia xab1kx 0kx 12(,.,)kx xx 的比值計算需要n次運算， 從小到大排列需要 次運算。 （k=1,2，,n）對于每一個k需要一次加法和一次比較 ，共2n次運算，這個貪婪算法的計算量為 ，是一個多項式時間算法。iicaiica2( log)nn11,kiikia xab2( log)nn啟發(fā)

7、式算法優(yōu)點：1）數(shù)學模型本身是實際問題的簡化，或多或少地忽略了一些因素；而且數(shù)據(jù)采集具有不確定性；參數(shù)估計估計具有不準確性；這些因素可能造成最優(yōu)算法所得到的解比啟發(fā)式算法更差。2）有些難的組合優(yōu)化問題可能還沒找到最優(yōu)算法，由算法復(fù)雜性理論，它們的計算時間也是不可接受的。3）一些啟發(fā)式算法可以用在最優(yōu)算法中，比如分支定界算法中，可以用啟發(fā)式算法估計上下界。4）簡單易行，比較直觀，易被使用者接受。5）速度快，這在實時管理中非常重要。6）多數(shù)情況下，程序簡單，易于在計算機上實現(xiàn)和修改.啟發(fā)式算法分類：1）簡單直觀的算法：如貪婪算法2）數(shù)學規(guī)劃算法：拉格朗日松弛算法3）現(xiàn)代優(yōu)化算法：遺傳算法，蟻群算法啟發(fā)式算法性能分析評價算法優(yōu)劣常用的三個主要指標：算法復(fù)雜性、解的偏離程度、和算法的穩(wěn)健性，即同一算法對不同實例、在不同時間、不同起點的計算效果的差異大小。評