N18

18. 18.1.

Közelíto˝ algoritmusok A közelítés mértékének kifejezése

Legyen A algoritmus egy minimalizációs feladat közelíto˝ megoldása, amely adott bemenetre a C értéket számítja ki, míg az optimális megoldás (célfüggvény) értéke C∗ . A közelítés mértéke a C/C∗ hányados. Maximalizációs feladat esetén a közelítés mértéke (adott bemenetre) a C∗ /C hányados. Azt mondjuk, hogy az A közelíto˝ algoritmusnak ρ(n) a hibakorlát-függvénye, ha minden n-méretu˝ bemenetre

C C∗ max , C∗ C 



≤ ρ(n) .

(1)

Az olyan algoritmust, amely biztosítja a ρ(n) hibakorlát betartását, ρ(n)-közelíto˝ algoritmusnak nevezzünk. A közelíto˝ séma olyan algoritmus, amelynek bemenete nem csak a feladat egy konkrét esete, hanem egy ε > 0 szám, amelyre teljesül, hogy rögzített ε-ra (1 + ε)-közelíto˝ algoritmus. Azt mondjuk, hogy egy közelíto˝ séma polinomiális közelíto˝ séma, ha bármely ε > 0-ra az algoritmus futási ideje polinomiális a bemenet n méretében. ˝ Egy polinomiális közelíto˝ algoritmus futási ideje nagyon gyorsan nohet az ε hibakorlát csökkenésével, pl. O(n2/ε ).

18.2.

Minimális lefedo˝ csúcshalmaz

Egy G = (V, E) irányítatlan gráf csúcslefedése olyan V 0 ⊆ V csúcshalmaz, amelyre teljesül, hogy bármely (u, v) ∈ E élre u ∈ V 0 vagy v ∈ V 0 . A lefedés mértéke a lefedésben szereplo˝ csúcsok száma, |V 0 |. Feladat: minimális lefedo˝ csúcshalmaz Bemenet: G = (V, E) irányítatlan gráf Kimenet: V 0 ⊆ V lefedo˝ csúcshalmaz, hogy |V 0 | minimális. Nem ismeretes polinomiális ideju˝ megoldás (a feladat NP-teljes). KÖZ -L EFEDÉS(G = (V, E),C) begin

C := 0/ ; E := E ; while E 6= 0/ do begin ˝ legyen (u, v) ∈ E tetszoleges él; C := C ∪ {u, v}; forall (x, v) ∈ E É LTÖRÖL(E, x, v); forall (u, x) ∈ E É LTÖRÖL(E, u, x); end

18.1. tétel. A KÖZ -L EFEDÉS polinomiális 2-közelíto˝ algoritmus. Bizonyítás. Jelölje A azon élek halmazát, amelyeket a KÖZ -L EFEDÉS választott és legyen C∗ az optimális megoldás értéke. Mivel C∗ lefedés, ezért minden E -beli élnek, így az A-belieknek is legalább egyik végpontját tartalmazza, tehát

|C∗ | ≥ |A| Mivel minden (u, v) él választása során u ∈ / C és v ∈ / C, így

|C| = 2 |A| 1

b

c

a

e

d

f

g

b

c

a

e

(a) b

c

a

e

c

a

e

f

g

(b) d

f

g

b

c

a

e

(c) b

d

d

f

g

(d) d

f

g

b

c

a

e

(e)

d

f (f)

2

g

tehát

|C| = 2 |A| ≤ 2 |C∗ |



Az algoritmus futási ideje O(V + E).

18.3.

˝ Az utazóügynök feladat háromszösz egyenlotlenséggel.

Adott egy G = (V, E) teljes (minden u, v ∈ V pontpár esetén (u, v) ∈ E ) gráf és minden (u, v) ∈ E ) élhez egy c(u, v) nemnegatív súly (költség) van rendelve. Az utazó ügynök feladat olyan Hamilton-körút keresését jelenti, amelynek az összköltsége minimális. A Hamilton-körút olyan körút a gráfban, amely minden pontot (pontosan egyszer) tartalmaz. Minden A ⊆ E élhalmazra értelmezzük a c költségfüggvényt, mint az élek költségeinek összegét:

c(A) =

∑

c(u, v) .

(u,v)∈A

Számos gyakorlati probléma esetén a költségfüggvény olyan, hogy bármely két pont között a közvetlen út költsége ˝ nem nagyobb, mint bármely nem közvetlen út költsége, azaz teljesül a háromszög-egyenlotlenség:

