網(wǎng)絡(luò)優(yōu)化課件

1

概論

2網(wǎng)

絡(luò)

優(yōu)

化

簡(jiǎn)介網(wǎng)絡(luò)：一般理解----計(jì)算機(jī)信息網(wǎng)絡(luò)電話通信網(wǎng)絡(luò)運(yùn)輸服務(wù)網(wǎng)絡(luò)能源和物質(zhì)分派網(wǎng)絡(luò)

人際關(guān)系網(wǎng)絡(luò)等等網(wǎng)絡(luò)優(yōu)化就是研究如何有效地計(jì)劃、管理和控制網(wǎng)絡(luò)系統(tǒng)，使之發(fā)揮最大的社會(huì)和經(jīng)濟(jì)效益

3網(wǎng)

絡(luò)

優(yōu)

化

簡(jiǎn)介

網(wǎng)絡(luò)：數(shù)學(xué)模型、數(shù)學(xué)結(jié)構(gòu)----圖從若干可能的安排或方案中尋求某種意義下的最優(yōu)安排或方案，數(shù)學(xué)上把這種問(wèn)題稱(chēng)為（最）優(yōu)化(Optimization)問(wèn)題

運(yùn)籌學(xué)（OperationsResearch-OR）廣義：管理科學(xué)(OR/MS)、系統(tǒng)科學(xué)/工程、工業(yè)工程(IE)、運(yùn)作管理(OM)

狹義：運(yùn)籌數(shù)學(xué)-最優(yōu)化連續(xù)優(yōu)化：數(shù)學(xué)規(guī)劃（線性規(guī)劃、非線性規(guī)劃）、非光滑優(yōu)化、全局優(yōu)化等離散優(yōu)化：組合優(yōu)化、網(wǎng)絡(luò)優(yōu)化、整數(shù)規(guī)劃等不確定規(guī)劃：隨機(jī)規(guī)劃、模糊規(guī)劃等網(wǎng)絡(luò)優(yōu)化就是研究與（賦權(quán)）圖有關(guān)的最優(yōu)化問(wèn)題4網(wǎng)

絡(luò)

優(yōu)

化

簡(jiǎn)介教材：謝金星、邢文訓(xùn)，《網(wǎng)絡(luò)優(yōu)化》，清華大學(xué)出版社，2000年8月。參考書(shū)：Ahuja,R.K.,MagnantiT.L.,OrlinJ.B.NetworkFlows:Theory,Algorithms,andApplications.PrenticeHall,1993:EnglewoodCliffs,NewJersey.成績(jī)：作業(yè)----50%左右（7次，每章一次） 考試----50%左右內(nèi)容：網(wǎng)絡(luò)優(yōu)化模型、算法及其復(fù)雜性對(duì)象：數(shù)學(xué)、計(jì)算機(jī)科學(xué)、管理科學(xué)、工程科學(xué)等5例1.1公路連接問(wèn)題某一地區(qū)有若干個(gè)主要城市，現(xiàn)準(zhǔn)備修建高速公路把這些城市連接起來(lái)，使得從其中任何一個(gè)城市都可以經(jīng)高速公路直接或間接到達(dá)另一個(gè)城市.假定已經(jīng)知道了任意兩個(gè)城市之間修建高速公路的成本，那么應(yīng)如何決定在哪些城市間修建高速公路，使得總成本最?。?/p>

1.1網(wǎng)絡(luò)優(yōu)化問(wèn)題的例子

例1.2最短路問(wèn)題（SPP-ShortestPathProblem）一名貨柜車(chē)司機(jī)奉命在最短的時(shí)間內(nèi)將一車(chē)貨物從甲地運(yùn)往乙地.從甲地到乙地的公路網(wǎng)縱橫交錯(cuò)，因此有多種行車(chē)路線，這名司機(jī)應(yīng)選擇哪條線路呢？假設(shè)貨柜車(chē)的運(yùn)行速度是恒定的，那么這一問(wèn)題相當(dāng)于需要找到一條從甲地到乙地的最短路.6例1.3運(yùn)輸問(wèn)題(TransportationProblem)某種原材料有M個(gè)產(chǎn)地，現(xiàn)在需要將原材料從產(chǎn)地運(yùn)往N個(gè)使用這些原材料的工廠.假定M個(gè)產(chǎn)地的產(chǎn)量和N家工廠的需要量已知，單位產(chǎn)品從任一產(chǎn)地到任一工廠的的運(yùn)費(fèi)已知，那么如何安排運(yùn)輸方案可以使總運(yùn)輸成本最低？

1.1網(wǎng)絡(luò)優(yōu)化問(wèn)題的例子

例1.4指派問(wèn)題(AssignmentProblem)一家公司經(jīng)理準(zhǔn)備安排N名員工去完成N項(xiàng)任務(wù)，每人一項(xiàng).由于各員工的特點(diǎn)不同，不同的員工去完成同一項(xiàng)任務(wù)時(shí)所獲得的回報(bào)是不同的.如何分配工作方案可以使總回

報(bào)最大？

7例1.5中國(guó)郵遞員問(wèn)題(CPP-ChinesePostmanProblem)一名郵遞員負(fù)責(zé)投遞某個(gè)街區(qū)的郵件.如何為他(她)設(shè)計(jì)一條最短的投遞路線(從郵局出發(fā)，經(jīng)過(guò)投遞區(qū)內(nèi)每條街道至少一次，最后返回郵局)？由于這一問(wèn)題是我國(guó)復(fù)旦大學(xué)管梅谷教授1960年首先提出的，所以國(guó)際上稱(chēng)之為中國(guó)郵遞員問(wèn)題.1.1網(wǎng)絡(luò)優(yōu)化問(wèn)題的例子

例1.6旅行商問(wèn)題/貨郎（擔(dān)）問(wèn)題(TSP-TravelingSalesmanProblem)一名推銷(xiāo)員準(zhǔn)備前往若干城市推銷(xiāo)產(chǎn)品.如何為他(她)設(shè)計(jì)一條最短的旅行路線(從駐地出發(fā)，經(jīng)過(guò)每個(gè)城市恰好一次，最后返回駐地)？這一問(wèn)題的研究歷史十分悠久，通常稱(chēng)之為旅行商問(wèn)題.81.1網(wǎng)絡(luò)優(yōu)化問(wèn)題的例子

例穩(wěn)定婚配問(wèn)題(StableMarriageProblem)假設(shè)有n個(gè)男人和n個(gè)女人,每人都希望從n個(gè)異性中選擇一位自己的配偶.假設(shè)每人都對(duì)n個(gè)異性根據(jù)自己的偏好進(jìn)行了排序,以此作為選擇配偶的基礎(chǔ).當(dāng)給定一種婚配方案(即給每人指定一個(gè)配偶)后,如果存在一個(gè)男人和一個(gè)女人不是互為配偶,但該男人喜歡該女人勝過(guò)其配偶,且該女人喜歡該男人也勝過(guò)其配偶,則該婚配方案稱(chēng)為不穩(wěn)定的.安排穩(wěn)定的婚配方案的問(wèn)題稱(chēng)為穩(wěn)定婚配問(wèn)題。91.1網(wǎng)絡(luò)優(yōu)化問(wèn)題的例子

《網(wǎng)絡(luò)優(yōu)化》：《網(wǎng)絡(luò)流》（NetworkFlows)特點(diǎn)：（1）與圖形有關(guān)，或易于用圖形方式表示（2）優(yōu)化問(wèn)題：從若干可能的安排或方案中尋求某種意義下的最優(yōu)安排或方案101.2圖與網(wǎng)絡(luò)–定義

定義1.1一個(gè)有向圖(DirectedGraph或

Digraph)G是由一個(gè)非空有限集合V(G)和V(G)中某些元素的有序?qū)螦(G)構(gòu)成的二元組，記為有向圖G=(V(G)，A(G)).其中V(G)稱(chēng)為圖G的頂點(diǎn)集(VertexSet)或節(jié)點(diǎn)集(NodeSet)，V(G)中的每一個(gè)元素稱(chēng)為該圖的一個(gè)頂點(diǎn)(Vertex)或節(jié)點(diǎn)(Node)；

A(G)稱(chēng)為圖G的弧集(ArcSet)，A(G)中的每一個(gè)元素(即V(G)中某兩個(gè)元素的有序?qū)?

稱(chēng)為該圖的一條從到的弧

(Arc).在不引起混淆的情況下，記號(hào)V(G)和A(G)中也可以省略G，即分別記頂點(diǎn)集、弧集為V和A，而記有向圖G=（V，A）.

如果對(duì)有向圖G中的每條弧賦予一個(gè)或多個(gè)實(shí)數(shù)，得到的有向圖稱(chēng)為賦權(quán)有向圖或有向網(wǎng)絡(luò),簡(jiǎn)稱(chēng)為網(wǎng)絡(luò)(Network).111.2圖與網(wǎng)絡(luò)–例圖G=(V，A)，其中頂點(diǎn)集V=

弧集A=弧12弧的端點(diǎn)(Endpoint)，尾(Tail)，頭(Head)；頂點(diǎn)相鄰(Adjacent)，鄰居(Neighbor)；弧與頂點(diǎn)關(guān)聯(lián)

