算法分析與設(shè)計(jì)-2016第12講

1、第12講-2016山東大學(xué)計(jì)算機(jī)學(xué)院近似性能比為2，是指最壞為2，好的可能很好，不看最好有多好，只看最壞有多壞。絕對(duì)近似性能比：RA=infr1|所有實(shí)例ID(), RA(I)r，可以找到r。找一個(gè)數(shù)r，所有實(shí)例近似性能比都比r小，r最小能小到多少。 只能證明算法近似性能比RA(I)2，則還需要想辦法證明RA(I)r 0, 存在有x X, 使 x Q/w32Q-1/Q=2這個(gè)算法的近似性能比可以無限接近11/9，但不會(huì)比11/9更小了。a2a1a6a5a4a3a7第一類，6m個(gè)第二類，6m個(gè)第三類，6m個(gè)第四類，12m個(gè)233444413R(I) r，r 11/9任意，存在r 11/9+ 7.

2、2：近似算法設(shè)計(jì)滿足三角不等式的貨郎問題：實(shí)例：城市集合C=c1,c2,cm, 城市之間距離：d(ci,cj)Z+,d(ci,cj)+d(cj,ck)d(ci,ck), ci, cj, ckC。詢問：求城市排列：c(1)c(2)c(m)，或頂點(diǎn)排列，使該排列表示的貨郎旅游長度最短。相當(dāng)于給定滿足三角不等式邊長的完全圖G。將城市看成圖G的點(diǎn)，G = (V, E)，V = v1,v2,vm*什么是歐拉圖：每個(gè)點(diǎn)的度數(shù)為偶數(shù)每個(gè)點(diǎn)的度數(shù)為偶數(shù)。能夠走遍每條邊，每條邊只走一次的無向圖。*任意圖的性質(zhì)：奇數(shù)度的點(diǎn)的個(gè)數(shù)為偶數(shù)個(gè)。 ijk*在歐拉圖上找歐拉回路，多項(xiàng)式時(shí)間可解的。走遍所有邊但邊不重復(fù)的點(diǎn)序

3、列。點(diǎn)允許重復(fù)。舉個(gè)例子這是歐拉回路的例子。 7654321歐拉回路：1,2,3,5,4,3,6,2,7,1*圖的最小生成樹問題是多項(xiàng)式時(shí)間可解答的。 a h g f c d b a h g f e c d b e 1 1 a h g f e c d b a g f e d b c 2 h a h g f c d b a h g f e c d b e 1 1 a h g f e c d b a g f e d b c 2 h acbcdedgfghgdcaacb-de-gf-h-a歐拉回路:acbcdedgfghgdca抄近路：acbdegfha把重復(fù)的去掉就可以抄近路。 a g f e d

4、 b c 2 h a h g f e c d b 算法：MST(minimum spanning tree algorithm)step1對(duì)G調(diào)用最小生成樹算法得到樹T=(V, ET)。step2復(fù)制T的每條邊得到歐拉圖D=(V, ED)step3在D中求歐拉回路v(1),v(2),v(k),v(2m-2)v(1)。step4抄近路得到貨郎旅游v(1)=v(1),v(2),v(k),v(m)v(1) 定理：RMST(I)2。證明：w( )表示權(quán)值。表示權(quán)值。(1)w(T)OPT(I)/最短的貨郎旅游去掉一條邊是一棵樹。最短的貨郎旅游去掉一條邊是一棵樹。這棵樹的邊權(quán)之和不小于這棵樹的邊權(quán)之和不小

5、于w(T)，所以，所以w(T)OPT(I)。 三角不等式什么是歐拉圖：每個(gè)點(diǎn)的度數(shù)為偶數(shù)。任意圖的性質(zhì)：奇數(shù)度點(diǎn)的個(gè)數(shù)為偶數(shù)個(gè)。一個(gè)算法A說明好和懷，要找到一個(gè)界C，使得RAC，就說算法A的近似度為C，如果C是一個(gè)常數(shù)，就叫常數(shù)近似算法。C有時(shí)也不一定是常數(shù)，現(xiàn)在有各種類型的近似算法。前面性質(zhì)：T中度數(shù)為奇數(shù)的點(diǎn)的個(gè)數(shù)為偶數(shù)個(gè)中度數(shù)為奇數(shù)的點(diǎn)的個(gè)數(shù)為偶數(shù)個(gè)。實(shí)際上不用復(fù)制每條邊得到歐拉圖，只需要加上一半條數(shù)的邊就能形成歐拉圖。若有2k個(gè)頂點(diǎn)的度數(shù)為奇數(shù)，則增加k條邊就可使圖變?yōu)闅W拉圖。但增加哪k條邊為好呢？對(duì)集：互相獨(dú)立的邊集， 偶數(shù)個(gè)頂點(diǎn)的完全圖，每條邊有權(quán)重。最小對(duì)集：權(quán)重之和最小的對(duì)集。

