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

概述與組合優(yōu)化概念續(xù)第1頁(yè)，課件共24頁(yè)，創(chuàng)作于2023年2月P,NP,NPC,NP-hard啟發(fā)式算法算法基礎(chǔ)第2頁(yè)，課件共24頁(yè)，創(chuàng)作于2023年2月第3頁(yè)，課件共24頁(yè)，創(chuàng)作于2023年2月問題、實(shí)例與輸入規(guī)模問題復(fù)雜性概念：復(fù)雜性的研究是從區(qū)分“問題”和“實(shí)例”并定義實(shí)例的“輸入規(guī)模”開始的。第4頁(yè)，課件共24頁(yè)，創(chuàng)作于2023年2月對(duì)于一個(gè)給定的組合優(yōu)化問題，當(dāng)問題中的參數(shù)賦予具體值時(shí)，稱為問題的一個(gè)實(shí)例如表1。這些具體值稱為數(shù)據(jù)，這些數(shù)據(jù)輸入計(jì)算機(jī)所占的空間稱為實(shí)例的輸入長(zhǎng)度或輸入規(guī)模如表2。表1問題實(shí)例TSPTSP例題中各參數(shù)為：100個(gè)城市，城市間距離已知背包問題背包例題中各參數(shù)為：4個(gè)物品，大小分別為4,3,2,2，價(jià)值分別為8,7,5,7，包的大小為6.整數(shù)線性規(guī)劃整數(shù)規(guī)劃例題中n，A,b，c已知。第5頁(yè)，課件共24頁(yè)，創(chuàng)作于2023年2月表2數(shù)據(jù)二進(jìn)制編碼輸入長(zhǎng)度111210210101046410000007k≥2≤第6頁(yè)，課件共24頁(yè)，創(chuàng)作于2023年2月一個(gè)實(shí)例完全由它的數(shù)據(jù)決定，給定一個(gè)問題的數(shù)據(jù)，即給定一個(gè)實(shí)例，我們可以用一種已知的計(jì)算機(jī)上的方法去求解。這種計(jì)算機(jī)上的求解方法稱為算法。算法不僅僅局限于每一個(gè)實(shí)例，而是求解問題的統(tǒng)一程序。評(píng)價(jià)算法的一個(gè)主要指標(biāo)是計(jì)算所耗用的時(shí)間。第7頁(yè)，課件共24頁(yè)，創(chuàng)作于2023年2月迄今為止，許多的組合優(yōu)化問題都沒有找到求最優(yōu)解的多項(xiàng)式時(shí)間算法。比多項(xiàng)式問題類可能更廣泛的一個(gè)問題類是非確定多項(xiàng)式時(shí)間（nondeterministicpolynomial，NP）問題，NP的概念是由判斷問題引入的。如果一個(gè)問題的每一個(gè)實(shí)例只有“是”或“否”兩種答案，則稱這個(gè)問題為判斷問題。稱有肯定答案的實(shí)例為“是”實(shí)例，稱答案為“否”的實(shí)例為“否”實(shí)例或非“是”實(shí)例。第8頁(yè)，課件共24頁(yè)，創(chuàng)作于2023年2月優(yōu)化問題與判定問題

在研究組合優(yōu)化問題復(fù)雜性時(shí)，處理的方法是對(duì)給定的一類優(yōu)化問題，將其轉(zhuǎn)化為判定問題，使對(duì)每一個(gè)實(shí)例只有“是”或“否”的回答。下面給出幾個(gè)優(yōu)化問題對(duì)應(yīng)的判定問題。第9頁(yè)，課件共24頁(yè)，創(chuàng)作于2023年2月將LP（目標(biāo)函數(shù)為求最?。┺D(zhuǎn)化為L(zhǎng)P判定問題第10頁(yè)，課件共24頁(yè)，創(chuàng)作于2023年2月P類問題

給定每個(gè)問題的實(shí)例，我們有多項(xiàng)式時(shí)間算法得出答案是是還是不是。NP問題

如果X是判定問題的一個(gè)答案為“是”的實(shí)例，則存在一個(gè)對(duì)X的一個(gè)多項(xiàng)式時(shí)間為界驗(yàn)證，使得能在多項(xiàng)式時(shí)間內(nèi)驗(yàn)證這個(gè)證明的真實(shí)性；第11頁(yè)，課件共24頁(yè)，創(chuàng)作于2023年2月定理：

即P是NP的子集。多項(xiàng)式時(shí)間歸納法（轉(zhuǎn)換）兩個(gè)判定問題

，如果

多項(xiàng)式歸結(jié)到

，則當(dāng)

有多項(xiàng)式算法時(shí)，