(Incident)，出弧(OutgoingArc)，入弧(IncomingArc)；弧相鄰

(Adjacent)；環(huán)

(Loop)，孤立點(diǎn)(IsolatedVertex)；圖的階(Order)頂點(diǎn)的度（Degree），出度，入度，奇點(diǎn)，偶點(diǎn)沒(méi)有環(huán)、且沒(méi)有多重弧的圖稱(chēng)為簡(jiǎn)單圖(SimpleGraph)1.2圖與網(wǎng)絡(luò)–基本概念131.2圖與網(wǎng)絡(luò)–子圖

稱(chēng)為G的子圖(Subgraph)

圖的支撐子圖

(SpanningSubgraph，又稱(chēng)生成子圖)是包含G

的所有頂點(diǎn)的子圖（頂點(diǎn)、弧）導(dǎo)出子圖(InducedSubgraph)圖的導(dǎo)出子圖是唯一的；圖的支撐子圖一般是不唯一的

有向圖中的途徑(Walk)是該圖的一些頂點(diǎn)和弧所組成的子圖，這些頂點(diǎn)與弧可以交錯(cuò)排列成點(diǎn)弧序列其中

或

如果該序列中的所有弧都指向同一方向，即，則該途徑稱(chēng)為有向途徑(DirectedWalk).141.2圖與網(wǎng)絡(luò)–路、圈

有向圖中的路(Path)是該圖的不包含重復(fù)頂點(diǎn)的途徑.方向與路的起點(diǎn)到終點(diǎn)的方向一致的弧稱(chēng)為路的前向弧(ForwardArc)；否則稱(chēng)為后向弧或反向弧(BackwardArc).P,P+,P-

有向圖中的有向路(DirectedPath)是該圖的不包含重復(fù)頂點(diǎn)的有向途徑，即不包含反向弧的路.

有向圖的圈(Cycle)是起點(diǎn)和終點(diǎn)重合，且不含其他重復(fù)頂點(diǎn)的途徑.C,C+,C-

有向圖中的有向圈(DirectedCycle)是該圖的不包含反向弧的圈.不包含有向圈的圖稱(chēng)為無(wú)圈圖(AcyclicGraph).151.2圖與網(wǎng)絡(luò)–路、圈

對(duì)于有向圖中的兩個(gè)頂點(diǎn)，如果在圖中至少存在一條路把它們連接起來(lái)，則稱(chēng)這兩個(gè)頂點(diǎn)是連通的(Connected).如果圖中任意兩個(gè)頂點(diǎn)都是連通的，則稱(chēng)該圖為連通的(Connected)；否則稱(chēng)為不連通的(Disconnected).不連通圖可以分解成一些連通分支的并，而連通圖只有一個(gè)連通分支.所謂連通分支(Component)，就是圖中的極大連通子

圖。如果有向圖中從任意一個(gè)頂點(diǎn)出發(fā)，都存在至少一條有向路到達(dá)任意另一個(gè)頂點(diǎn)，則稱(chēng)該圖為強(qiáng)連通的(StronglyConnected).同樣可以類(lèi)似地定義強(qiáng)連通分支.

若，則稱(chēng)兩個(gè)端點(diǎn)分別位于S，T的弧為一個(gè)割（cut），記為

[S，T]=161.2圖與網(wǎng)絡(luò)–無(wú)向圖

定義1.2一個(gè)無(wú)向圖(UndirectedGraph)G是由一個(gè)非空有限集合V和V中某些

元素

的無(wú)序?qū)螮構(gòu)成的，即G=(V，E).其中

V=V(G)仍稱(chēng)為

圖G的頂點(diǎn)集(VertexSet)或

節(jié)點(diǎn)集(NodeSet)，V中的每一個(gè)

元素

稱(chēng)為該圖的

一個(gè)頂點(diǎn)(Vertex)或

節(jié)點(diǎn)(Node)；E=E(G)=通常稱(chēng)為圖G的邊集合(EdgeSet)，E中的每一個(gè)元素(即V中某兩個(gè)元素的無(wú)序?qū)?稱(chēng)為該圖的一條邊(Edge).

邊上賦權(quán)的無(wú)向圖稱(chēng)為賦權(quán)無(wú)向圖或無(wú)向網(wǎng)絡(luò)(UndirectedNetwork).本課程中，在不引起混淆的情況下，有時(shí)將有向圖和無(wú)向圖都簡(jiǎn)稱(chēng)為圖(Graph)；也不再對(duì)弧和邊的概念作嚴(yán)格區(qū)分。并且，對(duì)圖和網(wǎng)絡(luò)的概念也不再作嚴(yán)格區(qū)分。171.2圖與網(wǎng)絡(luò)–兩種特殊的圖

若圖G=(V，E)的頂點(diǎn)集V可以表示成兩個(gè)互不相交的非空子集S，T的并集，且使得G中每一條邊的一個(gè)端點(diǎn)在S中，另一端點(diǎn)在T中，則稱(chēng)G為二部圖/二分圖(BibartiteGraph).當(dāng)|S|=p，|T|=q，且S與T中任意兩對(duì)頂點(diǎn)都相鄰時(shí)，稱(chēng)G為完全二部圖，記為Kp,q.類(lèi)似地，也可以定義有向的完全圖和有向的完全二部圖.Kn的弧的數(shù)量為n(n-1)/2

若無(wú)向圖G的任意兩個(gè)頂點(diǎn)間有且只有一條邊相連，則稱(chēng)其為完全圖(CompleteGraph).n階完全圖記為Kn.Kp,q的弧的數(shù)量為pq

181.3圖與網(wǎng)絡(luò)的數(shù)據(jù)結(jié)構(gòu)1.3.1鄰接矩陣(AdjacencyMatrix)表示法

圖G=(V，A)的鄰接矩陣C是如下定義的：C是一個(gè)的0-1矩陣，即每行元素之和正好是對(duì)應(yīng)頂點(diǎn)的出度，

每列元素之和正好是對(duì)應(yīng)頂點(diǎn)的入度.G=(V，A)是一個(gè)簡(jiǎn)單有向圖|V|=n，|A|=m

在鄰接矩陣的所有元素中，只有m個(gè)為非零元.191.3圖與網(wǎng)絡(luò)的數(shù)據(jù)結(jié)構(gòu)1.3.1鄰接矩陣表示法

對(duì)于網(wǎng)絡(luò)中的權(quán)，也可以用類(lèi)似鄰接矩陣的矩陣表示.只是此時(shí)一條弧所對(duì)應(yīng)的元素不再是1，而是相應(yīng)的權(quán)而已.如果網(wǎng)絡(luò)中每條弧賦有多種權(quán)，則可以用多個(gè)矩陣表示這些權(quán).12345201.3圖與網(wǎng)絡(luò)的數(shù)據(jù)結(jié)構(gòu)1.3.2關(guān)聯(lián)矩陣(IncidenceMatrix)表示法圖G=(V，A)的鄰接矩陣C是如下定義的：C是一個(gè)的矩陣，即每行元素1的個(gè)數(shù)正好是對(duì)應(yīng)頂點(diǎn)的出度，

每行元素-1的個(gè)數(shù)正好是對(duì)應(yīng)頂點(diǎn)的入度.G=(V，A)是一個(gè)簡(jiǎn)單有向圖|V|=n，|A|=m

在關(guān)聯(lián)矩陣的所有元素中，只有2m個(gè)為非零元.211.3圖與網(wǎng)絡(luò)的數(shù)據(jù)結(jié)構(gòu)1.3.2關(guān)聯(lián)矩陣表示法

如果網(wǎng)絡(luò)中每條弧賦有一個(gè)權(quán)，我們可以把關(guān)聯(lián)矩陣增加一行,把每一條弧所對(duì)應(yīng)的權(quán)存貯在增加的行中.如果網(wǎng)絡(luò)中每條弧賦有多個(gè)權(quán)，我們可以把關(guān)聯(lián)矩陣增加相應(yīng)的行數(shù)，把每一條弧所對(duì)應(yīng)的權(quán)存貯在增加的行中.1234512378654221.3圖與網(wǎng)絡(luò)的數(shù)據(jù)結(jié)構(gòu)1.3.3弧表（ArcList)表示法所謂圖的弧表,也就是圖的弧集合中的所有有序?qū)?弧表表示法直接列出所有弧的起點(diǎn)和終點(diǎn)，共需2m個(gè)存貯單元，因此當(dāng)網(wǎng)絡(luò)比較稀疏時(shí)比較方便.G=(V，A)是一個(gè)簡(jiǎn)單有向圖|V|=n，|A|=m

231.3圖與網(wǎng)絡(luò)的數(shù)據(jù)結(jié)構(gòu)1.3.3弧表表示法起點(diǎn)11234455終點(diǎn)23423534權(quán)(例)8964036712345241.3圖與網(wǎng)絡(luò)的數(shù)據(jù)結(jié)構(gòu)G=(V，A)是一個(gè)簡(jiǎn)單有向圖|V|=n，|A|=m