c(u, w) ≤ c(u, v) + c(v, w) . KÖZ -U TAZÓ Ü GYNÖK(G, c) begin ˝ r := V tetszoleges pontja; MFF − Prim(G, c, F); H:=Preorder(F) end A KÖZ -U TAZÓ Ü GYNÖK algoritmus futási ideje Θ(E) = O(V 2 ). ˝ 18.2. tétel. Ha teljesül a háromszög-egyenlotlenség, akkor KÖZ -U TAZÓ Ü GYNÖK polinomiális 2-közelíto˝ algoritmus. ˝ Bizonyítás. Legyen H ∗ egy optimális Hamilton-körút. Mivel a körútból bármelyik élet eltávolítva feszítofát kapunk, ezért

c(F) ≤ c(H ∗ ) Legyen W a pontoknak az a sorozata, amely minden pontot kétszer tartalmaz, a Preorder bejárás során érintett sorrendben:

public static <E> void Preorder(FaPont<E> p, Sor<E> S){ if (p==null) return; S.SorBa(p.elem); FaPont<E> q=p.elsofiu; while (q!=null){ Preorder1(q, S); q=q.testver; } S.SorBa(p.elem); } 3

a

d

a

d

e b

f

a e

g

c

b

f

e g

c h (a)

a

(c)

d

e b

f

c

e g

b

f

c h

h (d)

f

h (b)

d

b c

h

a

d

(e)

2. ábra. 4

g

g

c(W ) = 2c(F) . ∗

c(W ) ≤ 2c(H )

(2) (3)

˝ ha minden pontnak csak az elso˝ elofordulását ˝ W nem körút, de körutat kapunk belole, tartjuk meg a sorozatban. Ha a W sorozatban u, x, v esetén töröljük az x pontot, akkor az azt jelenti, hogy u-ból közvetlenül megyünk v-be, tehát a ˝ ˝ mivel háromszög-egyenlotlenség miatt az összköltség nem no,

c(u, x) + c(x, v) ≥ c(u, v) ˝ ˝ úgy kapható, hogy minden pontnak csak az elso˝ elofordulását ˝ Mivel az algoritmus által eloállított H körút W -bol hagyjuk ˝ meg, ezért ismételten alkalmazva a háromszög-egyenlotlenséget, kapjuk, hogy

c(H) ≤ c(W ) = 2c(F) ≤ 2c(H ∗ )

(4)

 18.4.

Részletösszeg feladat

Bemenet: S = {x1 , . . . , xn } pozitív egész számok halmaza és t pozitív egész szám. Kimenet: R ⊆ S, hogy

t0 =

∑x≤t

x∈R

és t 0 maximális. Legyen L = ha1 , . . . , am i egész számok egy sorozata és x egész szám. Értelmezzük az L+x muveletet ˝ úgy, hogy

L + x = ha1 + x, . . . , am + xi Egy exponenciális ideju˝ algoritmus a részletösszeg feladatra: R ÉSZLETÖSSZEG(S,t) begin

n := |S|; L0 := h0i; for i:=1 to n do begin Li :=Összefésül(Li−1 , Li−1 + xi ); ˝ a t -nél nagyobb elemeket; távolítsuk el Li -bol end; return Ln maximális eleme; end Az algoritmus megértéséhez jelölje Pi azon értékek halmazát, amelyeket egy az {x1 , x2 , . . . , xi } részhalmazainak ˝ képezhetünk. Ha S = {1, 4, 5}, akkor összegeibol

P1 = {0, 1}, P2 = {0, 1, 4, 5}, P3 = {0, 1, 4, 5, 6, 9, 10} Pi = Pi−1 ∪ (Pi−1 + xi ) .(5) A R ÉSZLETÖSSZEG algoritmus futási ideje lr. esetben exponenciális (O(2n )), mert S minden részhalmazát megvizsgálja. 5

18.5.

Egy teljes polinomiális közelíto˝ séma

Egy teljes polinomiális közelíto˝ sémát kaphatunk, ha létrehozása után minden Li listát "megritkítunk". Az alapötlet az, hogy ha egy sorozat két eleme közel van egymáshoz, akkor egyiket elhagyhatjuk, mert a közelíto˝ megoldásban nincs ˝ ˝ Az L sorozat δ-val való ritkítása azt jelenti, hogy minden szükség mindkettore. Legyen 0 < δ < 1 ritkítási tényezo. eltávolított y elemhez maradjon olyan z a sorozatban, hogy

y ≤z≤y. 1+δ

(6)

Például, ha δ = 0.1

L = h10, 11, 12, 15, 20, 21, 22, 23, 24, 29i , akkor L ritkítása után marad:

