Mohó algoritmusok angolul: greedy algorithms, románul: algoritmi greedy 1. feladat. Gazdaságos telefonhálózat építése Bizonyos városok között lehet direkt telefonkapcsolatot kiépíteni, pl. x és y város között a költség k(x, y). Építsünk minimális költségű telefonhálózatot, hogy minden vároból lehessen telefonálni minden városba! A módszer: Kruskal algoritmusa Példa. 4
4
1 10 2 5 3 8
6
6
9
5
12
6 1
1
2
8
3
6
2 5
3
2 3
4
4 13 8 2
6
5 1 2
7
7
1
8
4
----------------------------------------------------------{1}, {2}, {3}, {4}, {5}, {6}, {7}, {8} ----------------------------------------------------------5,7 1 * {1}, {2}, {3}, {4}, {5,7}, {6}, [8} 7,8 2 * {1}, {2}, {3}, {4}, {5,7,8}, {6} 3,4 2 * {1}, {2}, {3,4}, {5,7,8}, {6} 3,8 3 * {1}, {2}, {3,4,5,7,8}, {6} 1,3 4 * {1,3,4,5,7,8}, {2}, {6} 4,8 4 2,3 5 * {1,2,3,4,5,7,8}, {6} 1,5 6 2,5 6 4,5 6 1,6 8 * {1,2,3,4,5,6,7,8} 3,5 9 1,2 10 5,6 12 5,8 13 -----------------------------------------------------------
A csillaggal megjelölt elemek a megoldást adják.
2
Összesen n városunk van: v1, v2, . . . vn. Az algoritmus leírásához tekintsük a direkt kapcsolotok E = {e1, e2, . . . , em } halmazát úgy, hogy k(ei) ≤ k(ei+1), minden i = 1, 2, . . . , m− 1 értékre. Egy ei két várost köt össze, pl. vk , vl . Halmazok helyett egy h = (h1, h2, . . . , hn ) vektort használunk, amelynek elemei kezdetben egyenlőek az indexükkel, ami arra utal, hogy különböző halmazok elemei. Amikor két halmazt egyesítünk, a megfelelő hi értékeket egyenlővé tesszük (egyik halmaz elemeinek hi értékeit a másik halmaz hi értékeire állítjuk.). Kruskal(E) 1. for j=1,2, . . . , n 2. do hj := j 3. i := 1 4. while h elemei különbözőek 5. do if (ei végpontjai vk , vl ) és (hk 6= hl ) 6. then kiír ei 7. for j:=1, 2,. . . , n 8. do if hj = hl 9. then hj := hk 10. i:=i+1 A megoldás mindig optimális. 3
2. feladat. Színezzünk ki egy térképet a lehető legkevesebb színnel! Legyenek a színek : 1, 2, . . .. Mindig a legkisebb számú színt használjuk, amely lehetséges. Nem ad mindig optimális megoldást. A megoldás függ a színezés sorrendjétől. Példa.
a 1 , b2 , a 3 , b1 , a 2 , b3
a1
b3 a2
#
b2
"! 3
b1
a
3 b3 2 a2
a1 2
#
1
b2 3
"! 3
b1 3
a2
a 1 , b1 , a 2 , b2 , a 3 , b3
4 b3 3 a2
a1 2
#
1
3 b2
"! 3
a 4 2 b1
Mi a hasonlóság e két példa megoldása között? Mindkettő mohó algoritmus. Lokális optimumot használ a globális optimum meghatározására. Egy adott L halmaz bizonyos tulajdonságú M részhalmazát keressük. Kezdetben M üres, és mindig a legigéretesebb elemmel bővítjük. Van mikor a megoldás optimális, van mikor nem (ekkor a neve: heurisztikus mohó algoritmus). Be kell bizonyítani, hogy a megoldás optimális. 4
Pénzváltás. Feladat: a lehető legkevesebb bankjeggyel (érmével) fizessünk ki egy összeget. Mohó stratégia: mindig a legnagyobb címlettel próbálkozunk. Ha a lehetséges címletek: 1,5,8,10, a mohó megoldás nem mindig optimális. 13=10+1+1+1, az optimális 13=8+5. Ha a lehetséges címletek: 1,5,10,25, a mohó megoldás mindig optimális.
5
Huffman-kód a b c d e f gyakoriság (ezrekben) 45 13 12 16 9 5 fix hosszú kód 000 001 010 011 100 101 változó hosszú kód 0 101 100 111 1101 1100 100 000 betűs szövegben az a 45 000-szer, a b 13 000szer stb. fordul elő: fix esetben: 300 000 hosszú változó esetben: 224 000 hosszú mert (45 · 1 + 13 · 3 + 12 · 3 + 16 · 3 + 9 · 4 + 5 · 4) · 1000 = 224000
0
1
0
1
a:45
0
58
0
14
1
0
b:13
c:12
a:45 0
0
d:16
e:9
1
1
14
1
55
28
1
86
0
100
100
25
0
30
1
0
f:5 c:12
0 f:5
6
14
b:13
0010110100 ⇒ 0.0.101.101.100 ⇒ aabbc
1
d:16
1
e:9
Hátizsákfeladat Adottak: n tárgy si tömeggel (súllyal), ei értékkel S súlykapacitású hátizsák Feladat: Maximális nyereséggel pakoljuk meg a hátizsákot, ha egy tárgyból le is vághatunk. ("töredékes hátizsák"-feladat) mohó: érték/súly csökkenő sorrendjében pakolunk — optimális Ha csak egész tárgyakat helyezhetünk el, akkor nem mindig optimális. Példa: S = 110, n = 8 ei : si : ei/si :
11 1 11
21 11 1.9
31 21 1.47
33 23 1.43
43 33 1.3
53 43 1.23
55 45 1.22
65 55 1.18
Megoldás: mohó: 1, 11, 21, 23, 33 összeg = 89, érték = 139 optimális: 1, 11, 21, 33, 43 összeg = 109, érték = 159 töredékes hátizsák: 1, 11, 21, 23, 33, 21 (a 43-ból) összeg = 110, érték = 164.23 7
Ütemezés 1 Feladat: 3 processzoron 9 programot futtatni a lehető legrövidebb idő alatt. A programok időtartamai: 3, 5, 6, 10, 11, 14, 15, 18, 20 másodperc. leghosszabb először P1 20 P2
18
6
14
legrövidebb először P1 3 10
P3
3
11
15
P3
P2
10
5
5
15
11
6
35 mp.
18 14
40 mp.
20
optimális P1
20
P2
18
P3
15
34 mp.
14 11 10
5 6
8
3
Ütemezés 2 Feladat: n beteg kezelése úgy, hogy az összvárakozás minimális legyen. n = 3 t1 = 60, t2 = 10, t3 = 30. sorrend 1,2,3 1,3,2 2,3,1 2,1,3 3,1,2 3,2,1
összvárakozási idő 0+60+(60+10)=130 0+60+(60+30)=150 0+10+(10+30)= 50 0 +10+(10+60)=80 0+30+(30+60)=120 0+30+(30+10)=70
mohó: t1 ≤ t2 ≤ . . . tn sorrendben vizsgálunk — a megoldás mindig optimális
9
Eseménykiválasztás ai esemény az [si, fi ) időintervallumban történik (i = 1, 2, . . . , n). Feladat: Válasszunk ki minél több eseményt, amelyek nem fedik egymást időben. mohó: rendezzük fi szerint növekvő sorrendbe, és válasszuk ki azokat, amelyek nem fedik egymást — optimális i 1 2 3 4 5 6 7 8 9 10 11 si 1 3 0 5 3 5 6 8 8 2 12 fi 4 5 6 7 8 9 10 11 12 13 14 optimális: a1, a4, a8, a11 (szintén jó: a2, a4, a9, a11)
10
Huzalozás Feladat: legrövidebb huzallal kössünk össze egy-egy fekete és fehér korongot. z
j
z
z
j
j
j
z
1+1+1+3=6
mohó: balról jobbra első fekete-fehér pár, "töröljük", majd folytatjuk — optimális
11
Robotok a sakktáblán Egy robot bal-felső sarokból indul, mehet jobbra és lefele. Feladat: minimális számú robot szedje össze az összes érmét a tábláról. R
R
e
mohó:
e e
e
e e e e
? -e ?e -e ?
-e
e-e-e ? e ?
jobbra megy, ha van a sorban érme, különben egyet lefele, majd ismétli — optimális
12
Utazó ügynök problémája
– mindig a legközelebbi városba megy – nem optimális mohó: A,B,D,B,C,E optimális: A,D,B,C,E
16 14
13
Általános leírás Adott az L halmaz, egy P tulajdonság az L részhalmazaira (igaz v. hamis). Keresünk egy optimális M részhalmazt. Mohó(L, P) 1. M := ∅ 2. while (M nem megoldás) és (L 6= ∅) 3. do válasszuk ki L-ből a legigéretesebb x elemet 4. L := L \ {x} 5. if P(M ∪ {x}) igaz 6. then M := M ∪ {x} 7. if M megoldás 8. then return M 9. else return Nincs megoldás
Sokszor előfeldolgozást végzünk (pl. rendezzük L elemeit), ekkor a 3. lépésnél mindig a következő elemet választjuk. L minden elemét csak egyszer vizsgáljuk.
14