1.3.4鄰接表(AdjacencyLists)表示法圖的鄰接表是圖的所有節(jié)點(diǎn)的鄰接表的集合;而對(duì)每個(gè)節(jié)點(diǎn)，它的鄰接表就是它的所有出弧.對(duì)于有向圖G=（V，A），一般用A（i）表示節(jié)點(diǎn)i的鄰接表，即節(jié)點(diǎn)i的所有出弧構(gòu)成的集合或鏈表（實(shí)際上只需要列出弧的另一個(gè)端點(diǎn)，即弧的頭）.這種記法我們?cè)诒緯?shū)后面將會(huì)經(jīng)常用到.

251.3圖與網(wǎng)絡(luò)的數(shù)據(jù)結(jié)構(gòu)1.3.4鄰接表表示法122345283904602403053036470單向鏈表(指針數(shù)組)

A(1)={2,3}A(2)={4}A(3)={2}A(4)={3,5}A(5)={3,4}12345261.3圖與網(wǎng)絡(luò)的數(shù)據(jù)結(jié)構(gòu)1.3.5星形（Star）表示法前向星形(ForwardStar)表示法

節(jié)點(diǎn)對(duì)應(yīng)的出弧的起始地址編號(hào)數(shù)組（記為point）為記錄弧信息的數(shù)組為弧編號(hào)12345678起點(diǎn)11234455終點(diǎn)23423534權(quán)89640367節(jié)點(diǎn)號(hào)i123456起始地址point(i)1345791234512378654271.3圖與網(wǎng)絡(luò)的數(shù)據(jù)結(jié)構(gòu)1.3.5星形（Star）表示法反向星形(ReverseStar)表示法

節(jié)點(diǎn)對(duì)應(yīng)的入弧的起始地址編號(hào)數(shù)組（記為rpoint）為

記錄弧信息的數(shù)組為1234523756841節(jié)點(diǎn)號(hào)i123456起始地址rpoint(i)113689弧編號(hào)12345678終點(diǎn)起點(diǎn)2233344531145524權(quán)48906763281.3圖與網(wǎng)絡(luò)的數(shù)據(jù)結(jié)構(gòu)幾點(diǎn)說(shuō)明（1）星形表示法和鄰接表方法常用.星形表示法的優(yōu)點(diǎn)是占用的存貯空間較少;鄰接表方法增加或刪除一條弧所需的計(jì)算工作量很少（2）當(dāng)網(wǎng)絡(luò)不是簡(jiǎn)單圖，而是具有平行弧(即多重弧)時(shí)，鄰接矩陣法是不能采用的.其他方法則可以推廣到可以處理平行弧的情形.

（3）無(wú)向圖處理類(lèi)似.如無(wú)向圖的關(guān)聯(lián)矩陣只含有元素0和+1.在鄰接表和星形表示中，每條弧會(huì)被存貯兩次;反向星形表示顯然是沒(méi)有必要的，等等.291.4.1組合優(yōu)化–定義1.4計(jì)算復(fù)雜性的概念定義1.3所謂組合(最)優(yōu)化(CombinatorialOptimization)又稱(chēng)離散優(yōu)化（DiscreteOptimization），它是通過(guò)數(shù)學(xué)方法去尋找離散事件的最優(yōu)編排、分組、次序或篩選等.這類(lèi)問(wèn)題可用數(shù)學(xué)模型描述為：

優(yōu)化問(wèn)題三要素:(Min,f,F)或(Max,f,F)

其中D表示有限個(gè)點(diǎn)組成的集合(定義域)

,f為目標(biāo)函數(shù),F={x|x

D,g(x)

0}為可行域

301.4計(jì)算復(fù)雜性的概念1.4.1組合優(yōu)化–例例1.70-1背包問(wèn)題(knapsackproblem)設(shè)有一個(gè)容積為b的背包，n個(gè)體積分別為ai，價(jià)值分別為ci的物品，如何以最大的價(jià)值裝包？這個(gè)問(wèn)題稱(chēng)為0-1背包問(wèn)題.用數(shù)學(xué)規(guī)劃模型表示為：

D={0,1}n

例1.10裝箱問(wèn)題(BinPacking)如何以個(gè)數(shù)最少的尺寸為1的箱子裝進(jìn)n個(gè)尺寸不超過(guò)1的物品，該問(wèn)題為裝箱問(wèn)題.

311.4計(jì)算復(fù)雜性的概念1.4.1組合優(yōu)化–例例1.9整數(shù)線性規(guī)劃(IntegerLinearProgramming)

(IP)

.

我們假設(shè)線性整數(shù)規(guī)劃的參數(shù)（約束矩陣和右端項(xiàng)系數(shù)）都是整數(shù)(或有理數(shù)).許多組合優(yōu)化問(wèn)題可以用整數(shù)規(guī)劃模型表示,但有時(shí)不如直接用自然語(yǔ)言描述簡(jiǎn)潔

321.4計(jì)算復(fù)雜性的概念1.4.2多項(xiàng)式時(shí)間算法對(duì)于組合優(yōu)化問(wèn)題，我們關(guān)心的一般不是最優(yōu)解的存在性和唯一性，而是如何找到有效的算法求得一個(gè)最優(yōu)解.那么如何衡量算法的優(yōu)劣、有效與無(wú)效呢？

完全枚舉法可以求得最優(yōu)解,但枚舉時(shí)間有時(shí)不可能接受

ATSP:(n-1)!枚舉(TOUR,周游或環(huán)游)設(shè)計(jì)算機(jī)每秒進(jìn)行100億次枚舉,需

30!/10e+10>2.65e+22(秒)即2.65e+22/(365*24*60*60) >8.4e+13(年)331.4計(jì)算復(fù)雜性的概念1.4.2多項(xiàng)式時(shí)間算法構(gòu)造算法的目的是能夠解決問(wèn)題（或至少是問(wèn)題某個(gè)子類(lèi)）的所有實(shí)例而不單單是某一個(gè)實(shí)例

問(wèn)題（Problem）是需要回答的一般性提問(wèn)，通常含有若干個(gè)滿足一定條件的參數(shù).問(wèn)題通過(guò)下面的描述給定：（1）描述所有參數(shù)的特性，（2）描述答案所滿足的條件.問(wèn)題中的參數(shù)賦予了具體值的例子稱(chēng)為實(shí)例(instance).衡量一個(gè)算法的好壞通常是用算法中的加、減、乘、除和比較等基本運(yùn)算的總次數(shù)（計(jì)算時(shí)間）C（I）同實(shí)例I在計(jì)算機(jī)計(jì)算時(shí)的二進(jìn)制輸入數(shù)據(jù)(輸入規(guī)模/長(zhǎng)度d（I）)的大小關(guān)系來(lái)度量.

C(I)=f(d(I)):該函數(shù)關(guān)系稱(chēng)為算法的計(jì)算復(fù)雜性（度）341.4計(jì)算復(fù)雜性的概念1.4.2多項(xiàng)式時(shí)間算法

對(duì)于一個(gè)正整數(shù)x，二進(jìn)制表示是以如ATSP:二進(jìn)制輸入長(zhǎng)度總量不超過(guò)(不考慮正負(fù)號(hào)、分隔符等)的系數(shù)來(lái)表示，其中，

x的二進(jìn)制數(shù)的位數(shù)不超過(guò)

假設(shè)每一個(gè)數(shù)據(jù)(距離)的絕對(duì)值都有上界K

輸入長(zhǎng)度是n的多項(xiàng)式函數(shù)所以網(wǎng)絡(luò)優(yōu)化中常用n,m等表示輸入規(guī)模351.4計(jì)算復(fù)雜性的概念1.4.2多項(xiàng)式時(shí)間算法例構(gòu)造算法將n個(gè)自然數(shù)從小到大排列起來(lái)

算法輸入自然數(shù)a(1),a(2),…,a(n).for(i=1;i<n;i++) for(j=i+1;j<=n;j++) if(a(i)>a(j)){ k=a(i);a(i)=a(j);a(j)=k; }即該算法的計(jì)算復(fù)雜性（度）為O(n2)基本運(yùn)算的總次數(shù)(最壞情形）：2n(n-1)=O(n2)

比較：（n-1)+(n-2)+…+1=n(n-1)/2

賦值：

3{(n-1)+(n-2)+…+1}=3n(n-1)/2361.4.2多項(xiàng)式時(shí)間算法1.4計(jì)算復(fù)雜性的概念定義1.4假設(shè)問(wèn)題和解決該問(wèn)題的一個(gè)算法已經(jīng)給定，若存在g(x)為多項(xiàng)式函數(shù)且對(duì)該問(wèn)題任意的一個(gè)實(shí)例I，使得計(jì)算時(shí)間成立，則稱(chēng)該算法為解決該問(wèn)題的多項(xiàng)式(時(shí)間)算法(Polynomialtimealgorithm).當(dāng)不存在多項(xiàng)式函數(shù)g(x)使得上式成立時(shí)，稱(chēng)相應(yīng)的算法是非多項(xiàng)式時(shí)間算法,或指數(shù)(時(shí)間)算法(Exponentialtimealgorithm)輸入規(guī)模增大時(shí)，多項(xiàng)式時(shí)間算法的基本計(jì)算總次數(shù)的增加速度相對(duì)較慢.注：上面定義中，要求對(duì)該問(wèn)題的任意一個(gè)實(shí)例均成立，這種分析方法稱(chēng)為最壞性能分析（Worst-CaseAnalysis）371.4計(jì)算復(fù)雜性的概念1.4.2多項(xiàng)式時(shí)間算法

