《云南大學(xué)報(bào)告問(wèn)題、模型與算法.ppt》由會(huì)員分享，可在線閱讀，更多相關(guān)《云南大學(xué)報(bào)告問(wèn)題、模型與算法.ppt（57頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

問(wèn)題、模型與求解算法,云南大學(xué)數(shù)學(xué)系李建平二OO九年十一月,內(nèi)容摘要,基礎(chǔ)知識(shí)最小支撐樹(shù)問(wèn)題最短路問(wèn)題匹配問(wèn)題歐拉問(wèn)題中國(guó)郵遞員問(wèn)題一些可計(jì)算性為NP-完備的組合最優(yōu)化問(wèn)題及數(shù)學(xué)模型,一、基礎(chǔ)知識(shí),1.1圖與支撐子圖定義1.1所謂一個(gè)（無(wú)向）圖是指給了一個(gè)集合V，以及V中的不同元素的無(wú)序?qū)?gòu)成的集合E，并記圖為G=(V，E)。稱V中的元素為圖G的頂點(diǎn)，稱E中的元素為圖G的邊。連接兩頂點(diǎn)u和v的邊記作uv（或者vu），也稱邊uv（或者vu）與頂點(diǎn)u,v相關(guān)聯(lián)，同時(shí)稱兩頂點(diǎn)u和v是相鄰的。,,,,,,,,,,太原,重慶,武漢,南京,徐州,連云港,上海,鄭州,石家莊,塘沽,青島,濟(jì)南,天津,北京,圖1.1,定義1.2所謂一個(gè)有向圖是指給了一個(gè)集合V，以及V中的不同元素的有序?qū)?gòu)成的集合A，并記有向圖為D=(V，A)。稱V中的元素為有向圖D的頂點(diǎn)，稱A中的元素為有向圖D的弧。以頂點(diǎn)u為起點(diǎn)和以頂點(diǎn)v為終點(diǎn)的弧記作（u，v），也稱與?。╱，v）與頂點(diǎn)u,v相關(guān)聯(lián)。,,,,,,,,,v3,v1,v2,v4,v6,v5,圖1.2,定義1.3給定兩個(gè)圖G=(V,E)和H=(V*,E*)，稱H是G的一個(gè)支撐（生成）子圖，如果V*=V和E*E。1.2圖的連通性定義1.4（路）給定圖G=(V,E)，一個(gè)點(diǎn)、邊交錯(cuò)的序列P=（v0,e1,v1,e2,v2，e3,v3,…,vk-1,ek,vk)，如果滿足ei=vi-1vi,i=1,2,…,k,則稱P為一條連結(jié)v0和vk的路，簡(jiǎn)記為P=v0v1v2v3…vk-1vk；稱v0，vk分別稱為路P的起點(diǎn)和終點(diǎn)，其余稱為中間點(diǎn)。,定義1.5（回路）設(shè)P為一條連結(jié)v0和vk的路，如果v0=vk，稱該路P為回路；如果v0≠vk，稱該路P為(嚴(yán)格的)路。定義1.6（圈）如果路P除起點(diǎn)和終點(diǎn)相同，中間所含的點(diǎn)均不相同，稱這樣的回路P為圈。定義1.7（連通圖）如果圖G中任意兩點(diǎn)之間均至少有一條路相連，稱G為連通圖；否則稱圖為不連通圖。問(wèn)題1.1：給定圖G，問(wèn)G是連通的嗎？,二、最小支撐樹(shù)問(wèn)題,2.1樹(shù)定義2.1一個(gè)無(wú)圈的連通圖稱為樹(shù)。樹(shù)具有如下一些性質(zhì)：性質(zhì)2.1設(shè)圖G=（V，E）是一棵樹(shù)，n≥2，則圖G中至少有兩個(gè)懸掛點(diǎn)。性質(zhì)2.2圖G=（V，E）是一棵樹(shù)的充要條件是G不含圈，并且有且僅有n-1條邊。性質(zhì)2.3圖G=（V，E）是一棵樹(shù)的充要條件是G是連通圖，并且有且僅有n-1條邊。性質(zhì)2.4圖G是一棵樹(shù)的充分必要條件是任意兩個(gè)頂點(diǎn)之間有且僅有一條路。,2.2支撐樹(shù)定義2.2設(shè)圖T=(V,E)是圖G=(V,E)的一個(gè)支撐子圖，如果圖T=(V,E‘)是一棵樹(shù)，那么稱T是G的一棵支撐樹(shù)。,,,,,,v6,v5,v2,v3,v4,v1,,,,,,圖2.1,（a）,（b）,v6,v5,v3,v1,v2,v4,2.3最小支撐樹(shù)問(wèn)題定義2.3設(shè)有圖G=（V，E；w），如果對(duì)于G中的每一條邊vivj，相應(yīng)地有一個(gè)數(shù)wij，那么稱這樣的圖G為賦權(quán)圖，wij稱為邊vivj的權(quán)。這里所指的權(quán)，是具有廣義的數(shù)量值。根據(jù)實(shí)際研究問(wèn)題的不同，可以具有不同的含義。例如長(zhǎng)度，費(fèi)用、流量等等。,定義2.4如果圖T=（V，E）是賦權(quán)圖G的一棵支撐樹(shù)，那么E‘中所有邊的權(quán)重之和稱為支撐樹(shù)T的權(quán)重，記作w(T)。如果圖G中支撐樹(shù)T*的權(quán)重w(T*)是在G的所有支撐樹(shù)T中的權(quán)重達(dá)到最小者，即w(T*)=min{w(T)|T為G的支撐樹(shù)}，那么稱T*是G的一棵最小支撐樹(shù)。類(lèi)似可定義最大支撐樹(shù)問(wèn)題。問(wèn)題2.1：給定圖G，如何求G的一棵最小支撐樹(shù)？,常用的有破圈算法和避圈算法：Algorithm破圈算法Input:賦權(quán)圖G=（V，E；w）Output:G的最小支撐樹(shù)TBegin①在圖中尋找一個(gè)圈。若不存在圈，則已經(jīng)得到最小支撐樹(shù)或說(shuō)明該圖不連通，后者不存在支撐樹(shù)（當(dāng)然沒(méi)有最小支撐樹(shù)）；②若存在圈，去掉該圈中權(quán)數(shù)最大的邊；③反復(fù)重復(fù)①、②兩步，直到找到最小支撐樹(shù)或說(shuō)明該圖不連通（故沒(méi)有最小支撐樹(shù)）。End,,,,,v6,v5,v2,v3,v4,（a）,v1,6,2,7,5,3,5,4,4,,,,,,v3,v2,v1,v4,v6,v5,5,1,3,1,4,2,（b）,圖2.2,避圈算法：從圖中依次尋找權(quán)重較小的邊，尋找過(guò)程中，節(jié)點(diǎn)不得重復(fù)，即不得構(gòu)成圈。注意在找較小權(quán)重邊時(shí)不考慮已選過(guò)的邊和可能造成圈的邊。如此反復(fù)進(jìn)行，直到得到最小支撐樹(shù)或者說(shuō)明該圖不連通，后者不存在支撐樹(shù)（當(dāng)然沒(méi)有最小支撐樹(shù)）。,2.4頂點(diǎn)加細(xì)限制性的最小支撐樹(shù)問(wèn)題定義2.5給定圖G=（V，E），在G的某些邊內(nèi)部增加一些頂點(diǎn)，所得到的新圖稱為原圖G的頂點(diǎn)加細(xì)圖（subdivision）。問(wèn)題2.2（頂點(diǎn)加細(xì)限制性的最小支撐樹(shù)問(wèn)題）給定賦權(quán)圖G=（V，E；w）及常數(shù)d，尋找圖G的一棵最小支撐樹(shù)T，在T上增加盡可能少的頂點(diǎn)，使得到新的（最小）頂點(diǎn)加細(xì)支撐樹(shù)T*上每條邊的權(quán)重不超過(guò)給定的常數(shù)d。,頂點(diǎn)加細(xì)限制性的最小支撐樹(shù)問(wèn)題的算法(1).利用已有的算法，對(duì)賦權(quán)圖G求最小支撐樹(shù)T，記T上權(quán)重大于d的邊為ei1,ei2,…,eik;(2).對(duì)邊eij按照下面方式插入insert(eij)頂點(diǎn)，其中當(dāng)w(eij)是d的倍數(shù)，取insert(eij)=[w(eij)/d]-1，當(dāng)w(eij)不是d的倍數(shù)，取insert(eij)=[w(eij)/d]；(3).輸出支撐樹(shù)T及插入的頂點(diǎn)。,定理2.1（李建平等，TheoreticalComputerScience410(2009),877-885）上述算法能夠求得頂點(diǎn)加細(xì)限制性的最小支撐樹(shù)問(wèn)題的最優(yōu)解，其算法復(fù)雜性就是求最小支撐樹(shù)問(wèn)題的算法復(fù)雜性。,問(wèn)題2.3（頂點(diǎn)加細(xì)限制性的支撐樹(shù)問(wèn)題）給定賦權(quán)圖G=（V，E；w；c），及常數(shù)B和d，尋找圖G的一棵支撐樹(shù)T，滿足（1）∑e∈Tw(e)≦B；（2）支撐樹(shù)T的頂點(diǎn)加細(xì)圖T*上每條邊的權(quán)重不超過(guò)給定的常數(shù)d。其目標(biāo)是使得∑e∈Tinsert(e)﹡c(e)到達(dá)最小。,定理2.2（李建平等，TheoreticalComputerScience410(2009),877-885）⑴頂點(diǎn)加細(xì)限制性的支撐樹(shù)問(wèn)題是NP-完備的；⑵上述問(wèn)題多項(xiàng)式等價(jià)于限制性的最小支撐樹(shù)問(wèn)題（SIAMJournalonComputing,Vol.33,no.2,261-268,2004）；⑶我們能夠設(shè)計(jì)多項(xiàng)式時(shí)間算法解決頂點(diǎn)加細(xì)限制性的支撐樹(shù)問(wèn)題的三種特殊情形，其算法復(fù)雜性就是求最小支撐樹(shù)問(wèn)題的算法復(fù)雜性。,三、最短路問(wèn)題,3.1最短路問(wèn)題定義3.1設(shè)有賦權(quán)圖G=（V，E;w），vs,vt是G中的兩個(gè)頂點(diǎn)，P是G中從vs到vt的任意一條路，路P的權(quán)重是指P中所有邊的權(quán)重之和，記作w(P)。問(wèn)題3.1（最短路問(wèn)題）在所有從vs到vt的路中，尋找一條權(quán)重最小的路P0，即w(P0)=minw(P)。P0稱為從vs到vs的最短路。P0的權(quán)重w(P0)稱為從vs到vt的距離，記作d（vs，vt）。類(lèi)似可定義賦權(quán)有向圖D中的最短路問(wèn)題。,3.2反圈定義3.2給定（無(wú)向）圖G=（V,E;w）,若SV，集合稱為由S確定的反圈（anticircuit）。類(lèi)似地，有向圖D=（V，A）,若SV，集合稱為由S確定的正向反圈，集合稱為由S確定的反向（或逆向）反圈。,3.3一般形式的反圈算法給定圖G=（V，E），設(shè)X(k),E(k)分別是V,E的子集合（初始k=0時(shí)，取X(0)是V的某個(gè)非空子集合,E(0)為空集合）。若由X(k)確定的反圈不為空集合，根據(jù)某些確定的限制條件，從該反圈中選取一條或多條邊，使得這些所選邊在V-X(k)中的端點(diǎn)互不相同。記被選邊的集合為F(k)，它們?cè)赩-X(k)中的端點(diǎn)集合為Y(k)。令對(duì)，重復(fù)上述過(guò)程或者終止。,3.4利用反圈算法求解最短路問(wèn)題(1)初值X(0)={vs}，L(vs)=0;(2)在中選一條邊vivj,使得L(vi)+w(vi,vj)=min{L(vi)+w(vi,vj)}令L(vj)=L(vi)+w(vi,vj)。(3)當(dāng)出現(xiàn)下面情形之一時(shí)，停止。當(dāng)，得到從vs到vt的最短路；當(dāng)，但是，說(shuō)明沒(méi)有從vs到vt的（最短）路。,3.5頂點(diǎn)加細(xì)限制性的最短路問(wèn)題定義3.3（頂點(diǎn)加細(xì)限制性的最短路問(wèn)題）給定賦權(quán)圖G=（V，E；w；vs,vt），及常數(shù)d，尋找圖G中從vs到vt的一條最短路P(vs,vt)，在P(vs,vt)上增加盡可能少的頂點(diǎn)，使得到的最短路P(vs,vt)上每條邊的權(quán)重不超過(guò)給定的常數(shù)d。,頂點(diǎn)加細(xì)限制性的最短路問(wèn)題的（標(biāo)號(hào)）算法：(1)取X(0)={vs}，E(0)=空集，L(vs)=0；(2)在X(k)確定的反圈中選取滿足條件的全部邊uv放入F(k)，這里u屬于X(k)，v不屬于X(k)L(u)+w(u,v)=min{L(u)+w(u,v)|u屬于X(k)，v不屬于X(k)}直到vt屬于某個(gè)X(k),轉(zhuǎn)(3)；或者無(wú)邊可選（停止）；,(3)當(dāng)存在vt屬于某個(gè)X(k)，在E(k)中（遞歸）去掉那些不能到達(dá)vt的頂點(diǎn)及其關(guān)聯(lián)的邊；(4)在新圖Gk=(X(k),E(k))中構(gòu)造新的權(quán)重，對(duì)邊e屬于E(k)，當(dāng)w(e)≦d時(shí)，取w(e)=0，當(dāng)w(e)>d時(shí)，取w(e)=insert(e)，其中當(dāng)w(e)是d的倍數(shù)，取insert(e)=[w(e)/d]-1，當(dāng)w(e)不是d的倍數(shù)，取insert(e)=[w(e)/d]；,(5)相應(yīng)地，在新圖Gk=(X(k),E(k))中，對(duì)邊e屬于E(k)，當(dāng)w(e)>d時(shí),插入insert(e)個(gè)新的頂點(diǎn)；(6)在新圖Gk=(X(k),E(k))中按照新的權(quán)重w，計(jì)算從vs到vt的一條最短路P(vs,vt)；(7)輸出最短路P(vs,vt)及插入的頂點(diǎn)，這里最短路P(vs,vt)關(guān)于w的權(quán)重就是所求路的權(quán)重，關(guān)于w的權(quán)重就是所增加定點(diǎn)的數(shù)目。,定理3.1（李建平等，submittedtoAlgorithmica2007）上述算法能夠求得限制性的最短路問(wèn)題的最優(yōu)解，其算法復(fù)雜性就是求最短路問(wèn)題的算法復(fù)雜性。,問(wèn)題3.4（頂點(diǎn)加細(xì)限制性的最短路問(wèn)題）給定賦權(quán)圖G=（V，E；w，c;vs,vt），及常數(shù)B和d，尋找圖G中從vs到vt的一條路P(vs,vt)，滿足（1）∑e∈P(vs,vt)w(e)≦B；（2）使得路P(vs,vt)的頂點(diǎn)加細(xì)圖中每條邊的權(quán)重不超過(guò)給定的常數(shù)d。其目標(biāo)是使得（費(fèi)用）∑e∈P(vs,vt)insert(e)﹡c(e)到達(dá)最小。,定理2.2（李建平等，submittedtoAlgorithmica，2007）⑴頂點(diǎn)加細(xì)限制性的最短路問(wèn)題是NP-完備的；⑵上述問(wèn)題多項(xiàng)式等價(jià)于限制性的最短路問(wèn)題（MathematicsofOperationsResearch,vol.17,no.1,36-42,1992）；⑶當(dāng)B表示圖G中從vs到vt的最短路長(zhǎng)度時(shí)，我們能夠設(shè)計(jì)多項(xiàng)式時(shí)間算法解決該問(wèn)題；⑷當(dāng)只計(jì)算頂點(diǎn)加細(xì)的數(shù)目時(shí)，我們能夠設(shè)計(jì)多項(xiàng)式時(shí)間算法解決該問(wèn)題。,四、匹配問(wèn)題,4.1背景在生活中經(jīng)常會(huì)遇到這樣的問(wèn)題，如某單位需要指派n個(gè)人去完成n項(xiàng)任務(wù)，每個(gè)人只做一項(xiàng)工作，同時(shí)，每項(xiàng)工作只由一個(gè)人完成。由于各人的專(zhuān)長(zhǎng)不同，每個(gè)人完成各項(xiàng)任務(wù)的效率也不同。于是產(chǎn)生了應(yīng)指派哪一個(gè)人去完成哪一項(xiàng)任務(wù)，使完成n項(xiàng)任務(wù)的總效率最高（如所用的時(shí)間為最少）。我們把這類(lèi)問(wèn)題稱之為指派問(wèn)題或分派問(wèn)題(AssignmentProblem)。,求解這樣的問(wèn)題時(shí)，需要引入變量xij,其取值只能是1或0，并令：當(dāng)問(wèn)題是要求極小化時(shí)的數(shù)學(xué)模型是：,4.2匹配問(wèn)題定義4.1給定圖G=（V，E），如果M是E的子集合，當(dāng)M中任意兩條邊都不相鄰，則稱M是圖G的一個(gè)匹配(matching)。當(dāng)圖G的匹配M的元素個(gè)數(shù)恰好為頂點(diǎn)數(shù)的一半時(shí)，稱M是圖G的完美匹配。,問(wèn)題4.1（最大基數(shù)匹配問(wèn)題）尋找圖G的匹配M，使得M中含的元素個(gè)數(shù)最多。問(wèn)題4.2（最優(yōu)匹配問(wèn)題）對(duì)于賦權(quán)圖G=（V，E;w），尋找圖G的匹配M，使得M中含的元素的權(quán)重之和最大。問(wèn)題4.3（最小或最大完美匹配問(wèn)題）對(duì)于賦權(quán)圖G=（V，E;w），尋找圖G的完美匹配M，使得M中含的邊的權(quán)重之和達(dá)到最?。ɑ蜃畲螅?4.3求解二部圖匹配設(shè)G=（S，T；E）是二部圖，能夠用反圈算法來(lái)解決二部圖最大匹配問(wèn)題：設(shè)M為當(dāng)前已有的匹配，(1)初始k=0時(shí)，令X(0)={|v是關(guān)于M的非飽和頂點(diǎn)}；(2)在中選邊的原則為如果，則選以vi為頂點(diǎn)的非飽和邊如果，則選以vi為頂點(diǎn)的飽和邊；,(3)在某一步，當(dāng)出現(xiàn)下面情形之一時(shí)停止：情形1：X(k)中有非飽和的T型點(diǎn)，此時(shí)有關(guān)于M的增廣路，則可增廣匹配M（重復(fù)步驟(2)）；情形2情形1沒(méi)有出現(xiàn)，但是由X(k)確定的反圈中無(wú)邊可選，此時(shí)沒(méi)有關(guān)于M的增廣路，則M是最大匹配。,定理4.1：設(shè)G是一個(gè)圖，M是G的一個(gè)匹配，則M是G的最大匹配當(dāng)且僅當(dāng)G中不存在關(guān)于匹配M的增廣路。4.3求解賦權(quán)二部圖完美匹配：匈牙利算法（或最小費(fèi)用最大流問(wèn)題的算法）4.4求解一般圖匹配：Edmonds算法4.5求解一般賦權(quán)圖匹配：Edmonds算法,五、歐拉問(wèn)題,5.1背景德國(guó)的哥尼斯堡城有一條普雷格爾河，河中有兩個(gè)島嶼，河的兩岸和島嶼之間有七座橋相互連接，如圖5.1所示。1736年瑞士科學(xué)家歐拉發(fā)表了關(guān)于圖論方面的第一篇科學(xué)論文，解決了著名的哥尼斯堡七座橋問(wèn)題。,,A,B,,,,,,,,,,,,,,,圖5.1,C,D,,,,,,,圖5.2,A,C,D,B,5.2歐拉問(wèn)題定義5.1給定一個(gè)圖G=（V，E），如果存在一條回路C經(jīng)過(guò)每條邊恰好一次，稱這樣的圖G是歐拉圖。回路C被稱為歐拉回路。問(wèn)題5.1（歐拉問(wèn)題）對(duì)于給定的圖G=（V，E），判斷圖G是否是歐拉圖？定理5.1（歐拉定理）圖G是歐拉圖當(dāng)且僅當(dāng)G是連通圖，并且G的每個(gè)頂點(diǎn)的度為偶數(shù)。,1921年，F(xiàn)leury提供了一個(gè)有效的算法來(lái)尋找圖G的歐拉回路。以Pk=v1v2…vkvk+1表示第k步得到的路，記Gk=G[E-E(Pk)]，如下進(jìn)行第k+1步：在Gk中選一條邊ek+1=vk+1vk+2，使得ek+1不是圖Gk的割邊（除非dGk(vk+1)=1)。令Pk+1=v1v2…vkvk+1vk+2，及Gk+1=G[E-E(Pk+1)]，直到?jīng)]有邊可選。,5.3一筆畫(huà)問(wèn)題問(wèn)題5.2（一筆畫(huà)問(wèn)題）對(duì)于給定的圖G=（V，E），問(wèn)G是否存在一條路P經(jīng)過(guò)每條邊恰好一次？如果G存在這樣的一條路，稱G是可一筆畫(huà)的。這時(shí)，也稱圖G是M圖。定理5.2圖G是可一筆畫(huà)的當(dāng)且僅當(dāng)G是連通圖，并且G中至多存在兩個(gè)頂點(diǎn)的度為奇數(shù)。,六、中國(guó)郵遞員問(wèn)題,6.1中國(guó)郵遞員問(wèn)題1960年，中國(guó)的數(shù)學(xué)家管梅谷教授提出如下問(wèn)題：一個(gè)郵遞員，每次送信都要走遍他負(fù)責(zé)的投遞范圍內(nèi)的每條街道，完成投遞任務(wù)后回到郵局，問(wèn)他應(yīng)該按照何路線投遞信件，使得所走的總路程之和達(dá)到最?。?把這個(gè)問(wèn)題抽象為圖的問(wèn)題，就是對(duì)于給定的連通賦權(quán)圖G=（V，E;w），要尋找G的一個(gè)閉回路C，要求C經(jīng)過(guò)每條邊至少一次，使得閉回路C中的邊權(quán)重之和達(dá)到最小。管梅谷教授在1960年給出了一個(gè)判定閉回路C是否是最優(yōu)的一個(gè)充分必要條件，但是沒(méi)有設(shè)計(jì)出有效的算法；Edmonds和Johnson于1973年給出了一個(gè)有效的算法來(lái)完整地解決了中國(guó)郵遞員問(wèn)題。,Edmonds-Johnson算法：(1)在賦權(quán)圖中找到所有度為奇數(shù)的頂點(diǎn)（共有偶數(shù)個(gè)），如v1,v2,…,v2r-1v2r，并且計(jì)算這2r個(gè)奇數(shù)頂點(diǎn)之間的最短路及其長(zhǎng)度；(2)在以這2r個(gè)頂點(diǎn)為新的頂點(diǎn)構(gòu)造完全圖H2r，在完全圖H2r中，頂點(diǎn)vi與vj之間的邊權(quán)重定義為圖G中vi與vj之間的最短路長(zhǎng)度。,(3)在完全圖H2r上尋找權(quán)重最小的完美匹配M，每條匹配邊對(duì)應(yīng)于圖G中的一條最短路，把得到的r條最短路疊加到賦權(quán)圖G上，就得到新的賦權(quán)圖G*（這是一個(gè)歐拉圖）；(4)對(duì)新的賦權(quán)圖G*，利用求歐拉回路的算法(Fleury)能夠找到一條歐拉回路C，這條回路C就是圖G上的中國(guó)郵遞員問(wèn)題的最優(yōu)解（最優(yōu)路線）。,七、NP-完備的組合最優(yōu)化問(wèn)題,7.1哈密爾頓問(wèn)題(HamiltonianProblem)定義7.1設(shè)給定一個(gè)圖G=（V，E），C是一個(gè)圈，如果C經(jīng)過(guò)G的每個(gè)頂點(diǎn)恰好一次，則稱C是圖G的哈密爾頓圈，也稱圖G是哈密爾頓圖。問(wèn)題7.1（哈密爾頓問(wèn)題）對(duì)于給定圖G，問(wèn)G是否含有哈密爾頓圈？即G是否是哈密爾頓圖？,7.2貨郎擔(dān)問(wèn)題(TravellingSalesmanProblem)設(shè)給定一個(gè)賦權(quán)的完全圖G=（V，E；w），尋找G的一條閉回路C經(jīng)過(guò)所有的頂點(diǎn)（該回路C可以經(jīng)過(guò)某些頂點(diǎn)多次），使得閉回路C上邊的權(quán)重之和達(dá)到最小。一般地，貨郎擔(dān)問(wèn)題沒(méi)有近似值為f(n)的近似算法，對(duì)于滿足三角不等式的完全圖G，存在近似值為2和3/2的近似算法（樹(shù)算法與Christofides算法）。,7.3排序問(wèn)題（SchedulingProblem)給定m臺(tái)功能相同的機(jī)器，設(shè)有n件需要加工的任務(wù)，其加工時(shí)間分別為p1,p2,…,pn，每件任務(wù)要不間斷地在某臺(tái)機(jī)器上加工完成，問(wèn)：如何安排加工任務(wù)的順序（稱為方案），使得把全部任務(wù)加工完畢所需時(shí)間達(dá)到最小。存在近似值為2-1/m和4/3-1/3m的近似算法。,7.４裝箱問(wèn)題（Bin-PackingProblem）給定n個(gè)大小分別為a1,a2,…,an的物品，把它們放入容量為1的多個(gè)箱子之中，要求每個(gè)箱子中所放數(shù)之和不超過(guò)該箱子的容量1，問(wèn)：如何安排裝箱順序，使得需要的箱子數(shù)目盡可能少。該問(wèn)題不存在近似值為3/2-k的近似算法，這里k是大于０的任意正數(shù)。存在多個(gè)近似算法來(lái)解決該問(wèn)題，其近似值為2或3/2。,7.５背包問(wèn)題(KnapsackProblem)給定一個(gè)背包，其容量為Ｂ，設(shè)有n件物品，每件物品的容量分別為a1,a2,…,an，當(dāng)把這些物品放入背包之中，產(chǎn)生的效益分別為p1,p2,…,pn，問(wèn)：如何安排裝物體的順序（稱為方案），滿足裝入背包的物品容量之和不超過(guò)容量Ｂ，使得產(chǎn)生的效益之和達(dá)到最大。存在全多項(xiàng)式近似方案PTAS(polynomial-timeapprximationscheme)。,7.６最小點(diǎn)覆蓋問(wèn)題設(shè)給定一個(gè)圖G=（V，E），尋找Ｖ的一個(gè)子集合Ｓ，使得Ｇ中每條邊的兩個(gè)頂點(diǎn)至少有一個(gè)要屬于Ｓ，稱Ｓ是圖Ｇ的一個(gè)點(diǎn)覆蓋。最小點(diǎn)覆蓋問(wèn)題:就是要尋找點(diǎn)覆蓋Ｓ，使得|S|達(dá)到最小。存在近似值為2的近似算法來(lái)解決該問(wèn)題（匹配、LP）。利用匹配算法，能夠解決二部圖的最小點(diǎn)覆蓋問(wèn)題。,7.７染色問(wèn)題給定圖Ｇ＝（Ｖ，Ｅ），所謂Ｇ的一個(gè)k點(diǎn)染色是指把Ｖ劃分為k個(gè)子集V1,V2,…,Vk,使得集合Vi中的點(diǎn)染成顏色i，并且集合Vi是獨(dú)立集。點(diǎn)染色問(wèn)題就是求這樣的最小正整數(shù)k。給定圖Ｇ＝（Ｖ，Ｅ），所謂Ｇ的一個(gè)k邊染色是指把Ｅ劃分為k個(gè)子集1,E2,…,Ek,使得集合Ei中的邊染成顏色i，并且集合Ei是匹配。邊染色問(wèn)題就是求這樣的最小正整數(shù)k。,7.８平面圖的面染色問(wèn)題給定平面圖Ｇ＝（Ｖ，Ｅ），所謂Ｇ的一個(gè)k面染色是指把Ｇ的所有面劃分為k個(gè)子集F1,F2,…,Fk,使得集合Fi中的面染成顏色i，任何有公共邊的兩個(gè)面具有不同的顏色。面染色問(wèn)題就是求這樣的最小正整數(shù)k。四色猜想(定理)：任何平面圖可以４-面染色。(1979)五色定理：任何平面圖可以５-面染色。(1890),謝謝！,