L0 = h10, 12, 15, 20, 23, 29i ˝ ˝ A következo˝ eljárás egy L = hy1 , . . . , ym i bemeneti sorozatot ritkít Θ(m) idoben, feltételezve, hogy L nemcsökkenoen rendezett. R ITKÍT(L, δ) begin

m := |L|; L0 := hy1 i; utolso:=y1 ; for i:=2 to m do begin if yi > utolso ∗ (1 + δ) then begin Vegéhez(L0 , yi ); utolso:=yi end; end; return L0 end Egy közelíto˝ polinomiális séma 0 < ε < 1 "közelíto˝ paraméterrel": KÖZ -R ÉSZLETÖSSZEG(S,t, ε)

begin

n := |S|; L0 := h0i; for i:=1 to n do begin Li :=Összefésül(Li−1 , Li−1 + xi ); Li :=Ritkít(Li , ε); ˝ a t -nél nagyobb elemeket; távolítsuk el Li -bol end; z∗ := Ln maximális eleme; return z∗ ; end

6

18.3. tétel. A KÖZ -R ÉSZLETÖSSZEG egy teljes polinomiális közelíto˝ séma a részletösszeg feladatra. ˝ megtartja azt a tulajdonságot, hogy Li minden Bizonyítás. Li ritkítása és a t -nél nagyobb elemek eltávolítása Li -bol eleme egyben Pi eleme is. Tehát a kiszámított z∗ is S bizonyos részhalmazának az összege. Legyen y∗ ∈ Pn a feladat optimális megoldása. Ekkor z∗ ≤ y∗ . Azt kell megmutatni, hogy y∗ /z∗ ≤ 1 + ε. Azt is meg kell mutatni, hogy az algoritmus futási ideje mind 1/ε-nak, mind n-nek polinomiális függvénye. i-szerinti indukcióval megmutatható, hogy minden y ∈ Pi -hez van olyan z ∈ Li , hogy

y ≤z≤y (1 + ε/2n)i

(7)

˝ A fenti egyenlotlenségnek teljesülnie kell y∗ ∈ Pn -ra, így van olyan z ∈ Ln , hogy

y∗ ≤ z ≤ y∗ , n (1 + ε/2n) és így

y∗  ε n ≤ 1+ . z 2n

(8)

˝ o˝ egyenlotlenség, ˝ Mivel van olyan z ∈ Ln amelyre fennáll az eloz ennek teljesülnie kell Ln legnagyobb elemére, azaz z∗ -ra, tehát

ε n y∗  ≤ 1 + . z∗ 2n

(9)

Már csak azt kell belátni, hogy y∗ /z∗ ≤ 1 + ε. Ehhez megmutatjuk, hogy (1 + ε/2n) ≤ 1 + ε. A (16) limesz miatt tudjuk, hogy limn→∞ (1 + ε/2n)n = eε/2 . Mivel belátható, hogy n

d  ε n 1+ >0, dn 2n

(10)

n ezért a (1 + ε/2n) függvény n növekvo˝ függvénye és a eε/2 értékhez tart, ezért

 ε n 1+ ≤ eε/2 2n ≤ 1 + ε/2 + (ε/2)2

(11) (12)

≤ 1+ε

(13)

ex ≥ 1 + x ,

(14)

1 + x ≤ ex ≤ 1 + x + x2 .

(15)

˝ Felhasznált egyenlotlenségek: Minden x valós számra Ha |x| ≤ 1, a következo˝ közelítést kapjuk Ha x → 0, akkor a ex nek 1 + x-hez való közelítés elég jó:

ex = 1 + x + Θ(x2 ) .  x n lim 1 + = ex . n→∞ n

(16)

Ahhoz, hogy megmutassuk, hogy KÖZ -R ÉSZLETÖSSZEG teljes polinomiális közelíto˝ séma, megadunk egy korlátot ˝ Li hosszára. A ritkítás után Li két egymást követo˝ z és z0 elemére fenn kell állni a z0 /z > 1 + ε/2n egyenlotlenségnek. 7

˝ Azaz legalább különbözniük kell. Minden sorozat tartalmazza a 0, esetleg 1 és még legfeljebb j k 1 + ε/2n tényezoben log1+ε/2n t elemet. Az elemek száma minden Li -ben legfeljebb

lnt +2 ln(1 + ε/2n) 2n(1 + ε/2n) lnt ≤ +2 ε 4n lnt +2 ≤ ε

log1+ε/2n t + 2 =

.

 ˝ Felhasznált egyenlotlenségek:

ln(x + 1) = x −

x2 x3 x4 + − ··· 2 3 4

x ≤ ln(1 + x) ≤ x 1+x 0<ε<1

8