近似值計(jì)算機(jī)提速10倍n10100100010121013nlogn3366499660.9e110.87e12n21001041061063.16e6n310001061091042.15e4108n410121016102010182n10241.27e301.05e301404310n1010101001010001213nlogn20791.93e137.89e297995n!3628800101584e25671415381.4計(jì)算復(fù)雜性的概念1.4.2多項(xiàng)式時(shí)間算法

算法復(fù)雜性研究中:常將算法的計(jì)算時(shí)間表示為：?jiǎn)栴}中的簡(jiǎn)單而典型的參數(shù)(如網(wǎng)絡(luò)優(yōu)化中n,m),

以及問(wèn)題中出現(xiàn)的數(shù)值(如弧上的權(quán))的最大值(按絕對(duì)值)K，等自變量的函數(shù)關(guān)系如果算法運(yùn)行時(shí)間的上界是m,n和K的多項(xiàng)式函數(shù)，則稱(chēng)相應(yīng)的算法為偽多項(xiàng)式（Pseudopolynomial）（時(shí)間）算法，或擬多項(xiàng)式（時(shí)間）算法.實(shí)際問(wèn)題的輸入規(guī)模/長(zhǎng)度一定是m,n和logK的一個(gè)多項(xiàng)式函數(shù).所以：多項(xiàng)式算法等價(jià)于其運(yùn)行時(shí)間的上界是m,n和logK的多項(xiàng)式函數(shù).特別地,如果運(yùn)行時(shí)間的上界是m,n的多項(xiàng)式函數(shù)（即該多項(xiàng)式函數(shù)不包含logK）,則稱(chēng)相應(yīng)的算法為強(qiáng)多項(xiàng)式(StronglyPolynomial)時(shí)間算法.一般來(lái)說(shuō)，偽多項(xiàng)式算法并不是多項(xiàng)式算法.391.4.3多項(xiàng)式問(wèn)題1.4計(jì)算復(fù)雜性的概念TSP等許多問(wèn)題至今沒(méi)有找到多項(xiàng)式時(shí)間算法,但尚未證明其不存在定義1.5對(duì)于給定的一個(gè)優(yōu)化問(wèn)題，若存在一個(gè)求解該問(wèn)題最優(yōu)解的多項(xiàng)式時(shí)間算法，則稱(chēng)給定的優(yōu)化問(wèn)題是多項(xiàng)式可解問(wèn)題，或簡(jiǎn)稱(chēng)多項(xiàng)式問(wèn)題，所有多項(xiàng)式問(wèn)題集記為P(Polynomial).同樣道理,可以定義強(qiáng)多項(xiàng)式問(wèn)題,偽多項(xiàng)式問(wèn)題等.TSP是否存在多項(xiàng)式時(shí)間算法?----這是21世紀(jì)數(shù)學(xué)和計(jì)算機(jī)科學(xué)的挑戰(zhàn)性問(wèn)題之一40布置作業(yè)目的掌握?qǐng)D與網(wǎng)絡(luò)的基本概念掌握算法復(fù)雜性的基本概念內(nèi)容《網(wǎng)絡(luò)優(yōu)化》第49-51頁(yè)

5;9;14;16更正：第14題“”改為

411.5NP,NPC和NP-hard概念

(計(jì)算復(fù)雜性理論）網(wǎng)

絡(luò)

優(yōu)

化

第1章概論（第2講）

NetworkOptimization清華大學(xué)數(shù)學(xué)科學(xué)系

謝金星辦公室：理科樓1308#（電話：62787812）Email:jxie@

/~jxie42運(yùn)籌學(xué)的ABC--A2B2C2

（至少是組合優(yōu)化、理論計(jì)算機(jī)科學(xué)的ABC）ApproximateAlgorithm(近似算法)；HeuristicBranchandBound（分枝定界）

ComputationalComplexity（計(jì)算復(fù)雜性）口莫開(kāi)，開(kāi)口常說(shuō)錯(cuò)。ＮＰ理論在監(jiān)督，眾目睽睽難逃脫。計(jì)算復(fù)雜性理論的“Bible”GareyMR.andJohnson.DS,Computersandintractability:aguidetothetheoryofNP-completeness.SanFrancisco:.W.H.FreemanandCo.,1979(中譯本:《計(jì)算機(jī)和難解性：NP-C理論導(dǎo)論》.張立昂等譯,科學(xué)出版社，1987)431.5.1問(wèn)題、實(shí)例與輸入規(guī)模評(píng)價(jià)一個(gè)算法的依據(jù)是該算法在最壞實(shí)例下的計(jì)算時(shí)間與實(shí)例輸入規(guī)模的關(guān)系：?jiǎn)栴}實(shí)例TSP問(wèn)題中各參數(shù):100個(gè)城市，城市間距離已知.背包問(wèn)題問(wèn)題中各參數(shù):4個(gè)物品，大小分別為4,3,2,2.價(jià)值分別為8,7,5,7.包的大小為6.整數(shù)線性規(guī)劃問(wèn)題中的n,A,b,c已知.比多項(xiàng)式問(wèn)題類(lèi)可能更廣泛的一個(gè)問(wèn)題類(lèi)是非確定多項(xiàng)式

(NondeterministicPolynomial，簡(jiǎn)記NP)問(wèn)題類(lèi)

存在多項(xiàng)式算法的問(wèn)題集合：多項(xiàng)式問(wèn)題類(lèi)（P）存在多項(xiàng)式函數(shù)g(x)滿足上式時(shí)，算法為多項(xiàng)式算法NP類(lèi)是通過(guò)判定問(wèn)題引入的。44對(duì)任何一個(gè)優(yōu)化問(wèn)題，可以考慮其三種形式：最優(yōu)化形式（原形：最優(yōu)解）計(jì)值形式（最優(yōu)值）判定形式（上界）定義1.6如果一個(gè)問(wèn)題的每一個(gè)實(shí)例只有“是”或“否”兩種答案，則稱(chēng)這個(gè)問(wèn)題為判定問(wèn)題(Decision/recognition/feasibilityproblem).稱(chēng)有肯定答案的實(shí)例為“是”實(shí)例(yes-instance).稱(chēng)答案為“否”的實(shí)例為“否”實(shí)例或非“是”實(shí)例(no-instance).1.5.2判定問(wèn)題-定義

例1.13線性規(guī)劃問(wèn)題(LP)的判定形式——LP判定問(wèn)題：給定一個(gè)實(shí)數(shù)值z(mì)，(LP)是否有可行解使其目標(biāo)值不超過(guò)z？即：給定z，是否有

?難度降低就有效算法的存在性而言，通常認(rèn)為三種形式等價(jià)！

45文字集

例1.15適定性問(wèn)題(Satisfiabilityproblem)在邏輯運(yùn)算中，布爾變量x的取值只有兩個(gè)：“真”(1)和“假”(0)，邏輯運(yùn)算有“或（+）”，“與（

）”和“非（—）.1.5.2判定問(wèn)題-例存在真值分配的表達(dá)式稱(chēng)為適定的(可滿足的)

+000011101111

000010100111

—0110文字集的任意一個(gè)子集中各元素（布爾變量）的“或”運(yùn)算組成一個(gè)句子,多個(gè)句子的“與”運(yùn)算組成一個(gè)表達(dá)式，如

適定性問(wèn)題：給定布爾表達(dá)式，（SAT） 是適定的嗎？461.5.2判定問(wèn)題-例例1.16三精確覆蓋(3-ExactCovering：X3C)已知的n個(gè)子集構(gòu)成的子集族

，其中每個(gè)子集包含S中三個(gè)元素，F(xiàn)中是否存在m個(gè)子集，使得？若m個(gè)子集滿足上式，則稱(chēng)這m個(gè)子集精確覆蓋S.471.5.3非確定多項(xiàng)式問(wèn)題類(lèi)(NP)–定義定義1.7若存在一個(gè)多項(xiàng)式函數(shù)g(x)和一個(gè)驗(yàn)證算法H，對(duì)一類(lèi)判定問(wèn)題A的任何一個(gè)“是”實(shí)例I，都存在一個(gè)字符串S是I的可行解，滿足其輸入長(zhǎng)度d(S)不超過(guò)g(d(I))，其中d(I)為I的輸入長(zhǎng)度，且算法H驗(yàn)證S為實(shí)例I的可行解的計(jì)算時(shí)間f(H)不超過(guò)g(d(I))，則稱(chēng)判定問(wèn)題A是非確定多項(xiàng)式的?？紤]將求解判定問(wèn)題的算法分為兩個(gè)階段：（1）猜測(cè)階段：求出或猜測(cè)該問(wèn)題的一個(gè)解（2）檢查或驗(yàn)證階段：一旦解已經(jīng)選定，將猜測(cè)的解作為輸入，驗(yàn)證此解是否為該實(shí)例“是”的回答.我們稱(chēng)實(shí)例“是”回答的解為實(shí)例的可行解，否則稱(chēng)為不可行解.

所有非確定多項(xiàng)式問(wèn)題的集合用NP表示.

