【正文】 向圖上的哈密頓圈、哈密頓路和 TSP也是 NP完全的，因?yàn)橛脙蓷l具有相反方向的弧來(lái)代替每一條邊，就可將一個(gè)無(wú)向圖上的問題轉(zhuǎn)化為一個(gè)有向圖上的問題，從而任一有向圖問題的有效算法必能用來(lái)求解無(wú)向圖問題。 iicSCK? ??不難看出，背包問題是 NP完全的，因?yàn)槿羧? ， 問題就化成了劃分問題?，F(xiàn)有一批容量為 C的箱子（足夠數(shù)量），要求找到一種裝箱方法，使得所用的箱子數(shù)最少。例如，我們有一批具有相同長(zhǎng)度的鋼材，如果想取出幾根已知長(zhǎng)度的鋼料生產(chǎn)某種設(shè)備，當(dāng)然會(huì)希望少用幾根原始鋼材以減少浪費(fèi)。當(dāng)我們想從購(gòu)買來(lái)的三夾板上鋸出 n塊已知長(zhǎng)、寬的板來(lái)制作家具時(shí)，遇到的是二維Bin—packing問題。下面的定理 告訴我們，即使是一維的 Bin—packing問題也是 NP完全的，故二維和三維的 Bin—packing問題更不可能是 P問題（它們也是 NP完全的）。 證明： 易見，劃分問題可轉(zhuǎn)化為 Bin— packing問題。 112njjCc?? ?從某種意義上講， 3—?jiǎng)澐謫栴}（即分為三個(gè)相等子集的問題）也許比 2—?jiǎng)澐謫栴}更難，因?yàn)橐呀?jīng)找到了求解 2—?jiǎng)澐謫栴}的一些較好算法（稱為偽多項(xiàng)式時(shí)間算法）。讀者不難發(fā)現(xiàn)， Bin—packing問題至少不會(huì)比 3—?jiǎng)澐謫栴}容易。 例 （排序問題 —Scheduling） 擬用 m臺(tái)機(jī)器加工 n個(gè)零件，對(duì)零件的加工可以提出各種不同的附加條件，希望排出一個(gè)加工順序（或時(shí)間表），使在某種衡量標(biāo)準(zhǔn)下所求得的加工順序?yàn)樽罴?。按目前流行的做法，人們常用三個(gè)參數(shù) α， β， υ來(lái)描述一個(gè)特定的排序問題，并記為 α/β/υ排序問題，其中 α描述機(jī)器情況， β描述加工零件時(shí)的附加要求或附加條件， υ表示衡量排序好壞的標(biāo)準(zhǔn)。有關(guān)排序問題，目前已有十多本專著及至少數(shù)千篇論文，這里不準(zhǔn)備細(xì)述專業(yè)知識(shí)，僅以幾個(gè)排序問題模型為例，來(lái)分析其計(jì)算復(fù)雜性。在這一模型中， α=Jm， J代表一類被稱為 Job shop的問題， m表示有 m臺(tái)機(jī)器。 β=no wiat，表示任一工件在開始第一道工序加工后不允許中間等待，直到它的各道加工均被完成。第八章例 （軋鋼問題）就是 Jm/no wait/Cmax排序問題的一個(gè)實(shí)例。 P2//Cmax問題是 NP完全。β=Φ，表示工件加工沒有附加要求或條件。容易看出，這一問題至少不會(huì)比劃分問題容易，故不可能是 P問題。但一般地講，事情決非如此簡(jiǎn)單，要將某一 NP完全問題多項(xiàng)式時(shí)間轉(zhuǎn)化為我們要研究的問題，常常需要用到一些巧妙而又精細(xì)的技巧。 討論 1/rj, prmp/ 排序問題，我們將證明它是 NP完全的，這是一個(gè) 一臺(tái)機(jī)器的排序問題，待加工的工件 Tj有一個(gè)準(zhǔn)備時(shí)間 rj， rj≥0，僅當(dāng) t≥rj時(shí) 它才能被加工。各工件的重要程度不同，對(duì)每一 Ti有一權(quán)因子 wj。 1njjjwC??jjwC?這一問題很難直接利用前面提到過的那些 NP完全問題來(lái)證明其 NP完全性。 例 （三元?jiǎng)澐謫栴}） 給定 3t個(gè)正整數(shù)的集合 {a1,…, a3t}，令 ，問是否能將此集合劃分成兩兩不相交的 t個(gè)子集， 使得每一子集恰含總和為 b的三項(xiàng)，（標(biāo)準(zhǔn)型中可設(shè) ）。 jjwC?對(duì)例 ，作如下的 1/rj , prmp/ 排序問題實(shí)例，該例中共有 4t－ 1項(xiàng)加工任務(wù)。這樣，這 t－ 1項(xiàng)工件應(yīng)分別在 [ b, b + 1], [2b + 1, 2b + 2],… [ ( t－ 1) b +1－ 2, (t－ 1)b + t－ 1]時(shí)段內(nèi)加工。 jjwC?（ 2）若三元分劃問題有解，可利用每一時(shí)段加工一個(gè)子集中的工件，此時(shí)不必中斷任何工件的加工，而 若三元分劃問題無(wú)解，則必有 Z Z是與排序無(wú)關(guān)的一個(gè)常數(shù)，而 =Z當(dāng)且僅當(dāng)三元?jiǎng)澐钟薪狻? 分枝定界法與隱枚舉法（精確算法） 在上一章中我們已經(jīng)看到，整數(shù)規(guī)劃、 0—1規(guī)劃都是 NP完全的。這樣，一方面不可能找到求解的有效算法，另一方面枚舉所有可能情況的辦法對(duì)規(guī)模較大的例子又無(wú)法實(shí)現(xiàn)。前面已經(jīng)指出，所謂指數(shù)算法實(shí)際上是指在最壞的情況下可能達(dá)指數(shù)時(shí)間的計(jì)算量，它并不排斥在大多數(shù)情況下算法表現(xiàn)出好的性態(tài)。這一實(shí)例鼓舞人們?nèi)?duì)其余問題尋找類似的算法。但人們的努力并沒有完全白費(fèi)，有些 NP完全問題已有了一些在實(shí)際應(yīng)用時(shí)值得一試的求解算法。 一、分枝定界法 例 某房屋出租單位有活動(dòng)資金 91萬(wàn)元，擬購(gòu)房出租，現(xiàn)有兩種房屋，一種每套 13萬(wàn)元，只有四套；另一種每套 ，數(shù)量不限。第一種房月租金收入為 2022元，第二種房月租金收入為 3000元。 分析： 若將變量四舍五入化整，雖滿足了變量的整數(shù)要求，但一方面得到的有可能不是可行解，另一方面即使得到的是可行解，也不能保證它是最優(yōu)解。對(duì)本例，因只有兩個(gè)變量，共有四種可能，即化整為（ 2,3），（ 2,4），（ 3,3），（ 3,4），其中只有 x1=2，x2=3是可行的，目標(biāo)值為 Z=，并非最優(yōu)解（最優(yōu)解為 x1=4， x2=2，Z*=）。 求解松馳線性規(guī)劃雖無(wú)法找出最優(yōu)整數(shù)解，但卻指出了該實(shí)例目標(biāo)函數(shù)值的一個(gè)下界（指標(biāo)準(zhǔn)型 min問題）。 下面介紹一種分枝定界技巧 從（ ILP）的松馳線性規(guī)劃的最優(yōu)解中選取一個(gè)非整分量（通常選離整數(shù)最遠(yuǎn)的分量），例如我們選取 x1，考察兩個(gè)新的松馳線性規(guī)劃。 （ LP1）的最優(yōu)解為（ 2， ），最優(yōu)目標(biāo)值為 ，其可行域中不包含具有更大目標(biāo)值的可行解，（ LP2）的最優(yōu)解為（ 3,），最優(yōu)目標(biāo)值為 。 （ LP4）無(wú)可行解，（ LP3）有最優(yōu)解（ 4, 2），該分枝的最優(yōu)目標(biāo)值 Z=。另一方面，又同時(shí) 求得一整數(shù)解其目標(biāo)值 Z=，故已有整數(shù)最優(yōu)解目標(biāo)值的一個(gè)下界（ LB） Z= 至此，我們已運(yùn)用分枝定界法求得了整數(shù)規(guī)劃例 ，整個(gè)過程見圖 。 為了讓讀者看清在各種不同類型的問題中是如何使用分枝定界法的，下面 我們?cè)倥e一例： 例 要調(diào)配紅、藍(lán)、白、黑、黃五種顏色的油漆。問應(yīng)當(dāng)如何調(diào)配較好（要求先建立模型）。如果該工人只需調(diào)配一次而不必考慮以后的工作，問題可以作類似的討論，（注：此工人只有一塊調(diào)色板）。相應(yīng)的費(fèi)用矩陣為 6 18 4 87 17 3 74 5 4 520 19 24 228 8 16 6MMMMM??????????紅 藍(lán) 白 黑 黃 紅 蘭 白 黑 黃 其中，“ M”表示充分大的正實(shí)數(shù)。從最后一個(gè)矩陣立即可得此調(diào)色問題的一個(gè)最優(yōu)順序：紅 → 藍(lán) → 黑 → 白 → 黃（黃 → 紅）。事實(shí)上，調(diào)色問題可看成旅行商問題的實(shí)例。例如，如果將例 1 2 3 4 5 1 4 8 6 8 42 5 7 1 1 1 3 53 1 1 6 8 4 44 5 7 2 2 25 1 0 9 7 5 5MMA MMM????? ????? ???????____________ 共計(jì)減 20 1 2 3 4 5 11 0 4 2 42 0 2 6 83 7 2 4 04 3 5 0 05 5 4 2 0MMA MMM???????????相應(yīng)的指派 1→ 2， 3→ 5→ 4不構(gòu)成一個(gè)旅行回路（哈密頓圈），它含有兩個(gè)子圈（ 1,2）和（ 3,5,4）。如對(duì)長(zhǎng)陣 A，由于從其相應(yīng)的等價(jià)問題矩陣 A1中可找到費(fèi)用為 0的最優(yōu)指派，故可知 20是其總費(fèi)用的一個(gè)下界。 兩種情況又可分別變換為 （情況 1）?。?14） ????????????????MMMMMMMMMMMMMMMMM00000000求得（ 1， 4， 5， 3， 2） （情況 2）（ 14） ????????????????MMMMMMMMMMMM2220003000000求得（ 1， 4， 5， 3， 2） 兩個(gè)旅行圈的費(fèi)用均為 26（指在原問題中）。 需要指出的是，雖然在上面的實(shí)例中計(jì)算量并不是很大，但對(duì)于 n較大的實(shí)例，用以上介紹的分枝定界法求解旅行商問題效果并不理想，如何構(gòu)造實(shí)用效果更好的分枝定界算法仍然是一個(gè)值得進(jìn)一步研究的問題。這里，我們將采用節(jié)省部分非必要運(yùn)算的所謂隱枚舉法來(lái)求解它。求解的全過程見表 所示，例如，點(diǎn)（ 0， 0， 1）的目標(biāo)為 5且滿足所有約束，故此后僅當(dāng)目標(biāo)值大于 5時(shí)才檢驗(yàn)是否滿足各約束，此類條件在隱舉枚法中被稱為過濾條件。這時(shí)，可從目標(biāo)值最大的點(diǎn)試起，只要發(fā)現(xiàn)使目標(biāo)值最大的可行解，搜索立即停止。例如在本例中， x2的系數(shù)為 2，用（ ）代替 x2，將目標(biāo)函數(shù)改寫 取 0當(dāng)且僅當(dāng) x2取 1，而 取 1僅當(dāng) x2取 0。約束條件中的 x2用 代替，搜索時(shí)先檢驗(yàn)系數(shù)大找量取 1的點(diǎn)。 ??21 x?? ???232 ,2523 xxxx?2x?ix?2x?2x當(dāng)然，由于 01規(guī)劃是 NP完全的，上述算法能否真正求得最優(yōu)解仍然是沒有保證的，全靠碰運(yùn)氣。如果一個(gè)隱枚舉法能對(duì)絕大多數(shù)實(shí)例在較快時(shí)間內(nèi)求出最優(yōu)解，它仍不失為一個(gè)好算法，至少?gòu)膶?shí)用角度上講，它一定會(huì)被人們廣泛地接受。下面將介紹求解復(fù)蓋問題的隱枚舉法。 圖 G=（ V， E）的頂點(diǎn)與邊 ei稱為相關(guān)聯(lián)的，若 是邊 ei的兩個(gè)頂點(diǎn)之一。在引入關(guān)聯(lián)關(guān)系后，圖 G可以用一個(gè)被稱為關(guān)聯(lián)矩陣的 m n階矩陣代數(shù)地表示，其中 m=│ V│, n=│ E│ 。 至此，關(guān)于復(fù)蓋的定義仍然是基于圖的概念給出的，事實(shí)上，我們還可以給出更一般的定義。 A、 B中的元素之間可以存在某種關(guān)系（關(guān)系可根據(jù)需要自行規(guī)定），記為 R，并稱之為關(guān)聯(lián)關(guān)系。 ? ?maaA ,1 ?? ? ?nbbB ,1 ??? ?ijrR ? jia Re（ I）設(shè) C= 為 A的一個(gè)子集，若對(duì) B中的任一元素 bj，總有 ，使得 ，則稱子集 C復(fù)蓋 B，記為 CRB。 例 假設(shè)我們正在餐廳點(diǎn)菜，希望所點(diǎn)的菜能包含我們所關(guān)心的某幾種營(yíng)養(yǎng)成分，同時(shí)又價(jià)格最低，例如，餐廳共有六種菜，記為 A={a、 b、c、 d、 e、 f}，我們希望菜中包含的營(yíng)養(yǎng)成分為 B=（蛋白質(zhì)、淀粉、維生素、礦物質(zhì)），引入關(guān)聯(lián)矩陣 R=（ rij）， rij=1當(dāng)且僅當(dāng)菜 i含營(yíng)養(yǎng)成分 j。 不難看出，例 01規(guī)劃問題的實(shí)例。 現(xiàn)介紹根據(jù)關(guān)聯(lián)信息，利用代數(shù)方法在計(jì)算機(jī)上求解復(fù)蓋問題的直接解法。 定義 （控制關(guān)系）（ i）若對(duì)所有的 j，由 rkj=1且 P（ ai） ≤P（ ak）， 則稱格 ai控制格 ak簡(jiǎn)記 aiak.。 易見，若存在兩個(gè)格 ai、 ak、 ai ak，則 ak在尋找最小復(fù)蓋時(shí)可以不必考慮，因?yàn)?ak必可用 ai代替，且 ai的價(jià)格不會(huì)高于 ak的價(jià)格。此外，若 A中存在著復(fù)蓋某點(diǎn)的本質(zhì)格，則此格必出現(xiàn)在任一復(fù)蓋中，否則，該點(diǎn)將無(wú)法被復(fù)蓋。 法則一 刪去所有本質(zhì)行（格）及一切在相應(yīng)行中已有 1的列（這些點(diǎn)已被復(fù)蓋）。 法則二 若只要求求出一個(gè)最小復(fù)蓋，則可刪去一切控制列（點(diǎn)），因?yàn)樗鼈儽貢?huì)被復(fù)蓋。 例 求解復(fù)蓋問題，其關(guān)聯(lián)矩陣及價(jià)格表為 ? ?iaP ai b1 b2 b3 b4 b5 b6 ????????????????????000100100100000001010011101000111000231432654321aaaaaa解： 步 1 a3是復(fù)蓋 b2的本質(zhì)格。 上述方法有時(shí)也會(huì)失效（從而引出復(fù)蓋問題的 NP完全性），例如復(fù)蓋問題 1 2 3 4() iiP a a b b b b12341 1 0 0 11 0 0 1 11 0 1 1 01 1 1 0 0aaaa????????????其中既無(wú)控制列或控制行，又無(wú)本質(zhì)行，這樣的關(guān)系矩陣常被稱為循環(huán)矩陣，此時(shí)要求解復(fù)蓋問題只好采用分枝辦法。 （分枝 2） 如不取 a1，問題化為 1 2 3 4()iiP a a b b b b23