也有多項(xiàng)式時(shí)間算法。第12頁(yè)，課件共24頁(yè)，創(chuàng)作于2023年2月所有的P類問題都是屬于NP問題.P是否等于NP?這個(gè)問題至今還未解決NP問題不一定都是難解的問題，比如簡(jiǎn)單的數(shù)組排序問題是P類問題，但是P屬于NP，所以也是NP問題.現(xiàn)在還不知道是否有P=NP或者P<>NP，但是后來(lái)人們發(fā)現(xiàn)還有一系列的特殊NP問題，這類問題的特殊性質(zhì)使得很多人相信P<>NP，只不過現(xiàn)在還無(wú)法證明。這類特殊的NP問題就是NP完全問題第13頁(yè)，課件共24頁(yè)，創(chuàng)作于2023年2月NP－Complete（NP完備類）第14頁(yè)，課件共24頁(yè)，創(chuàng)作于2023年2月常見的NP－完備問題有成千上萬(wàn)個(gè)NP－完備問題，如：整數(shù)線性規(guī)劃、團(tuán)、貨郎擔(dān)問題、適定性問題、點(diǎn)覆蓋、獨(dú)立集、哈密頓圈問題、0－1背包問題。事實(shí)上要證明一個(gè)問題是NP－完備的轉(zhuǎn)化為要證明：1）該問題是NP的2）有一個(gè)已知的NP－完備問題可以多項(xiàng)式時(shí)間轉(zhuǎn)化為該問題。第15頁(yè)，課件共24頁(yè)，創(chuàng)作于2023年2月NP－困難問題第16頁(yè)，課件共24頁(yè)，創(chuàng)作于2023年2月PNPNPCNPH第17頁(yè)，課件共24頁(yè)，創(chuàng)作于2023年2月一個(gè)問題的最優(yōu)算法求得該問題每個(gè)實(shí)例的最優(yōu)解，啟發(fā)式算法是對(duì)應(yīng)最優(yōu)算法提出的。定義為：一個(gè)基于直觀和經(jīng)驗(yàn)的短發(fā)，在可接受的花費(fèi)下給出待解決組合最優(yōu)化問題每一個(gè)實(shí)例的一個(gè)可行解，改可行解與最優(yōu)解的偏離程度不一定事先可以預(yù)計(jì)。在某些情況下，特別是實(shí)際問題中，最優(yōu)算法的計(jì)算時(shí)間使人無(wú)法忍受或因問題的難度事情計(jì)算時(shí)間隨實(shí)例規(guī)模的增加以指數(shù)速度增加。如TSP枚舉算法。第18頁(yè)，課件共24頁(yè)，創(chuàng)作于2023年2月背包問題的貪婪算法Step1對(duì)物品以從大到小排列，不妨把排列記成{1,2，…,n},k=1.Step2若則，否則k=k+1；當(dāng)k=n+1時(shí)，停止；否則，重復(fù)Step2。

為貪婪算法的解，單位尺寸價(jià)值比越大越先裝包。

第19頁(yè)，課件共24頁(yè)，創(chuàng)作于2023年2月

的比值計(jì)算需要n次運(yùn)算，從小到大排列需要次運(yùn)算。（k=1,2，…,n）對(duì)于每一個(gè)k需要一次加法和一次比較，共2n次運(yùn)算，這個(gè)貪婪算法的計(jì)算量為，是一個(gè)多項(xiàng)式時(shí)間算法。第20頁(yè)，課件共24頁(yè)，創(chuàng)作于2023年2月啟發(fā)式算法優(yōu)點(diǎn)：1）數(shù)學(xué)模型本身是實(shí)際問題的簡(jiǎn)化，或多或少地忽略了一些因素；而且數(shù)據(jù)采集具有不確定性；參數(shù)估計(jì)估計(jì)具有不準(zhǔn)確性；這些因素可能造成最優(yōu)算法所得到的解比啟發(fā)式算法更差。2）有些難的組合優(yōu)化問題可能還沒找到最優(yōu)算法，由算法復(fù)雜性理論，它們的計(jì)算時(shí)間也是不可接受的。3）一些啟發(fā)式算法可以用在最優(yōu)算法中，比如分支定界算法中，可以用啟發(fā)式算法估計(jì)上下界。4）簡(jiǎn)單易行，比較直觀，易被使用者接受。5）速度快，這在實(shí)時(shí)管理中非常重要。6）多數(shù)情況下，程序簡(jiǎn)單，易于在計(jì)算機(jī)上實(shí)現(xiàn)和修改.第21頁(yè)，課件共24頁(yè)，創(chuàng)作于2023年2月啟發(fā)式算法缺點(diǎn)1）不能保證求得最優(yōu)解2）表現(xiàn)不穩(wěn)定，啟發(fā)式算法在同一問題的不同實(shí)例計(jì)算機(jī)中會(huì)有不同的效果，有些很好，有些很差。在實(shí)際應(yīng)用中，這種不穩(wěn)定性造成計(jì)算結(jié)果不可信，可能造成管理困難。3）算法的好壞依賴于實(shí)際問題，算法設(shè)計(jì)者的經(jīng)驗(yàn)和技術(shù)，這一點(diǎn)很難總結(jié)規(guī)律，同時(shí)使不同算法之間難于比較。第22頁(yè)，課件共24頁(yè)，創(chuàng)作于2023年2月啟發(fā)式算法分類：1）簡(jiǎn)單直觀的算法：如貪婪算法2）數(shù)學(xué)規(guī)劃算法：拉格朗日松弛算法3）現(xiàn)代優(yōu)化算法：遺傳算法，蟻群算法第23頁(yè)，課件共24頁(yè)，創(chuàng)作于2023年2月啟發(fā)式算法性能分析評(píng)價(jià)算法優(yōu)劣常用的三個(gè)主要指標(biāo)：算法復(fù)雜性、解的偏離程度、和算法的穩(wěn)健性，即同一算法對(duì)不同實(shí)例、在