構(gòu)造字符串（解）的過(guò)程及驗(yàn)證算法H一起構(gòu)成一個(gè)算法，稱(chēng)為非確定多項(xiàng)式（時(shí)間）算法。48所以，可以從討論基本可行解的性質(zhì)入手

整系數(shù)問(wèn)題等價(jià)于有理系數(shù)問(wèn)題

1.5.3非確定多項(xiàng)式問(wèn)題類(lèi)(NP)–例例1.17整系數(shù)（或有理系數(shù)）的LP判定問(wèn)題屬于NP.其實(shí)，，LP

P，所以LP

NP.

下面考慮通過(guò)定義來(lái)說(shuō)明LP

NP分析與思考：(注意：書(shū)上證明有漏洞)

（不）等式組有可行解，等價(jià)于它有基本可行解

LP判定問(wèn)題等價(jià)于驗(yàn)證如下（不）等式組的可行解問(wèn)題

因此可以不考慮目標(biāo)函數(shù)問(wèn)題，仍記為49

1.5.3非確定多項(xiàng)式問(wèn)題類(lèi)(NP)–例引理1.1LP問(wèn)題的約束的基本可行解的各分量值有界，其二進(jìn)制字符串表達(dá)式的輸入長(zhǎng)度不超過(guò)例1.17整系數(shù)（或有理系數(shù)）的LP判定問(wèn)題屬于NP.（續(xù)）輸入長(zhǎng)度不超過(guò)又，，，分量值不超過(guò)50驗(yàn)證時(shí)最多需

(m+1)n個(gè)乘，(m+1)(n-1)個(gè)加或減，n+m+1個(gè)比較，共計(jì)LP實(shí)例的輸入長(zhǎng)度d(I)滿足

1.5.3非確定多項(xiàng)式問(wèn)題類(lèi)(NP)–例LP的一個(gè)基本可行解的輸入長(zhǎng)度不超過(guò)例1.17整系數(shù)（或有理系數(shù)）的LP判定問(wèn)題屬于NP.（續(xù)）對(duì)LP判定問(wèn)題的一個(gè)“是”實(shí)例，上述約束組（等式和不等式組）一定存在一個(gè)基本可行解.當(dāng)給定一個(gè)基本可行解x，只要驗(yàn)證是否滿足？

取多項(xiàng)式函數(shù)g(x)=2x2，則滿足定義，所以LP

NP.

51F中m個(gè)元素是S的一個(gè)精確三覆蓋的充分必要條件為：相應(yīng)的m個(gè)向量滿足集合S中共有3m個(gè)元素，子集族F中的每個(gè)子集合對(duì)應(yīng)一個(gè)3m維向量：向量的3m個(gè)分量對(duì)應(yīng)3m個(gè)元素，元素包含在對(duì)應(yīng)子集中的分量為1，余下的為0.例如：S=，F(xiàn)中的一個(gè)元素，對(duì)應(yīng)向量為

=(1,1,0,0,0,1)，表示為一個(gè)字符串(110001).

1.5.3非確定多項(xiàng)式問(wèn)題類(lèi)(NP)–例按字符串向量問(wèn)題，精確三覆蓋“是”實(shí)例的任何一個(gè)解可以用長(zhǎng)度為3m2的字符表示.驗(yàn)證是否可行解的算法最多需3m2個(gè)加法和3m個(gè)比較，算法的計(jì)算時(shí)間為3m2+3m.例1.19三精確覆蓋屬于NP三精確覆蓋問(wèn)題任何一個(gè)實(shí)例的輸入長(zhǎng)度d(I)≥3m.選g(x)=x2/3+x，則定義條件滿足，所以三精確覆蓋屬于NP.

52多項(xiàng)式轉(zhuǎn)換(定義)1.5.3非確定多項(xiàng)式問(wèn)題類(lèi)(NP)–問(wèn)題A2的難度不低于問(wèn)題A1

定義1.8給定問(wèn)題A1和A2，若存在一個(gè)多項(xiàng)式算法φ滿足：對(duì)A1的任何一個(gè)實(shí)例I1，算法φ將實(shí)例I1的輸入轉(zhuǎn)換為A2的一個(gè)實(shí)例I2的輸入；這種轉(zhuǎn)換過(guò)程使得實(shí)例I1和I2的解一一對(duì)應(yīng)，即φ將實(shí)例I1的一個(gè)解x1的輸入轉(zhuǎn)換為實(shí)例I2的一個(gè)解x2的輸入，且x1為I1的“是”答案x2是I2的一個(gè)“是”答案；則稱(chēng)A1問(wèn)題多項(xiàng)式轉(zhuǎn)換為A2問(wèn)題，算法φ稱(chēng)為問(wèn)題A1到問(wèn)題A2的一個(gè)多項(xiàng)式轉(zhuǎn)換（算法）(Transformation).常用的研究方法--多項(xiàng)式轉(zhuǎn)換(變換)、多項(xiàng)式歸約(歸結(jié))若A1多項(xiàng)式轉(zhuǎn)換為A2，且A2∈P，則A1∈P若A1多項(xiàng)式轉(zhuǎn)換為A2，且A2∈NP，則A1∈NP53進(jìn)一步，該映射可以在SAT實(shí)例的輸入長(zhǎng)度mn的多項(xiàng)式時(shí)間內(nèi)完成SAT的一個(gè)實(shí)例是由n個(gè)邏輯變量和m個(gè)句子組成，輸入長(zhǎng)度是mn.1.5.3非確定多項(xiàng)式問(wèn)題類(lèi)(NP)–多項(xiàng)式轉(zhuǎn)換

等價(jià)于一個(gè)整數(shù)（0-1）線性規(guī)劃問(wèn)題（目標(biāo)可以任意）。例1.20適定性問(wèn)題多項(xiàng)式轉(zhuǎn)換為整數(shù)（0-1）線性規(guī)劃問(wèn)題.將“真”對(duì)應(yīng)“1”，“假”對(duì)應(yīng)“0”，令邏輯變量x對(duì)應(yīng)整數(shù)0或1，

對(duì)應(yīng)1-x.含n個(gè)變量的句子(j=1,2,...,m)為“真”，對(duì)應(yīng)下列不等式組有可行解：適定性問(wèn)題多項(xiàng)式轉(zhuǎn)換為整數(shù)（0-1）線性規(guī)劃（判定）問(wèn)題54進(jìn)一步，該映射可以在X3C實(shí)例的輸入長(zhǎng)度的多項(xiàng)式時(shí)間內(nèi)完成特殊0-1背包判定問(wèn)題（本書(shū)后面簡(jiǎn)稱(chēng)0-1背包判定問(wèn)題）:對(duì)給定的整數(shù)和b，是否存在{1,2,...,n}的子集B，使得?例1.21三精確覆蓋多項(xiàng)式轉(zhuǎn)換為0-1背包判定問(wèn)題1.5.3非確定多項(xiàng)式問(wèn)題類(lèi)(NP)–多項(xiàng)式轉(zhuǎn)換

所以，三精確覆蓋問(wèn)題多項(xiàng)式轉(zhuǎn)換為0-1背包判定問(wèn)題三精確覆蓋實(shí)例的一個(gè)解一一對(duì)應(yīng)背包問(wèn)題實(shí)例的一個(gè)解：

假設(shè)存在B

{1,2,...,n}，使得.由|B|不超過(guò)n，知左邊和式中（n+1)同次冪項(xiàng)的系數(shù)和不超過(guò)n（無(wú)進(jìn)位）；又由b的每個(gè)冪次項(xiàng)系數(shù)為1,知左邊和式中n+1的每個(gè)次冪項(xiàng)系數(shù)恰好為1.

{|j

B}得S的一個(gè)三精確覆蓋

55多項(xiàng)式歸約(定義)1.5.4NP完全問(wèn)題類(lèi)(NPC)-定義1.9已知判定問(wèn)題A1和A2，若存在多項(xiàng)式函數(shù)和，使得對(duì)A1的任何實(shí)例I，在多項(xiàng)式時(shí)間內(nèi)構(gòu)造A2的一個(gè)實(shí)例，其輸入長(zhǎng)度不超過(guò)，并對(duì)A2的任何一個(gè)算法H2，都存在問(wèn)題A1的一個(gè)算法H1，使得H1算法調(diào)用H2算法且使得計(jì)算時(shí)間 ，其中fH1(x)和fH2(x)分別表示算法H1和H2的計(jì)算時(shí)間與實(shí)例輸入長(zhǎng)度x之間的關(guān)系，則稱(chēng)問(wèn)題A1多項(xiàng)式歸約為問(wèn)題A2.

根據(jù)A2的算法H2，構(gòu)造A1的算法H1的過(guò)程，即映射

φ

：H2H1稱(chēng)為從A1到A2的一個(gè)多項(xiàng)式歸約(reduction).

56問(wèn)題A2的難度不低于問(wèn)題A1(注意：書(shū)上此處有誤)

若A1多項(xiàng)式歸約為A2，且A2∈P，則A1∈P若A1多項(xiàng)式歸約為A2，且A2∈NP，則A1∈NP若A1多項(xiàng)式歸約為A2，則當(dāng)把H1對(duì)H2的一次調(diào)用當(dāng)成一次基本運(yùn)算時(shí)，H1是A1的多項(xiàng)式算法。1.5.4NP完全問(wèn)題類(lèi)(NPC)-多項(xiàng)式歸約多項(xiàng)式轉(zhuǎn)換是多項(xiàng)式歸約的特例歸約映射可以如下構(gòu)造：

