【正文】 第九章 離散優(yōu)化模型及算法設(shè)計(jì) 浙江大學(xué)數(shù)學(xué)建?；? 167。 某些 P問(wèn)題及其算法 在上一章中 ,我們介紹了與計(jì)算復(fù)雜性有關(guān)的一些基本概念 .人們發(fā)現(xiàn) ,在離散問(wèn)題中存在著兩個(gè)互不相交的類： P類與 NP完全類（若 P≠ NP）。前者具有求解的有效算法而后者不可能有這種算法。從這一點(diǎn)上講， P問(wèn)題可以看成是一類具有良好性質(zhì)而又較容易求解的問(wèn)題，而 NP完全問(wèn)題則是固有地難解的。 在 167。 ，有著廣泛應(yīng)用背景的線性規(guī)劃問(wèn)題是一個(gè) P問(wèn)題。這樣，作為線性規(guī)劃子問(wèn)題的運(yùn)輸問(wèn)題及作為運(yùn)輸問(wèn)題子問(wèn)題的指派問(wèn)題自然更是 P問(wèn)題。雖然從平均的角度講，人們似乎更常遇到 NP完全問(wèn)題，但 P仍不失為一個(gè)十分重要的問(wèn)題類。一方面，很多 P問(wèn)題象線性規(guī)劃一樣有著極廣泛的應(yīng)用前景，且它們本身又是十分有趣的；另一方面，它們也是研究一些更為復(fù)雜、難解的問(wèn)題時(shí)經(jīng)常被采用的研究工具。在本章中，將再介紹一些經(jīng)常遇到的 P問(wèn)題并給出求解它們的有效算法。 一、擬陣問(wèn)題及貪婪算法 在 P類中又存在著一個(gè)被稱為擬陣的具有更為良好性質(zhì)的問(wèn)題類，其中的任一問(wèn)題均可用一種被稱為貪婪法的方法來(lái)求解，而這一性質(zhì)并不是所有的 P問(wèn)題都具有的。 例 （最小生成樹(shù)問(wèn)題 ——MST） 給定一連通圖 G=（ V， E）， ，有一表示邊長(zhǎng)的權(quán) C（ e）（表示頂點(diǎn)間的距離或費(fèi)用），求此圖的具有最小總權(quán)的生成樹(shù)。 ???e此問(wèn)題的標(biāo)準(zhǔn)形式為給定一完全圖 G，其每邊賦有一權(quán)數(shù)，求此完全圖的最小生成樹(shù)。所謂樹(shù)是指連通而無(wú)圈的圖，單獨(dú)的一個(gè)點(diǎn)也可看成一顆樹(shù)。樹(shù)用 (U， T)表示， U為樹(shù)的頂點(diǎn)， T為樹(shù)的邊集。不相交的樹(shù)的集合被稱為森林。一個(gè)連通圖的生成樹(shù)是指圖中具有最多邊數(shù)的一棵樹(shù)。容易證明，對(duì)于一個(gè)連通圖 G， G 的任一生成樹(shù)必有 ∣ V∣ 1條邊。 求解最小生成樹(shù)的算法主要依據(jù)下面的定理： 定理 設(shè) {（ V1， T1）， … （ Vk ,Tk） }為連通圖 G中的森林， V1 U V2…U Vk=V。 … k,若僅有一個(gè)頂點(diǎn)在 Vi中的具有最小權(quán)的邊為（ ,u），則必有一棵 G的最小生成樹(shù)包含邊（ ,u）。 ,1??i??根據(jù)定 1可以作了如下算法：任選一點(diǎn) ，令 若 V1=V，停；否則，找出僅有一個(gè)頂點(diǎn)在 V1中的邊里具有最小權(quán)的邊（ ,u），設(shè)，將 u加入 V1（ ,u）加入 T。重復(fù)上述步驟，直到 V1=V。 1? ? ?11: , : .VT?? ? ?? ?證明 ：設(shè) G的一棵最小生成樹(shù)（ V， T）不含（ ,u）。將（ ,u）加入 T，由于（ V， T）是生成樹(shù)， T U（ ,u）中含有過(guò)（ ,u）的唯一的圈。不妨設(shè) ，則 ，此圈中的點(diǎn)不全由 Vi中的點(diǎn)組成 ,因此必存在圈中的另一邊 。刪去邊 得到一新的生成樹(shù)（ V，T1）， T1= ，須其總權(quán)不超過(guò)（ V， T）的權(quán) ,即（ V， T）是包含邊（ ,u）的最小生成樹(shù)。 iV?? iV??? ?39。 39。 39。 39。, iiuu? ? ? ?? ? ?39。39。u?? ?? ? ? ?39。39。, uu????? ?? ??例 求圖 G的最小生成樹(shù)。 解 ： 不妨從頂點(diǎn)開(kāi)始尋找。 標(biāo)號(hào) 1，先加入 （因?yàn)檫厵?quán) 最?。?， 標(biāo)號(hào) 2。再加入 標(biāo)號(hào) 3。 … ，每次加入一條一頂點(diǎn)已標(biāo)號(hào)加一頂點(diǎn)未標(biāo)號(hào)而又具有最小權(quán)的邊，直到所有頂點(diǎn)均標(biāo)號(hào)為止。找到的最小生成樹(shù)已用又線標(biāo)在圖 。 ? ?1 1 1,V ??? 2? ? ?12??2? 44??容易看出算法的計(jì)算量為 O∣ (V)2∣ ，所以此算法是有效算法，若 G具有O（ ）條邊，其中 n=∣ V∣ ，計(jì)算量的界還是不能改進(jìn)的，因?yàn)槊織l邊至少應(yīng)被檢查一次。 2nC由例 ，算法執(zhí)行的每一步均加入一條可以加入的（即不生成圈的）具有最小權(quán)的邊，而不去考慮它對(duì)以后選取的影響，這種算法被稱為貪婪算法。 例 (入樹(shù)問(wèn)題 ) 給出一個(gè)有向圖 G=（ V， A），對(duì) A中的每一條孤 e，給出一個(gè)權(quán) C（ e），求 A的一個(gè)具有最大權(quán)（或最小權(quán)）的子集 B，要求 B中任意兩條孤都沒(méi)有公共的終點(diǎn)。 考察下面的入樹(shù)問(wèn)題實(shí)例： 例 給出有向圖 G=（ V， A） （圖 ） ，孤上標(biāo)出的數(shù)字為該邊的 權(quán)，求此圖具有最大權(quán)的入樹(shù)。 解：由于入樹(shù)不能包含具有公共終點(diǎn)的孤，故對(duì)每一頂點(diǎn) 只能選取一條入孤。為使選出的弧具有最大權(quán)，只需要對(duì)每一頂點(diǎn)選取權(quán)最大的入孤，可用計(jì)算量為 O（ ∣ V∣∣ E∣ ）的貪婪法求解，具有最大權(quán)的入樹(shù)為 。 i?? ? ? ? ? ? ? ? ? ?? ?1 2 2 1 2 4 4 5 5 3, , , , , , , , ,? ? ? ? ? ? ? ? ? ?類似地，出樹(shù)問(wèn)題也可以用貪婪法求解。 例 (矩陣擬陣問(wèn)題 )給出一個(gè)矩陣 Amxn，記其 n個(gè)列向量為 e1,… ， en。設(shè)對(duì)每一列向量 en已指定一權(quán) C（ en）求 的一個(gè)線性無(wú)關(guān)的子集，它具有最大的權(quán)和。 ? ? ? ?1, ,i in?易見(jiàn)，這一問(wèn)題也可以用貪婪法求解。集合 的線性無(wú)關(guān)的子集被稱為獨(dú)立子集，利用貪婪法必可求得具有最大權(quán)的獨(dú)立子集，可用線性代數(shù)知識(shí)加以證明 （見(jiàn)習(xí)題 1） 。 ? ? ? ?1 , ,i in?例 求矩陣 A的列向量具有最大權(quán)和的獨(dú)立子集 7*45762101543100012731214531011?????????????AC(ei)＝ 8 4 7 5 2 6 4 解： 采用貪婪法，先取權(quán)最大的列 e1，同時(shí)對(duì) A作高斯消去，逐次加入 線性無(wú)關(guān)的向量： A的列向量中具有最大權(quán)的獨(dú)立子集為 。 ? ?1 3 5 4? ? ?取 e6 取 e4 取 e3 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 4 5 1 1 0 2 0 5 4 3 1 0 0 0 3 3 4 2 1 1 0 4 5 3 1 0 1 1 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 1 2 3 1 1 1 0 5 4 3 1 0 0 0 3 3 4 2 1 1 0 4 5 3 1 0 1 1 A ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 4 / 9 0 4 / 19 4 / 9 0 2 0 4 / 5 1 4 / 3 4 / 1 0 0 0 3 3 4 2 1 1 0 4 5 3 1 0 1 1 定義 (擬陣 ) 設(shè) E是一個(gè)有限集， γ為 E的部分子集構(gòu)成的封閉系統(tǒng)（即若 ，則必有 ）。若 M=（ E， γ）上的離散優(yōu)化問(wèn)題的每一實(shí)例均可用貪婪算法求出最優(yōu)解，則稱 M為一擬陣。（注： γ被稱為獨(dú)立系統(tǒng)）。 ,39。AA???? 39。A ??現(xiàn)以矩陣擬陣為例，對(duì)定義 。 對(duì)矩陣擬陣的每一實(shí)例， E={e1,… en}為矩陣列向量的集合， γ為 E的線性無(wú)關(guān)子集構(gòu)成的系統(tǒng)，稱為獨(dú)立系統(tǒng)，其元素被稱為獨(dú)立子集。由于 E的任一線性無(wú)關(guān)子集的子集也是 E的線性無(wú)關(guān)子集，故獨(dú)立系統(tǒng) γ是封閉的。又由于這一離散優(yōu)化問(wèn)題的任一實(shí)例都可用貪婪法求解，故構(gòu)成一擬陣，被稱為矩陣擬陣。例 ，例 。 擬陣問(wèn)題（或稱擬陣結(jié)構(gòu)） 有一個(gè)明顯而又本質(zhì)的特性，其任一極大獨(dú)立子集中包含著相同個(gè)數(shù)的元素，從而可以引入基的概念。例如，矩陣列向量的所有線性無(wú)關(guān)極大組均具有相同的向量個(gè)數(shù)，這就導(dǎo)出了基 ——即矩陣列秩的概念。對(duì)于圖擬陣，每一極大獨(dú)立集均為一生成樹(shù)，其邊數(shù)均為|V|1。對(duì)于劃分?jǐn)M陣，孤集被劃分成個(gè) |V|個(gè)子集，每一子集由指向同一頂點(diǎn)的孤組成。顯然，任一極大獨(dú)立集應(yīng)在每一子集中取一條孤，故其基數(shù)為頂點(diǎn)個(gè)數(shù)。 我們不加證明地引入下面的定理，雖然其證明并不十分困難。 定理 E為一有限集合，為 E的部分子集構(gòu)成的封閉獨(dú)立系統(tǒng)。以下 兩個(gè)條件均為 M=(E, y)構(gòu)成擬陣（即其上的優(yōu)化問(wèn)題可用貪婪法求解） 的充分必要條件： （條件 2） 若 I、 I?均為 A的兩個(gè)極大獨(dú)立集，則 |I|=|I’|。 AE??（條件 1） 若 I、 I? |I||I’|，則必可找到一個(gè)元素 e ，使得 （注： | |表示元素個(gè)數(shù)） 39。I? Ie ???,??二、兩分圖匹配問(wèn)題與增廣路算法 在上一小節(jié)中我們已經(jīng)看到，有些 P問(wèn)題可以用極為簡(jiǎn)單的貪婪法求解。但對(duì)絕大多數(shù)的 P問(wèn)題來(lái)說(shuō)，這一結(jié)果并不成立，只能根據(jù)其本身的結(jié)構(gòu)，去尋找求解它的獨(dú)特算法。下面，我們將介紹幾個(gè)這樣的 P問(wèn)題。 例 （婚姻問(wèn)題） 在遙遠(yuǎn)的地方有一位酋長(zhǎng)，他想把三個(gè)女兒嫁出去。假定三個(gè)女兒為 A、 B、 C，三位求婚者為 X、 Y、 Z。每位求婚者對(duì) A、 B、C愿出的財(cái)禮數(shù)視其對(duì)她們的喜歡程度而定： 問(wèn)酋長(zhǎng)應(yīng)如何嫁女，才能獲得最多的財(cái)禮（從總體上講，他的女婿最喜歡 他的女兒）。 ??????????7412810272653zyxCBA例 ，但它也可以看成是兩分圖賦權(quán)匹配問(wèn)題的實(shí)例。 用三個(gè)點(diǎn)表示酋長(zhǎng)的三個(gè)女兒，將它們放在一邊。再用三個(gè)點(diǎn)表示求婚者，將它們放在另一邊。在有可能結(jié)婚的兩人之間畫一條邊，并在邊上寫上求婚者對(duì)這種結(jié)婚愿付出的財(cái)禮數(shù)，得到圖 。圖 ，它的頂點(diǎn)可以分成兩個(gè)子集，只有分屬不同子集的點(diǎn)才可能有邊相連（但也可以無(wú)邊），這樣的圖稱為兩分圖。 定義 (匹配 ) 圖 G的一個(gè)匹配是指邊集 E的一個(gè)子集 M， M中的任意兩條邊 均不具有公共的頂點(diǎn)。 容易看出，酋長(zhǎng)要解的問(wèn)題是在兩分圖圖 匹配，讀者不難由此得到一般兩分圖最大權(quán)匹配問(wèn)題的數(shù)學(xué)模型。 由于兩分圖最大權(quán)匹配問(wèn)題等價(jià)于指派問(wèn)題，所以它是一個(gè) P問(wèn)題。對(duì)于這一 P問(wèn)題，我們是否也能象前面一樣用貪婪法求解呢？如果用貪婪法求解例 ，則有 C嫁 y（ 28頭），去除 C、 y及相應(yīng)邊（一夫一妻）；再將 B嫁x（ 5頭），去除 B、 x及相應(yīng)邊；最后， A只能嫁 Z（ 1頭）。共得財(cái)禮 34頭牛。事實(shí)上，酋長(zhǎng)的女兒只有六種嫁法（ 3?。?，比較所有方案，發(fā)現(xiàn) C嫁x、 A嫁 y、 B嫁 z最好（ y幾乎差不多同樣喜歡 C和 A，而 z則明顯喜歡 C而不太喜歡 A），可得財(cái)禮 57頭牛。雖然后一算法不是多項(xiàng)式時(shí)間的，對(duì)待嫁者數(shù)量稍大的問(wèn)題無(wú)法求得結(jié)果，但對(duì)本例，它至少表明用貪婪法沒(méi)有求得最優(yōu)解，因而兩分圖最大權(quán)匹配問(wèn)題不是擬陣問(wèn)題（或者講不具有擬陣結(jié)構(gòu)），從而，一般賦權(quán)圖上的最大權(quán)匹配問(wèn)題更不是擬陣問(wèn)題。用他的名字命名的 O（ n4）算法，由于他的算法較復(fù)雜 ,本書不準(zhǔn)備作詳細(xì)介紹 ,有興趣的讀者可查閱 “組合最優(yōu)化，算法和復(fù)雜性”一書第十一章。至于兩分圖賦權(quán)匹配問(wèn)題，由于它與指派問(wèn)題的等價(jià)性，完全可以用計(jì)算量 O（ n3）的匈牙利方法求解，也可以化為后面的網(wǎng)絡(luò)流問(wèn)題求解。 如果所有邊的權(quán)均為 1，則最大權(quán)匹配化成最大匹配問(wèn)題（即求邊數(shù)最多 的匹配）。對(duì)于這一較為簡(jiǎn)單的子問(wèn)題，存在著增廣路算法。 定義 設(shè) M是圖 G的一個(gè)匹配， M中的邊稱為匹配邊，其端點(diǎn)稱為一對(duì)配偶（其它邊稱為未匹配邊或自由邊）。 V中已有配偶的點(diǎn)稱為已蓋點(diǎn)，否則稱為未蓋點(diǎn)。 定義 依次取未匹配邊、匹配邊的路稱為交錯(cuò)路。 由未蓋點(diǎn)到未蓋點(diǎn)的交錯(cuò)路稱為增廣路。易見(jiàn)，增廣路中未匹配邊的數(shù)目比匹配邊的數(shù)目多一條，且交換增廣路中的未匹配邊與匹配邊可以得到一個(gè)多一條邊的匹配。 例 在圖 （ a）中，用雙線劃出的邊組成該圖的一個(gè)極大匹配。由未蓋點(diǎn) 出發(fā)，可作出增廣路 ，從而可得到一個(gè)增加一條匹配邊的更大匹配，如圖 （ b）所示。此時(shí)，圖中雖然仍存在未蓋點(diǎn)