【正文】 P問(wèn)題，具有良好的組合結(jié)構(gòu)）。例如，求解線性規(guī)劃的單純形法從理論上講是指數(shù)算法，但在實(shí)際應(yīng)用時(shí)它又一般表現(xiàn)得出奇地好（已經(jīng)證明，其平均計(jì)算量?jī)H為 O(nlog2n)）。出于實(shí)際需要，人們不得不采取一些折中的辦法，即以枚舉為基礎(chǔ)，選用一些減少計(jì)算量的技巧或規(guī)則，以增大算法的實(shí)用效果。事實(shí)上，僅對(duì)部分變量有非負(fù)約束的線性規(guī)劃（稱(chēng)為混合整數(shù)規(guī)劃）也是 NP完全的。 13( 1 ) 3 / 2 1 )j j j kj K tw C a a t b Z? ? ?? ? ? ???jjwC?jjwC?167。除去加工這 t－ 1項(xiàng)工件的時(shí)段，整個(gè)加工期還留下長(zhǎng)度均為 b的 t個(gè)時(shí)段。相應(yīng)數(shù)據(jù)為 1njjj wC??j=1,…,3 t，令 rj=0，需加工時(shí)間 Pj=aj, wj=1 j=3t+1,…,4 t－ 1，令 rj= (j－ 3t)(b+1)－ 1 Pj=1, wj=2 ??等價(jià)性證明可分以下幾步完成，有興趣的讀者可以自己完成它： （ 1）證明最后 t－ 1項(xiàng)工件應(yīng)盡早加工，否則必將增大 ，因?yàn)樗鼈兊?wj=2，而前 3t項(xiàng)則有 wj=1。 311 tiibat?? ?, 42ibbia? ? ?現(xiàn)在，我們來(lái)證明，對(duì)三元?jiǎng)澐謫?wèn)題的每一實(shí)例，總可構(gòu)造出一個(gè)等價(jià)的1/1/rj, prmp/ 排序問(wèn)題的實(shí)例，（因此，會(huì)解后者就必會(huì)解前者）。我們將用到下面的已被證明的 NP完全問(wèn)題。評(píng)判排序優(yōu)劣的標(biāo)準(zhǔn)為各工件完工時(shí)間 Cj的加權(quán)和 越小越好。 prmp表示加工允許中斷以便先加工其他工件，未完成的加工可在此后的某一時(shí)期補(bǔ)上。下面給出一個(gè)稍難一些的例子，供有興趣的讀者參考。 在上面的例 ，我們又列舉了幾個(gè) NP完全問(wèn)題，它們的 NP完全性證明都非常簡(jiǎn)單。 γ=Cmax的解釋同上。這里， α=P2表示是一個(gè) 2臺(tái)機(jī)器的平行機(jī)問(wèn)題，即有兩臺(tái)完全相同的機(jī)器，每一工件只需在其中任意一臺(tái)上加工一次即可。在那里已經(jīng)證明了這一問(wèn)題等價(jià)與 TSP，從而是 NP完全的。 υ =Cmax表示排序優(yōu)劣的評(píng)價(jià)標(biāo)準(zhǔn)是全系統(tǒng)的加工時(shí)間最短，即由第一臺(tái)機(jī)器開(kāi)始加工起到最后一臺(tái)機(jī)器完工為止的時(shí)間跨度最小。 Job shop意指每一工件要在 m臺(tái)機(jī)器的每一臺(tái)上加工（當(dāng)不需某臺(tái)加工時(shí)可令加工時(shí)間為零），且各工件使用機(jī)器的順序可以不同。 Jm/ no wait /Cmax問(wèn)題是 NP完全的。按此方法分類(lèi)，有人作過(guò)統(tǒng)計(jì)，認(rèn)為至少有 9000多個(gè)不同的排序問(wèn)題已被或多或少地研究過(guò)，其中 76%為 NP完全的 ， 12%的為 P問(wèn)題 ，余下的 12%目前還未搞清其計(jì)算復(fù)雜性，但根據(jù)種種跡象 ，大部分可能是 NP完全的。 Scheduling是一類(lèi)應(yīng)用面極廣的離散問(wèn)題，可以講它不是一個(gè)問(wèn)題，而是一類(lèi)問(wèn)題，因?yàn)椴煌臋C(jī)器環(huán)境、不同的加工要求或不同的衡量標(biāo)準(zhǔn)所得出的模型是不同的。順便指出， Bin—packin問(wèn)題中的臬子容量 C可以取為 1，這樣的問(wèn)題與例 。但對(duì) 3—?jiǎng)澐謫?wèn)題不可能存在類(lèi)似算法，由于本書(shū)篇幅有限，不再作詳盡的討論。事實(shí)上， 取 ， J={c1,…, }可劃分為兩個(gè)相等的集合的充要條件是 它們可裝入兩只容量為 C的箱中。 定理 （一維） Bin—packing問(wèn)題是 NP—完全的。而當(dāng)我們真正想把一批已知長(zhǎng)、寬、高的物體裝入具有相同尺寸的箱子時(shí)，又遇到了三維的。此時(shí)，我們就遇到了一個(gè)一維的 Bin—packing問(wèn)題。 例 。 112niiKC?? ?例 ：以 K為“背包”的容量，欲將 C中的整數(shù)裝入背包中，使背包中的各數(shù)之和盡可能地大（求－ C的子集 S，使 且盡可能大），即要求求解 0－ 1（線性）規(guī)劃問(wèn)題： i icSCK? ??St xi≥0， xi≤1 xi為整數(shù) 1m ax n iiicx??1niiic x K???例 （裝箱問(wèn)題 —— Bin— packing）有一批待裝箱的物品J={p1,?, pn}， pj的長(zhǎng)度為 l(pj)。 例 （背包問(wèn)題） 給定一組整數(shù) C={c1,…, }以及一整數(shù) K，問(wèn)是否存在C的一個(gè)子集 S，使得 。事實(shí)上，對(duì)任意 中的邊（ υi,υj），有（ υi,υj）不在 G中，故 υi,υj不能全在 G的團(tuán) K中，從而 υi與 υj中至少有一個(gè)在 V－ K中，由邊（ υi,υj）的任意性可知， V－ K中，由邊（ υi,υj）的任意性可知， V－ K 必為 的一個(gè)復(fù)蓋。而團(tuán)問(wèn)題是 NP完全的（見(jiàn)第八章六個(gè)基本 NP完全問(wèn)題），故獨(dú)立集問(wèn)題是 NP完全的。 證明 稱(chēng)圖 為圖 G的補(bǔ)集，若 與 G有相同的頂點(diǎn)集，且（ υi,υj）是 的邊當(dāng)且僅當(dāng)它不是 G的邊。 ( , )uE???對(duì)于例 ，我們?yōu)閿⑹龇奖?，采用了圖的語(yǔ)言，其實(shí)也完全可以將它們表達(dá)成其他方式。 所謂獨(dú)立集是指 V的一個(gè)子集 ，有 1{ , , }, 1 ,kii s t k?? ? ? ?( , )stii E?? ?例 （復(fù)蓋問(wèn)題） 給定圖 G=（ V， E），求 G的頂點(diǎn)的一個(gè)最小復(fù)蓋。本節(jié)將再分析一些問(wèn)題，看看別人是如何判定它們的 NP完全性的。要判定一個(gè)離散問(wèn)題的性質(zhì)沒(méi)有一個(gè)固定的程式可以沿用（雖然總是用多項(xiàng)式轉(zhuǎn)換的方法），常常要用到較高的技巧，并要求對(duì)問(wèn)題的組合結(jié)構(gòu)有相當(dāng)?shù)牧私?。但這類(lèi)問(wèn)題事實(shí)上有無(wú)限多個(gè)，很多時(shí)候，我們會(huì)遇到一些對(duì)其計(jì)算機(jī)復(fù)雜性一無(wú)所知的問(wèn)題。有時(shí)，我們可以從有關(guān)書(shū)籍或文獻(xiàn)中查到它，因?yàn)閯e人早已對(duì)它作過(guò)研究。各種跡象使人們來(lái)越來(lái)越傾向于相信，對(duì)這些問(wèn)題根本不存在有效算法，自 1972年 Cook發(fā)表那篇著名的論文以來(lái)，這些問(wèn)題越來(lái)越多地被發(fā)現(xiàn)。正如第八章所講，存在著大量具有 NP完全性的問(wèn)題，雖然許多人作了巨大的努力，仍未找到任何有效算法。從某種意義上說(shuō)，可以認(rèn)為這些問(wèn)題已被較好地解決了。 167。一方面，我們必須先搞清問(wèn)題的計(jì)算復(fù)雜性，而另一方面，條件的微小改變就有可能將一個(gè) P問(wèn)題轉(zhuǎn)變?yōu)镹P完全的。但可以證明，最大切割問(wèn)題卻是 NP完全的。又譬如，網(wǎng)絡(luò)流中的最大流問(wèn)題是 P問(wèn)題。由于哈密頓路問(wèn)題是 NP 完全的，故最長(zhǎng)簡(jiǎn)單路徑問(wèn)題的有效算法不可能存在，除非 P=NP。如若不然，我們可以利用它的有效算法如下構(gòu)造出哈密頓問(wèn)題的有效算：令圖 G=（ V， E）的所有邊的權(quán)均為 1，以一端點(diǎn)為起點(diǎn)求到其余各頂點(diǎn)的最長(zhǎng)簡(jiǎn)單路徑。 求最小的問(wèn)題是 P問(wèn)題，求最大的問(wèn)題可以是 NP完全的，這樣的例子也不少。 （ 4）線性規(guī)劃問(wèn)題、運(yùn)輸問(wèn)題及指派問(wèn)題均為 P問(wèn)題，但相應(yīng)的整數(shù)線性規(guī)劃及 0—1規(guī)劃均為 NP完全的。 （ 3）歐拉圈問(wèn)題求由一頂點(diǎn)出發(fā)經(jīng)且僅經(jīng)過(guò)每邊一次回到原頂點(diǎn)的圈，而TSP則求由一頂點(diǎn)出發(fā)經(jīng)且僅經(jīng)過(guò)每個(gè)頂點(diǎn)一次返回原頂點(diǎn)的圈。 （ 2）指派問(wèn)題與 TSP也有相似之處，前者求一置換而使目標(biāo)值最小，后者求一循環(huán)置換（不包含子圈）而使目標(biāo)值最小。 （ 1）最短路徑問(wèn)題是 P問(wèn)題，而由一點(diǎn)出發(fā)到達(dá)每一頂點(diǎn)一次（不必返回原點(diǎn)）的哈密頓路問(wèn)題及由一頂點(diǎn)出發(fā)經(jīng)所有頂點(diǎn)一次到達(dá)另一頂點(diǎn)的最短路徑問(wèn)題 ——流浪的旅行商問(wèn)題（ WTSP）均是 NP完全的。 最后，我們還想強(qiáng)調(diào)幾點(diǎn)： 許多表面有點(diǎn)相象的問(wèn)題事實(shí)上可能具有完全不同的計(jì)算復(fù)雜性。線性規(guī)劃的單純形法例外，改進(jìn)次數(shù)可能達(dá)到指數(shù)次。從上述 P問(wèn)題（包括第八章中的線性規(guī)劃、運(yùn)輸問(wèn)題及指派問(wèn)題）可以看出，它們都可以用某種逐次改進(jìn)的方法來(lái)求解。由于事實(shí)上存在著無(wú)窮多個(gè) P問(wèn)題，而且即使某問(wèn)題是 NP完全的，它的許多特殊條件下的子問(wèn)題也仍然可以是多項(xiàng)式時(shí)間可解的，因而我們不可能對(duì) P類(lèi)作一完整的介紹。 。然后，求出任意兩個(gè)奇頂點(diǎn)之間的最短路徑及最短矩離最短路徑長(zhǎng)度），再解一個(gè)奇頂點(diǎn)之間的最小權(quán)匹配（或指派問(wèn)題，注意這里的距離矩陣是對(duì)稱(chēng)的）。若無(wú)向圖 G是歐拉圖，則任一歐拉圖都提供了一條最佳郵路。一個(gè)由郵局出發(fā)去各街道送信最后返回郵局的郵遞員遇到的問(wèn)題就是一個(gè)中國(guó)郵路問(wèn)題。要求從一指定頂點(diǎn)出發(fā)，至少經(jīng)過(guò)每一條邊一次最后返回原出發(fā)點(diǎn)，并使經(jīng)過(guò)邊的總長(zhǎng)度最小。 與歐拉圖有較大聯(lián)系的另一有名的 P問(wèn)題是無(wú)向圖上的中國(guó)郵路問(wèn)題。而圖的奇頂點(diǎn)數(shù)又可通過(guò)對(duì)其頂點(diǎn)一一檢測(cè)而求得。下面的圖 （ a）為歐拉圈，而圖 （ b）則為歐拉路，后者雖可一筆畫(huà)出，但必須以一個(gè)奇頂點(diǎn)為起點(diǎn)，以另一個(gè)奇頂為終點(diǎn)。 把關(guān)聯(lián)偶數(shù)條邊的頂點(diǎn)稱(chēng)為偶頂點(diǎn)，把關(guān)聯(lián)奇數(shù)條邊的頂點(diǎn)稱(chēng)為奇頂點(diǎn)，則容易看出奇頂點(diǎn)的個(gè)數(shù)必為偶數(shù)個(gè)（因?yàn)槊恳还P畫(huà)都產(chǎn)生一個(gè)起點(diǎn)與一個(gè)終點(diǎn)），又易得出 定理 G為歐拉路的充要條件為： G是連通的且奇頂點(diǎn)的個(gè)數(shù)為 2。顯然，圖 G為歐拉圖的充要條件是它可以被一筆畫(huà)出且首尾相連（當(dāng)首尾不能相連時(shí)則被稱(chēng)為歐拉路）。給定一個(gè)無(wú)向圖 G=（ V， E），問(wèn)能否由一個(gè)頂點(diǎn)出發(fā)，經(jīng)且僅經(jīng)過(guò)每條邊一次并返回原出發(fā)頂點(diǎn)。 容易看出，作出 n年設(shè)備更新問(wèn)題的有向圖將問(wèn)題化為最短路徑問(wèn)題大約需要 O(n2)計(jì)算量，其后要求求解的最短路徑問(wèn)題的計(jì)算量也是 O(n2)，故設(shè)備更新問(wèn)題可在 O(n2)時(shí)間內(nèi)求解。例如，?。?① ， ② ）上的數(shù) 68表示第一年初購(gòu)買(mǎi)設(shè)備到 5年后的第六年初更換，需支付購(gòu)設(shè)備費(fèi) 10萬(wàn)元及各年維修費(fèi) 58 萬(wàn)元，共計(jì) 68萬(wàn)元。當(dāng)然，作為一般情況，還可能要考慮殘值，如購(gòu)買(mǎi)了新車(chē)，舊車(chē)可以折價(jià)處理，回收資金與已使用年數(shù)有關(guān)?，F(xiàn)準(zhǔn)備制訂一個(gè)五年內(nèi)的設(shè)備更新計(jì)劃，使五年內(nèi)支付的設(shè)備購(gòu)置費(fèi)用及總維修費(fèi)用最少。 作為最短路徑問(wèn)題的一個(gè)應(yīng)用實(shí)例，我們來(lái)研究下面的設(shè)備更新問(wèn)題： 例 某單位使用一種設(shè)備。 從圖 A到各點(diǎn)的距離及最短路徑，而從圖 各點(diǎn)到 E點(diǎn)的距離及最短路徑，這是兩者的區(qū)別。 按一般習(xí)慣，動(dòng)態(tài)規(guī)劃算法常按逆順序進(jìn)行。算法進(jìn)行中，事實(shí)上在構(gòu)造一棵由已標(biāo)號(hào)頂點(diǎn)及它們與其前行點(diǎn)間的邊組成的樹(shù)。 容易看出，算法是多項(xiàng)式時(shí)間的。直到擬到達(dá)的終點(diǎn)已標(biāo)號(hào)為止。一般，在標(biāo)新頂點(diǎn)時(shí)，先找出離已標(biāo)號(hào)頂點(diǎn)最近的頂點(diǎn)。（兩者目的略有不同）對(duì)例 ，如從起點(diǎn) A開(kāi)始標(biāo)導(dǎo)，先在 A點(diǎn)標(biāo)上 0。算法既可以通過(guò)對(duì)頂點(diǎn)逐次標(biāo)號(hào)來(lái)實(shí)現(xiàn)，也可以通過(guò)矩陣運(yùn)算進(jìn)行。若點(diǎn)P在 A到 E的最短路上，則 P到 E的最短路徑必整個(gè)地包含在 A到 E的最短路徑上。 例 給定圖 ，邊上的數(shù)字為兩頂點(diǎn)間的距離（或費(fèi)用），求由 A到 E的最短路徑。 P四、最短路徑問(wèn)題 最短路徑問(wèn)題是又一個(gè)經(jīng)常遇到的 P問(wèn)題，它在工藝流程的安排、管道或網(wǎng)絡(luò)的鋪設(shè)、設(shè)備更新等實(shí)際生產(chǎn)中常被用到，是網(wǎng)絡(luò)規(guī)劃的基本問(wèn)題之一。找出最大財(cái)禮數(shù) 28，以此數(shù)減每邊原有的財(cái)禮費(fèi)，并用此差為各邊的費(fèi)用，得一最小費(fèi)用最大流問(wèn)題（未注數(shù)字的邊費(fèi)用均為零），其網(wǎng)絡(luò)圖見(jiàn)圖 。它可用來(lái)求解運(yùn)輸問(wèn)題、指派問(wèn)題及賦權(quán)兩分圖匹配問(wèn)題（等價(jià)于指派問(wèn)題），也可用來(lái)尋找網(wǎng)絡(luò)的瓶頸 ——即最小切割（ P， ）確定的邊。這樣，每次得到的均為相同流量的流中費(fèi)用最小的，而最后得到的即為最小費(fèi)用最大流。算法可以用歸納方式給出，當(dāng) υ=0時(shí)，可取 =0，這顯然是 υ=0的最小費(fèi)用流。由于 1是最小費(fèi)用流， 1的增廣網(wǎng)絡(luò)中不存在負(fù)圈，故 C中必有一邊（ i, j），其反向邊（ j, i）含在 P中（因?yàn)槿缛舨蝗唬?C不含 P中任意邊，則 C將含在 1的增廣網(wǎng)絡(luò)中，與 1為最小費(fèi)用流的假設(shè)矛盾，見(jiàn)圖 ），但這又說(shuō)明 P∪ （ C－（ i, j））是S到 t的更小費(fèi)用單位流增廣路，與 P是最小費(fèi)用單位流增廣路的假設(shè)矛盾。 證明： 設(shè) 1+2不是流量為 υ+1的最小費(fèi)用流，由定理 6，在 1+ 2的增廣網(wǎng)絡(luò)中必存在一負(fù)圈 C。 圖 （ a）中流的增廣網(wǎng)絡(luò)（ b）中已不存在負(fù)費(fèi)用循環(huán)流，它是一個(gè)最小費(fèi)用的流。調(diào)整此循環(huán)流上的流量，得到圖（ a）中的流。求此網(wǎng)絡(luò)的一個(gè)更小費(fèi)用流。 ?例 圖 （ a）給出了有向圖 G上的一個(gè)可行流，其中弧上的三個(gè)數(shù)字分別為容量、單位流費(fèi)用及實(shí)際流量。 ? ? 定義 增廣網(wǎng)絡(luò) G’上由 s到 t的流量為零但邊流量不全為零的流稱(chēng)為一個(gè)循環(huán)流?，F(xiàn)在，我們將以最大流問(wèn)題的增廣路算法為基礎(chǔ)，導(dǎo)出求解最小費(fèi)用最大流問(wèn)題的算法。希望求出由 s到 t的最大流，使得總費(fèi)用最少，即求最大流 φ*，使 *( , )( ) m in { ( , ) ( , ) }i j AL l i j i j????? ?最大流例如，在交通網(wǎng)絡(luò)中， l(i, j)可以是 i, j之間的距離或運(yùn)費(fèi)。如圖 ，圖中的（ a）、（ b）、（ c）均是流量為 7的最大流，邊上的兩個(gè)數(shù)字依次為容量和邊上的實(shí)際流量。例如由圖 作出其相應(yīng)的增廣網(wǎng)絡(luò)圖 ，其中實(shí)箭線為正規(guī)定，虛箭線為增廣邊，邊上的數(shù)字為邊容量。39。, , ,C j i C j i j i???（ 2）若