H1：STEP1–用多項(xiàng)式轉(zhuǎn)換將A1的實(shí)例轉(zhuǎn)換為A2的實(shí)例

STEP2–用H2算法求解A2的實(shí)例即多項(xiàng)式轉(zhuǎn)換可以認(rèn)為是只允許調(diào)用一次H2的多項(xiàng)式歸約571.5.4NP完全問(wèn)題類(lèi)(NPC)-多項(xiàng)式歸約（例）例1.22適定問(wèn)題多項(xiàng)式歸約為三精確覆蓋問(wèn)題（證明較繁，略）課后自己看書(shū)體會(huì)證明技巧

581.5.4NP完全問(wèn)題類(lèi)(NPC)–定義定義1.10（1）對(duì)于判定問(wèn)題A，若A

NP且NP中的任何一個(gè)問(wèn)題可在多項(xiàng)式時(shí)間內(nèi)歸約為A，則稱(chēng)A為NP完全問(wèn)題(NP-Complete或NPC).可以表示為A

NPC.NPC和NP-hard兩者的區(qū)別是:驗(yàn)證一個(gè)問(wèn)題A是否為NP-hard無(wú)須判斷A是否屬于NP.根據(jù)定義可知NPC

NPH.

當(dāng)已知一個(gè)問(wèn)題屬于NPC或NPH時(shí)，如果再遇到一個(gè)新問(wèn)題：（1）若已知問(wèn)題多項(xiàng)式歸約為新問(wèn)題，則新問(wèn)題屬于NPH;（2）對(duì)于判定問(wèn)題A，若NP中的任何一個(gè)問(wèn)題可在多項(xiàng)式時(shí)間歸約為判定問(wèn)題A，則稱(chēng)A為NP困難問(wèn)題(NP-hard或NPH).可以表示為A

NPH.

（2）若還可以驗(yàn)證新問(wèn)題屬于NP，則新問(wèn)題屬于NPC.

591.5.4NP完全問(wèn)題類(lèi)(NPC)–證明例1.23(Cook定理，1971）SAT

NPC.前面已經(jīng)證明SAT

NP，所以尚需證明：

任何一個(gè)NP問(wèn)題可以多項(xiàng)式歸約為SAT計(jì)算復(fù)雜性理論的奠基性工作之一：第一個(gè)被證明的NPC問(wèn)題！是證明許多其他NPC問(wèn)題的出發(fā)點(diǎn)基本思想：

若A

NP，則A存在非多項(xiàng)式時(shí)間算法（猜測(cè)解、驗(yàn)證解）。對(duì)猜測(cè)解、驗(yàn)證解的過(guò)程進(jìn)行分析，構(gòu)造一個(gè)SAT問(wèn)題?。ㄗC明細(xì)節(jié)較繁，略）601.5.4NP完全問(wèn)題類(lèi)(NPC)–證明（例）例1.24整數(shù)線性規(guī)劃（ILP）的判定問(wèn)題屬于NPC

例1.20已證明適定問(wèn)題多項(xiàng)式轉(zhuǎn)換為0-1線性規(guī)劃(ZOLP)的判定問(wèn)題ZOLP判定問(wèn)題屬于NPH與線性規(guī)劃的判定問(wèn)題屬于NP的證明類(lèi)似，可以證明：整數(shù)線性規(guī)劃的判定問(wèn)題屬于NP引理 如果ILP有可行解，則它有一個(gè)可行解推論：ZOLP多項(xiàng)式等價(jià)于ILP；ILP的判定問(wèn)題屬于NPC易知：ZOLP的判定問(wèn)題屬于NPZOLP判定問(wèn)題屬于NPC611.5.4NP完全問(wèn)題類(lèi)(NPC)–證明（例）例1.25三精確覆蓋（X3C）屬于NPC.SAT多項(xiàng)式歸約為X3C（例1.22）X3C∈NP（例1.19）X3C∈NPC例1.26（特殊）（0-1）背包判定問(wèn)題屬于NPC.X3C多項(xiàng)式變換為背包判定問(wèn)題（例1.21）背包判定問(wèn)題∈NP（易證）背包判定問(wèn)題∈NPC621.5.4NP完全問(wèn)題類(lèi)(NPC)–證明（例）例1.27（集合）劃分（PARTITION）問(wèn)題是NPC.PARTITION問(wèn)題：給定整數(shù)，是否存在{1,2,...,n}的一個(gè)子集S，使得？要證明PARTITION∈NPC，尚需證明：這是（特殊）（0-1）背包判定問(wèn)題的一個(gè)特殊情況，包的容積背包判定問(wèn)題∈NPPARTITION∈NP

所有NP問(wèn)題多項(xiàng)式轉(zhuǎn)換/歸約為集合劃分問(wèn)題，或：某個(gè)NPC問(wèn)題多項(xiàng)式轉(zhuǎn)換/歸約為集合劃分問(wèn)題可以證明：背包問(wèn)題多項(xiàng)式轉(zhuǎn)換為集合劃分問(wèn)題63觀察：1.5.4NP完全問(wèn)題類(lèi)(NPC)–證明（例）例1.27PARTITION問(wèn)題是NPC.（續(xù)）這個(gè)映射滿足“轉(zhuǎn)換”定義的性質(zhì)①-轉(zhuǎn)換的多項(xiàng)式性證明：背包問(wèn)題多項(xiàng)式轉(zhuǎn)換為集合劃分問(wèn)題給定0-1背包判定問(wèn)題的任何一個(gè)實(shí)例構(gòu)造集合劃分問(wèn)題的實(shí)例其中這個(gè)映射滿足“轉(zhuǎn)換”定義的性質(zhì)②-解的一一對(duì)應(yīng)性64(必要性)若存在{1,2,...,n}的子集S，使得，則存在{1,2,...,n+2}的一個(gè)子集S’=S∪{n+2}使得.

(充分性)若存在{1,2,...,n+2}的一個(gè)子集S’

使得

由于，因此S’含且只含n+1，n+2之一1.5.4NP完全問(wèn)題類(lèi)(NPC)–證明（例）例1.27PARTITION問(wèn)題是NPC.（續(xù)）存在{1,2,...,n}的子集S，使得的充分必要條件是存在{1,2,...,n+2}的一個(gè)子集S’使得.

于是存在{1,2,...,n}的子集S，使得即651.5.4NP完全問(wèn)題類(lèi)(NPC)–證明（例）易證：裝箱判定問(wèn)題屬于NP易證.

例1.28裝箱(BP)判定問(wèn)題是NPC.(注意：書(shū)上證明有漏洞)

給定正整數(shù)K及n個(gè)物品，尺寸為(正整數(shù))，是否能在K個(gè)尺寸為B(正整數(shù))的箱子中裝入這n個(gè)物品？要證明BP∈NPC，可將劃分問(wèn)題多項(xiàng)式轉(zhuǎn)換為BP給定正整數(shù),構(gòu)造BP問(wèn)題:K=2，，這一過(guò)程可以在多項(xiàng)式時(shí)間內(nèi)完成存在{1,2,...,n}的子集S，使得的充分必要條件是在K=2個(gè)尺寸為B的箱子中可以裝入這n個(gè)物品所以BP∈NPC（思考：正整數(shù)集合劃分問(wèn)題∈NPC）66強(qiáng)多項(xiàng)式算法/問(wèn)題1.5.4NP完全問(wèn)題類(lèi)(NPC)–補(bǔ)充說(shuō)明:算法復(fù)雜性研究中:常將算法的計(jì)算時(shí)間表示為：?jiǎn)栴}中的簡(jiǎn)單而典型的參數(shù)(如網(wǎng)絡(luò)優(yōu)化中n,m),

以及問(wèn)題中出現(xiàn)的數(shù)值(如弧上的權(quán))的最大值(按絕對(duì)值)K，等自變量的函數(shù)關(guān)系實(shí)際問(wèn)題的輸入規(guī)模/長(zhǎng)度一定是m,n和logK的一個(gè)多項(xiàng)式函數(shù).所以,如果一個(gè)算法是多項(xiàng)式時(shí)間算法,則運(yùn)行時(shí)間的上界一定也是m,n和logK的多項(xiàng)式函數(shù).

特別地,如果運(yùn)行時(shí)間C(I)的上界是m,n的多項(xiàng)式函數(shù)（即該多項(xiàng)式函數(shù)不包含logK）,則稱(chēng)相應(yīng)的算法為強(qiáng)多項(xiàng)式（StronglyPolynomial）時(shí)間算法，簡(jiǎn)稱(chēng)強(qiáng)多項(xiàng)式算法.

存在強(qiáng)多項(xiàng)式算法的問(wèn)題稱(chēng)為強(qiáng)多項(xiàng)式問(wèn)題.