6、問題：?jiǎn)栴}：實(shí)例：偶數(shù)個(gè)點(diǎn)的完全圖，實(shí)例：偶數(shù)個(gè)點(diǎn)的完全圖，每條邊有權(quán)重。詢問：求圖中權(quán)重之和最小的對(duì)集。詢問：求圖中權(quán)重之和最小的對(duì)集。這個(gè)問題是多項(xiàng)式時(shí)間可計(jì)算的。這個(gè)問題是多項(xiàng)式時(shí)間可計(jì)算的。1234W(i,j)算法：MST(minimum spanning tree algorithm)step1對(duì)G調(diào)用最小生成樹算法得到樹T=(V, ET)。step2復(fù)制T的每條邊得到歐拉圖D=(V, ED)step3在D中求歐拉回路v(1),v(2),v(k),v(2m-2)v(1)。step4抄近路得到貨郎旅游v(1)=v(1),v(2),v(k),v(m)v(1) 1 1 1 1 1 1 2

7、2 2 2 2 2 3 1 a b c d e f 2 1 1 1 1 1 a b c d e f 1 1 1 1 1 a b c d e f 1 1 2 1 2 a b c d e f 1 1 2 2 2 2 1 a c e f 1 1 1 1 1 1 2 2 2 2 2 2 3 1 a b c d e f 2 1 1 1 1 1 a b c d e f 1 1 1 1 1 a b c d e f 1 1 2 1 2 a b c d e f v1,v2,v3,v4, ,v2k-1v2k,v1d(v1,v2)+d(v2,v3)+d(v2k-1,v2k)+d(v2k,v1)OPT(I)一定存在一

8、個(gè)對(duì)集長度不超過OPT(I)/2v1v2v3v4v5v6v7v8 1 1 1 1 1 1 2 2 2 2 2 2 3 1 a b c d e f 2 d(v1,v2) + + d(v2k-1,v2k) OPT(I)/2，或d(v2,v3) + + d(v2k,v1)OPT(I)/2v1v2v3v4v5v6v7v8v1v2,v3v4,v5v6,v7v8是對(duì)集M1v2v3,v4v5,v6v7,v8v1也是對(duì)集M2兩個(gè)對(duì)集中有一個(gè)的長度OPT(I)/2M是最小對(duì)集，必有w(M)minw(M1),w(M2) OPT(I)/2所以，w(T)+w(M) 3OPT(I)/2MM(I)w(T)+w(M) 3O

9、PT(I)/2非獨(dú)立任務(wù)這個(gè)問題前面沒有講過，沒有半序關(guān)系，是NP-Hard，有半序關(guān)系也是NP-hard，可以證明。說明：(1)任務(wù)主次表：L=ti1, ti2,tin，一個(gè)挑選任務(wù)安排的次序表。最后任務(wù)的排工情況與主次表有關(guān)。(2)若要排工ti，必須ti任務(wù)之前的任務(wù)全部完成后才行。待加工的任務(wù) tk：若不存在尚未完成的ti，titk，待加工與未加工不同。計(jì)算排工的算法如下：L = ti1, ti2, tin ，非空閑算法。Step1：開始所有處理機(jī)空閑，所有任務(wù)未加工。Step2：對(duì)L從左到右掃描，判定每個(gè)任務(wù)tj是否處于待加工。若tj處于待加工，則將tj安排到下標(biāo)最小的空閑處理機(jī)Pi上

10、加工。直到所有任務(wù)加工完。待加工狀態(tài)：一個(gè)任務(wù)的前驅(qū)任務(wù)都已完成了。機(jī)器排好序，任務(wù)排好序，順序安排任務(wù)。觀察：若任務(wù)主次表恰好，則非空閑策略得到的排工表是最優(yōu)的。 主次表：L=t1, t2, t3, t5, t6, t4, t9, t11, t8, t7, t10兩臺(tái)處理機(jī)，則排工情況如下： 非空閑算法得到完成任務(wù)時(shí)間為：37=NI(I,L)主次表：L=t1, t2, t3, t5, t6, t4, t9, t11, t8, t7, t10兩臺(tái)處理機(jī)，則排工情況如下： 非空閑算法得到完成任務(wù)時(shí)間為：37=NI(I,L)主次表：L=t1, t2, t3, t5, t6, t4, t9, t11