67偽多項(xiàng)式算法、強(qiáng)NPC問(wèn)題1.5.4NP完全問(wèn)題類(lèi)(NPC)–補(bǔ)充說(shuō)明如果算法運(yùn)行時(shí)間的上界是m,n和K的多項(xiàng)式函數(shù)，則稱(chēng)相應(yīng)的算法為偽多項(xiàng)式（Pseudopolynomial）(時(shí)間)算法，或擬多項(xiàng)式(時(shí)間)算法。如果采用“一進(jìn)制”編碼（UnaryEncoding,即用x位表示一個(gè)正整數(shù)x），則偽多項(xiàng)式算法運(yùn)行時(shí)間的上界是實(shí)例輸入長(zhǎng)度的多項(xiàng)式函數(shù)。除非P=NP,否則不存在偽多項(xiàng)式算法的NPC問(wèn)題稱(chēng)為強(qiáng)NPC（

StronglyNPC）問(wèn)題，有時(shí)也稱(chēng)為Unary-NPC問(wèn)題。TSP、SAT等是強(qiáng)NPC問(wèn)題,而背包問(wèn)題則不是強(qiáng)NPC問(wèn)題.

由于采用“一進(jìn)制”編碼在當(dāng)前的計(jì)算機(jī)上是不現(xiàn)實(shí)的，所以一般來(lái)說(shuō),偽多項(xiàng)式算法并不是多項(xiàng)式算法.68Co-NP類(lèi)1.5.4NP完全問(wèn)題類(lèi)(NPC)–補(bǔ)充說(shuō)明例TSP問(wèn)題的余已知n，n階整數(shù)矩陣dij，整數(shù)K，所有的環(huán)游長(zhǎng)度都大于K嗎？但是，不能證明一個(gè)NP問(wèn)題的余問(wèn)題也是NP的！

（這是因?yàn)閷?duì)于NP問(wèn)題的否實(shí)例，我們前面并沒(méi)有關(guān)心其判定算法）定義對(duì)判定問(wèn)題A和B，如果B的所有是實(shí)例（編碼）正好都不是A的是實(shí)例（編碼），則稱(chēng)B是A的余（Complement），記B=定理若A∈P，則∈P定義所有NP問(wèn)題的余記為Co-NP；所有NPC問(wèn)題的余記為Co-NPC69多項(xiàng)式空間問(wèn)題1.5.4NP完全問(wèn)題類(lèi)(NPC)–補(bǔ)充說(shuō)明定義對(duì)一個(gè)問(wèn)題，如果存在一個(gè)算法，其運(yùn)算能被限制在以實(shí)例輸入長(zhǎng)度的多項(xiàng)式為界的空間內(nèi)進(jìn)行，則該問(wèn)題稱(chēng)為多項(xiàng)式空間的。所有多項(xiàng)式空間的問(wèn)題的集合稱(chēng)為PSPACE（多項(xiàng)式空間問(wèn)題類(lèi)）定理PPSPACE，NPPSPACE，Co-NPPSPACE有些問(wèn)題是不可計(jì)算的，如停機(jī)問(wèn)題定義若A∈PSPACE，且所有PSPACE問(wèn)題都可以多項(xiàng)式歸結(jié)為A，則A稱(chēng)為PSPACE完備的（PSPACE-Complete）。701.5.4NP完全問(wèn)題類(lèi)(NPC)–補(bǔ)充說(shuō)明想象的問(wèn)題類(lèi)示意圖

PNP

NPCco-NP

co-NPCPSPACE-COMPLETEPSPACEStonglyNPCStonglyPPseudo-PolynomialStonglyNPC的余711.5.4NP完全問(wèn)題類(lèi)(NPC)–補(bǔ)充說(shuō)明上圖中所有問(wèn)題類(lèi)可能最后都收縮為一個(gè)點(diǎn)-P

P=NP嗎？

----這是21世紀(jì)數(shù)學(xué)和計(jì)算機(jī)科學(xué)的挑戰(zhàn)性問(wèn)題之一72

最小樹(shù)與最小樹(shù)形圖

73最小樹(shù)問(wèn)題的例子例公路連接問(wèn)題某一地區(qū)有n個(gè)主要城市，現(xiàn)準(zhǔn)備修建高速公路把這些城市連接起來(lái)，

使得從其中任何一個(gè)城市都可以經(jīng)高速公路直接或間接到達(dá)另一個(gè)城市.假定已經(jīng)知道了任意兩個(gè)城市i和j之間修建高速公路的成本（費(fèi)用）wij(>0),那么應(yīng)任何決定在哪些城市間修建高速公路，使得總成本最??？

高速公路網(wǎng)正好構(gòu)成這個(gè)完全圖G的一個(gè)連通的支撐子圖T.

為了使得總建設(shè)成本最小,該子圖必須是無(wú)圈的

無(wú)圈連通圖稱(chēng)為樹(shù)，上面這樣一類(lèi)問(wèn)題稱(chēng)為最小樹(shù)問(wèn)題.742.1樹(shù)的基本概念–

定義定義2.1 無(wú)圈連通圖稱(chēng)為樹(shù)（tree）.無(wú)圈圖（即若干棵樹(shù)的并）稱(chēng)為森林或者簡(jiǎn)稱(chēng)林（forest）.如果一個(gè)圖的支撐子圖是一棵樹(shù)，則稱(chēng)這棵樹(shù)為該圖的支撐樹(shù)或者生成樹(shù)(spanningtree)，并稱(chēng)支撐樹(shù)中的弧為樹(shù)?。╰reearc），而不屬于支撐樹(shù)中的弧為非樹(shù)弧（nontreearc）.樹(shù)是一類(lèi)既簡(jiǎn)單而又非常重要的圖形，在計(jì)算機(jī)科學(xué)、有機(jī)化學(xué)、電網(wǎng)絡(luò)分析、最短連接及渠道設(shè)計(jì)等領(lǐng)域都有廣泛的應(yīng)用.在本節(jié)及下一節(jié)中，我們假設(shè)所討論的圖與網(wǎng)絡(luò)都是無(wú)向的.752.1樹(shù)的基本概念–

例例2.1含6個(gè)頂點(diǎn)的樹(shù)(非同構(gòu)的)：共有6種弧的條數(shù)=節(jié)點(diǎn)數(shù)-1

任何兩個(gè)頂點(diǎn)之間存在唯一的一條路762.1樹(shù)的基本概念-樹(shù)的等價(jià)定義引理2.1 G=（N，E）為一個(gè)圖，|N|=n，則下列命題等價(jià)：G是一棵樹(shù)；G連通，且|E|=n-1；G無(wú)圈，且|E|=n-1；G的任何兩個(gè)頂點(diǎn)之間存在唯一的一條路；G連通，且將G的任何一條弧刪去之后，該圖成為非連通圖；6)G無(wú)圈，且在G的任何兩個(gè)不相鄰頂點(diǎn)之間加入一條弧之后，該圖正好含有一個(gè)圈.

772.1樹(shù)的基本概念-最小樹(shù)的定義定義2.2 G=（N，E，W）為一個(gè)無(wú)向網(wǎng)絡(luò)，W為權(quán)函數(shù),即W:E→R

（這里R表示實(shí)數(shù)集合）.G中權(quán)最?。ù螅┑幕》Q(chēng)為最?。ù螅┗?如果H=（N1，E1）為G的一個(gè)子圖，子圖H的權(quán)定義為H所包含的所有弧的權(quán)之和，記為W(H)，即W（H）=.

弧e=(i，j)上的權(quán)常記為W(e),We

或w(e)，wij等

如果T*是G的一棵生成樹(shù)，且對(duì)G的任何一棵生成樹(shù)T都有W（T*

）≤W（T），則T*稱(chēng)為網(wǎng)絡(luò)G的最小支撐樹(shù)或者最小生成樹(shù)（MST：minimumspanningtree），或者簡(jiǎn)稱(chēng)最小樹(shù).圖的最小樹(shù)一般不唯一782.1樹(shù)的基本概念-最小樹(shù)的應(yīng)用一例例2.2二維矩陣數(shù)據(jù)存貯問(wèn)題某些蛋白質(zhì)的氨基酸序列差異不多，如果用二維矩陣的每一行記錄一種蛋白質(zhì)氨基酸序列，行與行之間的差異很小.其中一種方法是只存貯其中一行作為參照行，再存貯行與行之間的一部分差異信息，使得我們可以在需要時(shí)根據(jù)參照行生成所有其它行的元素.R1R3R2R4C13C12C24一般地，給定差異信息cij，如何確定存貯哪些行之間的差異元素,使得存貯空間盡可能少呢？這一問(wèn)題可以用最小樹(shù)問(wèn)題來(lái)描述:我們把矩陣每行作為一個(gè)節(jié)點(diǎn)構(gòu)成一個(gè)完全圖,第i個(gè)節(jié)點(diǎn)對(duì)應(yīng)于矩陣第i行，并令弧(i,j)上的權(quán)為cij.對(duì)于存貯問(wèn)題,實(shí)際上只需要存貯一行的元素,以及由該完全圖的一棵支撐樹(shù)所對(duì)應(yīng)的差異元素.最小樹(shù)就對(duì)應(yīng)于最優(yōu)的存貯方案. 79最小樹(shù)的“割最優(yōu)條件”2.1樹(shù)的基本概念-觀察：支撐樹(shù)刪去一條樹(shù)弧后形成兩棵子樹(shù)，圖中兩個(gè)端點(diǎn)分屬于兩棵子樹(shù)的弧形成一個(gè)割.

定理2.1生成樹(shù)T*是最小樹(shù)的充要條件是：對(duì)T*中的任何一條弧，將該弧從T*中刪除后形成的割中，該弧為最小弧.T*

必要性：很容易用反證法證明。ee’設(shè)w(e)

>

w(e’),令T’=T*-e+

e’，則w(T*)

>

w(T’)80T*e2.1樹(shù)的基本概念-

充分性.設(shè)T*是生成樹(shù)并滿足定理中的條件但不是最小樹(shù)，設(shè)最小樹(shù)為T(mén)0.記e

T*\T0,將e從T*中刪除后產(chǎn)生一個(gè)割.

將e加入T0后必然產(chǎn)生一個(gè)圈，該圈必然包括割中一條與e不同的弧e’，由假設(shè)，w(e)

w(e’).最小樹(shù)的“割最優(yōu)條件”重復(fù)這一過(guò)程，最后可以得到T*也是最小樹(shù)

e’由T0為最小樹(shù)，w(e)

w(e’),則w(e)

=

w(e’)，因此，T1=T0-e’+

e也是最小樹(shù)，與

T*有更多的公共弧

81最小樹(shù)的“圈最優(yōu)條件”2.1樹(shù)的基本概念-觀察：支撐樹(shù)加上一條非樹(shù)弧后包含一個(gè)唯一的圈T*定理2.1生成樹(shù)T*是最小樹(shù)的充要條件是：對(duì)屬于G但不屬于T*的任何一條弧，將該弧加入T*后形成的圈中，該弧為最大弧.

必要性：很容易用反證法證明。e’e若w(e)

<

w(e’)，令T’=T*-e’+e,則w(T*)

>

w(T’)，矛盾。822.1樹(shù)的基本概念-T*

充分性.設(shè)T*是生成樹(shù)并滿足定理2.2中的條件，我們來(lái)證明它也滿足定理2.1中的條件。最小樹(shù)的“圈最優(yōu)條件”

對(duì)T*中的任何一條弧e，將該弧從T*中刪除后形成的割中，考慮任何一條與e不同的弧e’.由定理2.2中的條件假設(shè)w(e’)

>

w(e)，即弧e為最小弧.ee’所以，滿足定理2.1中的條件。證畢。83貪婪算法的共性2.2最小樹(shù)算法-可以計(jì)算最小樹(shù),自然也可以計(jì)算連通圖的生成樹(shù).

算法開(kāi)始時(shí)假設(shè)某支撐子圖T的弧集合為空集;

算法運(yùn)行過(guò)程中不斷將一些弧加入到子圖中,并且每次加入T中的弧就會(huì)成為最后找到的最小樹(shù)的一員，而不會(huì)再?gòu)腡中退出.最直接的算法:“破圈法”

–

復(fù)雜度高，實(shí)施不易理論基礎(chǔ)-“割最優(yōu)條件”和“圈最優(yōu)條件”.如果算法結(jié)束時(shí)無(wú)法得到支撐樹(shù),則說(shuō)明圖不連通,因?yàn)檫B通圖一定有支撐樹(shù).可以計(jì)算最小樹(shù),變形后可以計(jì)算最大樹(shù)。貪婪算法(GreedyAlgorithm):842.2.1Kruskal算法（1956）

2.2最小樹(shù)算法基本思想：每次將一條權(quán)最小的弧加入子圖T中，并保證不形成圈.（避圈法）如果當(dāng)前弧加入后不形成圈,則加入這條弧,如果當(dāng)前弧加入后會(huì)形成圈,則不加入這條弧,并考慮下一條弧.STEP0. 令i=1,j=0,T=

.把G的邊按照權(quán)由小到大排列，即

;STEP1. 判斷T{ei}是否含圈.若含圈,轉(zhuǎn)STEP2,否則轉(zhuǎn)STEP3.STEP2. 令i=i+1.若i

m,轉(zhuǎn)STEP1;否則結(jié)束,此時(shí)G不連通,所以沒(méi)有最小樹(shù).STEP3. 令T=T{ei},j=j+1.若j=n-1,結(jié)束，T是最小樹(shù);否則轉(zhuǎn)STEP1.正確性：圈最優(yōu)條件852.2最小樹(shù)算法例2.3用Kruskal算法計(jì)算最小樹(shù)：2.2.1Kruskal算法（1956）

113254638524711325435286Kruskal算法的計(jì)算復(fù)雜性對(duì)m條弧進(jìn)行排序,其復(fù)雜度為判斷加入一條弧到T中時(shí)是否形成圈,其復(fù)雜度依賴(lài)于算法的具體實(shí)現(xiàn)方法.在算法的計(jì)算過(guò)程中,T是一個(gè)森林.如果該森林的每一棵子樹(shù)中的節(jié)點(diǎn)用一個(gè)單向鏈表表示，則可以方便地判斷圈.當(dāng)考慮弧(i,j)時(shí)，如果其端點(diǎn)屬于同一單向鏈表，則加入T后會(huì)形成圈；如果其端點(diǎn)分屬于兩個(gè)不同的單向鏈表，則加入T后不會(huì)形成圈，因此將這兩個(gè)鏈表合并成一個(gè)鏈表.由于處理每一條弧所需要的時(shí)間為O（n），因此這種實(shí)現(xiàn)方法的復(fù)雜度為O（nm）.

87Kruskal算法的計(jì)算復(fù)雜性改進(jìn)算法實(shí)現(xiàn)改進(jìn)：利用三個(gè)數(shù)組size-用來(lái)記錄每個(gè)鏈表中所含節(jié)點(diǎn)的個(gè)數(shù)(鏈表規(guī)模)；last-用來(lái)記錄每個(gè)鏈表中最后的節(jié)點(diǎn)編號(hào)first-用來(lái)記錄每個(gè)節(jié)點(diǎn)所在鏈表的第一個(gè)節(jié)點(diǎn).如果鏈表L={1，2，4，5}

，則size(L)=|L|=4,last(L)=5,first(1)=first(2)=first(4)=first(5)=1.

考慮?。╥，j）時(shí)，只需判斷first(i)與

first(j)是否相等,相等則端點(diǎn)屬于同一單向鏈表；否則合并鏈表.因此所有這些判斷所需要的計(jì)算時(shí)間為O(m).合并時(shí),我們總是把節(jié)點(diǎn)數(shù)較多的鏈表L’放在前面,而把節(jié)點(diǎn)數(shù)較少的鏈表L追加在后面.88Kruskal算法的計(jì)算復(fù)雜性合并后,對(duì)于size和last的修改非常容易,可以在常數(shù)時(shí)間內(nèi)完成;但對(duì)

first的修改必須對(duì)鏈表L中的每個(gè)元素(節(jié)點(diǎn))進(jìn)行,復(fù)雜度為O(h)，h=size(L).只需要證明獲得一個(gè)規(guī)模為n的鏈表的計(jì)算時(shí)間（操作次數(shù)）不超過(guò)

p2nlogn(這里p2

p1為常數(shù)）.這種合并最多進(jìn)行(n-1)次,對(duì)

first進(jìn)行修改的總的復(fù)雜度為記鏈表L追加在鏈表L’（,)后面而合并成一個(gè)鏈表時(shí)的計(jì)算時(shí)間（操作次數(shù)）不超過(guò)p1h（這里p1為常數(shù)）

數(shù)學(xué)歸納法:當(dāng)n=1時(shí)不需要進(jìn)行任何合并操作,因此結(jié)論成立.當(dāng)n>1時(shí),我們假設(shè)結(jié)論對(duì)規(guī)模小于n的鏈表均成立.設(shè)規(guī)模為n的鏈表由L追加在L’

后面合并而成,則h

n/2,h'=n-h.

p2hlogh+p2(n-h)log(n-h)+p1hp2hlog(n/2)+p2(n-h)logn+p2h=p2nlogn.

算法最后復(fù)雜度：O(mlogn)排序O（mlogn）；其他O（m+nlogn）.89Kruskal算法(改進(jìn)的實(shí)現(xiàn)）-例首先考慮弧（1，2），將L1，L2合并成一個(gè)鏈表（如L1）：L1={1，2}，size（L1）=2，

last（L1）=2，first（1）=first（2）=1.1132546385247L1={1}，size（L1）=1，

last（L1）=1，first（1）=1；L2={2}，size（L2）=1，

last（L2）=2，first（2）=2；L3={3}，size（L3）=1，

last（L3）=3，first（3）=3；L4={4}，size（L4）=1，

last（L4）=4，first（4）=4；L5={5}，size（L5）=1，

last（L5）=5，first（5）=5.

90Kruskal算法(改進(jìn)的實(shí)現(xiàn)）-例下一步考慮弧（1，4），將L1，L4合并成一個(gè)鏈表（如L1）：L1={1，2，4，5}，size（L1）=4，

last（L1）=5，first（1）=first（2）=first（4）=first（5）=1.下一步考慮弧（4，5），將L4，L5合并成一個(gè)鏈表（如L4）：L4={4，5}，size（L4）=2，

last（L4）=5，first（4）=