11、, t8, t7, t10兩臺(tái)處理機(jī)，則排工情況如下： 非空閑算法得到完成任務(wù)時(shí)間為：37=NI(I,L)主次表：L=t1, t2, t3, t5, t6, t4, t9, t11, t8, t7, t10兩臺(tái)處理機(jī)，則排工情況如下： 非空閑算法得到完成任務(wù)時(shí)間為：37=NI(I,L)主次表：L=t1, t2, t3, t5, t6, t4, t9, t11, t8, t7, t10兩臺(tái)處理機(jī)，則排工情況如下： 非空閑算法得到完成任務(wù)時(shí)間為：37=NI(I,L)主次表：L=t1, t2, t3, t5, t6, t4, t9, t11, t8, t7, t10兩臺(tái)處理機(jī)，則排工情況如下： 非空

12、閑算法得到完成任務(wù)時(shí)間為：37=NI(I,L)主次表：L=t1, t2, t3, t5, t6, t4, t9, t11, t8, t7, t10兩臺(tái)處理機(jī)，則排工情況如下： 非空閑算法得到完成任務(wù)時(shí)間為：37=NI(I,L)主次表：L=t1, t2, t3, t5, t6, t4, t9, t11, t8, t7, t10兩臺(tái)處理機(jī)，則排工情況如下： 非空閑算法得到完成任務(wù)時(shí)間為：37=NI(I,L)主次表：L=t1, t2, t3, t5, t6, t4, t9, t11, t8, t7, t10兩臺(tái)處理機(jī)，則排工情況如下： 非空閑算法得到完成任務(wù)時(shí)間為：37=NI(I,L)主次表：L=t

13、1, t2, t3, t5, t6, t4, t9, t11, t8, t7, t10兩臺(tái)處理機(jī)，則排工情況如下： 非空閑算法得到完成任務(wù)時(shí)間為：37=NI(I,L)主次表：L=t1, t2, t3, t5, t6, t4, t9, t11, t8, t7, t10兩臺(tái)處理機(jī)，則排工情況如下： 非空閑算法得到完成任務(wù)時(shí)間為：37=NI(I,L)ti是tj的前驅(qū) P1 P2 5 6 3 10 9 4 4 5 2 3 8 T10 T7 T4 T5 T2 T1 T8 T11 T9 T6 T3 123*這個(gè)要說明一下為什么，這回真是有點(diǎn)搞清楚了，這條通路肯定存在，要證明的。若通路上一任務(wù)前面的所有任務(wù)

14、都沒在一個(gè)空閑區(qū)間安排，則在此空閑區(qū)間安排這個(gè)任務(wù)即可。1kN(I,L)那條通路上的任務(wù)加工長度之和OPT(I)OPT(I)算法LPTStep1：將任務(wù)排序使：形成主次表：L=T1,T2,Tn，t1t2tn。Step2：對(duì)主次表從1到n掃描，若有空閑機(jī)器，則將任務(wù)安排到空閑機(jī)器上加工。直到完成。 *下面一個(gè)問題：獨(dú)立任務(wù)排工。前面的多任務(wù)排工問題中，任務(wù)和任務(wù)之間沒有半序關(guān)系。就是獨(dú)立任務(wù)排工。任務(wù)：T1,T2,Tn，相應(yīng)的加工長度：t1,t2,tn。下面算法思想是先排時(shí)間長的，后排時(shí)間短的。取前取前k個(gè)任務(wù)形成實(shí)例個(gè)任務(wù)形成實(shí)例I1，則，則OPT(I) OPT(I1)，LPT(I)=LPT(I1)I1:T1,TkI:T1,Tk,TnOPT(I) OPT(I1), LPT(I)=LPT(I1)LPT(I)/OPT(I)=LPT(I1)/OPT(I) LPT(I1)/OPT(I1)4/3-1/(3m)所有機(jī)器非空閑P1T1(t1=2m-1)T2m(t=m)T2m+1P2T2(t2=2