5
Minim´ aln´ı kostry, Hladov´ y algoritmus
Kromˇe teoretick´ych “hr´atek” maj´ı kostry graf˚ u (Odd´ıl 4.4) n´asleduj´ıc´ı d˚ uleˇzit´e praktick´e pouˇzit´ı: Dˇr´ıve jsme uvaˇzovali spojen´ı v grafech cestami jdouc´ımi z jednoho m´ısta do druh´eho, ale nyn´ı se pod´ıv´ame na jin´y zp˚ usob “propojov´an´ı” vˇsech vrchol˚ u grafu najednou. Vezmˇeme si tˇreba poˇzadavky propojen´ı dom˚ u elektrick´ym rozvodem, propojen´ı ˇskol internetem, atd. Zde n´as ani tak nezaj´ımaj´ı d´elky jednotliv´ych cest mezi propojen´ymi body, ale hlavnˇe celkov´a d´elka ˇci cena veden´ı/spojen´ı, kter´e mus´ıme postavit. 2 Naˇsim c´ılem je tedy naj´ıt minim´aln´ı souvisl´y podgraf dan´eho grafu, tedy minim´aln´ı zp˚ usob propojen´ı (v dan´ych podm´ınk´ach), ve kter´em existuj´ı cesty mezi kaˇzdou dvojic´ı vrchol˚ u.
Struˇ cn´ y pˇrehled lekce ˇ sen´ı probl´emu minim´aln´ı kostry v grafu – hladov´y a Jarn´ık˚ • Reˇ uv algoritmus. • Obecn´e pojet´ı hladov´eho algoritmu. • Matroidy – struktury, na nichˇz hladov´y algoritmus vˇzdy funguje. Petr Hlinˇen´ y, FI MU Brno
1
FI: MA010: Kostry, Hladov´ y algoritmus
5.1
Hled´ an´ı minim´ aln´ı kostry
Probl´ em 5.1. Probl´ em minim´ aln´ı kostry (MST) Je d´an (souvisl´y) v´aˇzen´y graf G, w s nez´aporn´ym ohodnocen´ım hran w. Ot´azkou je naj´ıt kostru T v G, kter´a m´a nejmenˇs´ı moˇzn´e celkov´e ohodnocen´ı. Form´alnˇe X w(e) . M ST = min kostra T ⊂G
e∈E(T )
Kostra dan´eho grafu je minim´ aln´ı podgraf, kter´ y zachov´ av´ a souvislost kaˇzd´e komponenty p˚ uvodn´ıho grafu. Proto n´ am vlastnˇe ukazuje “minim´ aln´ı propojen´ı” dan´ ych vrchol˚ u, ve kter´em jeˇstˇe existuj´ı cesty mezi vˇsemi dvojicemi, kter´e byly propojeny i p˚ uvodnˇe.
Petr Hlinˇen´ y, FI MU Brno
2
FI: MA010: Kostry, Hladov´ y algoritmus
Praktickou formulac´ı probl´emu je tˇreba propojen´ı dom˚ u elektrick´ ym rozvodem, ˇskol internetem, atd. Jedn´ a se tady o zad´ an´ı, ve kter´ ych n´ as zaj´ım´ a pˇredevˇs´ım celkov´ a d´elka ˇci cena propojen´ı, kter´e je tˇreba vytvoˇrit. Pˇr´ıklad je uveden na n´ asleduj´ıc´ım obr´ azku i s vyznaˇcenou minim´ aln´ı kostrou vpravo. 3
4
s
s
2
3
1
3
s
3
s 1
s 4
2
s 1 2
1
2
s
s 2
3
s
3
1
2
s
s
1 2
1
4
s
s
s 1
s2
s 4
2
Algoritmus 5.2. Hladov´ y“ pro minim´ aln´ı kostru. ” Je d´an souvisl´y v´aˇzen´y graf G, w s nez´aporn´ym ohodnocen´ım hran w. – Seˇrad´ıme hrany grafu G vzestupnˇe podle jejich ohodnocen´ı, tj. w(e1 ) ≤ w(e2 ) ≤ · · · ≤ w(em ). 2 – Zaˇcneme s pr´azdnou mnoˇzinou hran T = ∅ pro kostru. – Pro i = 1, 2, . . . , m vezmeme hranu ei a pokud T ∪ {ei } nevytv´aˇr´ı kruˇznici, pˇrid´ame ei do T . Jinak ei “zahod´ıme”. 2 – Na konci mnoˇzina T obsahuje hrany minim´aln´ı kostry v´aˇzen´eho grafu G, w. Petr Hlinˇen´ y, FI MU Brno
3
FI: MA010: Kostry, Hladov´ y algoritmus
Pro ilustraci si uk´ aˇzeme postup hladov´eho algoritmu pro vyhled´ an´ı kostry v´ yˇse zakreslen´eho grafu. Hrany si nejprve seˇrad´ıme podle jejich vah 1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 4, 4. V obr´ azku pr˚ ubˇehu algoritmu pouˇz´ıv´ ame tlust´e ˇc´ ary pro vybran´e hrany kostry a teˇckovan´e ˇc´ ary pro zahozen´e hrany. Hrany ted’ postupnˇe pˇrid´ av´ ame do kostry / zahazujeme. . . 3
4
s
s
2
3
1
3
s
s 1
s 4
3
s
s
2
3
s 1
s
3
s 2
3
s 1 2
1
2
s
2
s 2
4
s
1
s 4
s 4
3
2
s
s
s 1
1 2
1
s
s
2
s
2
1
2
1
3
s
3
s
3
1
2
4
s
s
1
2
s
4
s 2
1
1
3
s
s 1
s 4
s 2
Z´ısk´ ame tak minim´ aln´ı kostru velikosti 1 + 2 + 2 + 3 + 1 + 1 + 2 = 12, kter´ a je v tomto pˇr´ıpadˇe (n´ ahodou) cestou, na posledn´ım obr´ azku vpravo. Poznamen´ av´ ame, ˇze pˇri jin´em seˇrazen´ı hran stejn´e v´ ahy by kostra mohla vyj´ıt jinak, ale vˇzdy bude m´ıt stejnou velikost 12. Petr Hlinˇen´ y, FI MU Brno
4
FI: MA010: Kostry, Hladov´ y algoritmus
D˚ ukaz spr´avnosti Algoritmu 5.2: Necht’ T je mnoˇzina hran z´ıskan´a v Algoritmu 5.2 a necht’ hrany jsou jiˇz seˇrazen´e w(e1 ) ≤ w(e2 ) ≤ · · · ≤ w(em ). Vezmˇeme mnoˇzinu hran T0 t´e minim´aln´ı kostry (m˚ uˇze jich b´yt v´ıce se stejnou hodnotou), kter´a se s T shoduje na co nejv´ıce prvn´ıch hran´ach. Pokud T0 = T , algoritmus pracoval spr´avnˇe. 2 Pˇredpokl´adejme tedy, ˇze T0 6= T , a uk´aˇzeme spor, tj. ˇze toto nem˚ uˇze ve skuteˇcnosti nastat. Oznaˇcme j > 0 takov´y index, ˇze se mnoˇziny T0 a T shoduj´ı na prvn´ıch j − 1 hran´ach e1 , . . . , ej−1 , ale neshoduj´ı se na ej . To znamen´a, ˇze ej ∈ T , ale ej 6∈ T0 . (Jistˇe nem˚ uˇze nastat ej 6∈ T , ale ej ∈ T0 .) 2 Podle D˚ usledku 4.5 obsahuje graf na hran´ach T0 ∪{ej } pr´avˇe jednu kruˇznici C. Kruˇznice C vˇsak nem˚ uˇze b´yt obsaˇzena v nalezen´e kostˇre T , a proto existuje hrana ek v C, kter´a ek 6∈ T a z´aroveˇn k > j. Potom vˇsak je w(ek ) ≥ w(ej ) podle naˇseho seˇrazen´ı hran, a tud´ıˇz kostra na hran´ach T0 \ {ek } ∪ {ej } (vznikl´a nahrazen´ım hrany ek hranou ej ) nen´ı horˇs´ı neˇz T0 a mˇeli jsme ji v naˇs´ı ´ uvaze zvolit m´ısto T0 . To je hledan´y spor. 2 2 Spr´ avn´ y pohled na pˇredchoz´ı d˚ ukaz by mˇel b´ yt n´ asledovn´ y: Pˇredpokl´ adali jsme, ˇze nalezen´ a kostra T se s nˇekterou optim´ aln´ı kostrou shoduje aspoˇ n na prvn´ıch j − 1 hran´ ach. Pot´e jsme uk´ azali, ˇze nˇekterou dalˇs´ı hranu ek v (pˇredpokl´ adan´e) optim´ aln´ı kostˇre lze zamˇenit hranou ej , a tud´ıˇz dos´ ahnout shodu aspoˇ n na prvn´ıch j hran´ ach. Dalˇs´ımi iteracemi z´ amˇen uk´ aˇzeme u ´plnou shodu naˇs´ı nalezen´e kostry T s nˇekterou optim´ aln´ı kostrou. V naˇsem d˚ ukaze jsme se vlastnˇe zamˇeˇrili na fakt, ˇze ta posledn´ı iterace z´ amˇen nem˚ uˇze selhat. Nakreslete si tento d˚ ukaz obr´ azkem! Petr Hlinˇen´ y, FI MU Brno
5
FI: MA010: Kostry, Hladov´ y algoritmus
Z´akladn´ı hladov´y algoritmus pro hled´an´ı minim´aln´ı kostry grafu byl poprv´e explicitnˇe pops´an Kruskalem, ale uˇz dˇr´ıve byly objeveny jeho podobn´e varianty, kter´e zde jen struˇcnˇe zm´ın´ıme. Algoritmus 5.3. Jarn´ık˚ uv pro minim´ aln´ı kostru. Hrany na zaˇc´atku neseˇrazujeme, ale zaˇcneme kostru vytv´aˇret z jednoho vrcholu a v kaˇzd´em kroku pˇrid´ame nejmenˇs´ı z hran, kter´e vedou z jiˇz vytvoˇren´eho podstromu do zbytku grafu. 2 Pozn´ amka: Tento algoritmus je velmi vhodn´ y pro praktick´e v´ ypoˇcty a je dodnes ˇsiroce pouˇz´ıvan´ y. M´ alokdo ve svˇetˇe vˇsak v´ı, ˇze poch´ az´ı od Vojtˇecha Jarn´ıka, zn´ am´eho ˇcesk´eho matematika — ve svˇetov´e literatuˇre se obvykle pˇripisuje Ameriˇcanu Primovi, kter´ y jej objevil aˇz skoro 30 let po Jarn´ıkovi.
Avˇsak historicky v˚ ubec prvn´ı algoritmus pro probl´em minim´aln´ı kostry (z roku 1928) byl nalezen jin´ym ˇcesk´ym (brnˇensk´ym) matematikem:2 Algoritmus 5.4. Bor˚ uvk˚ uv pro minim´ aln´ı kostru (n´aznak). Toto je ponˇekud sloˇzitˇejˇs´ı algoritmus, chov´a se jako Jarn´ık˚ uv algoritmus spuˇstˇen´y z´aroveˇ n ze vˇsech vrchol˚ u grafu najednou.
Petr Hlinˇen´ y, FI MU Brno
6
FI: MA010: Kostry, Hladov´ y algoritmus
5.2
Hladov´ y algoritmus v obecnosti
Asi nejprimitivnˇejˇs´ım moˇzn´ym pˇr´ıstupem pˇri ˇreˇsen´ı diskr´etn´ıch optimalizaˇcn´ıch ´uloh je postupovat stylem beru vˇ zdy to nejlepˇs´ı, co se zrovna nab´ız´ı. . . 2Tento
postup obecnˇe v ˇceˇstinˇe naz´yv´ame hladov´ym algoritmem, i kdyˇz lepˇs´ı by bylo pouˇz´ıt spr´avnˇejˇs´ı pˇreklad anglick´eho “greedy”, tedy nenasystn´y algoritmus. A jeˇstˇe hezˇc´ı ˇcesk´e spojen´ı by bylo “algoritmus hamouna”. Jednoduˇse bychom jej nast´ınili takto: • Postupnˇe v kroc´ıch vyber vˇzdy to nejlepˇs´ı, co se d´a (nab´ız´ı).
2
• To vyˇzaduje zvolit uspoˇr´ad´an´ı na objektech, ze kter´ych vyb´ır´ame.
2
• Pr˚ ubˇeh a ´uspˇech algoritmu silnˇe z´avis´ı na tomto zvolen´em uspoˇr´ad´an´ı. Jak asi kaˇzd´ y v´ı, nenasystnost ˇci hamounstv´ı neb´ yv´ a v ˇzivotˇe t´ım nejlepˇs´ım postupem, ale kupodivu tento princip perfektnˇe funguje v mnoha kombinatorick´ ych u ´loh´ ach! Jedn´ım zn´ am´ ym pˇr´ıkladem je v´ yˇse uveden´e hled´ an´ı minim´ aln´ı kostry. Jin´ ym pˇr´ıkladem je tˇreba jednoduch´ y probl´em pˇridˇelov´ an´ı (uniformn´ıch) pracovn´ıch u ´kol˚ u, na nˇemˇz si obecn´e sch´ema hladov´eho algoritmu ilustrujeme.
Petr Hlinˇen´ y, FI MU Brno
7
FI: MA010: Kostry, Hladov´ y algoritmus
Probl´ em 5.5. Pˇridˇ elen´ı pracovn´ıch ´ ukol˚ u Uvaˇzujeme zadan´e pracovn´ı ´ ukoly, kter´e maj´ı pˇresnˇe urˇcen´y ˇcas zaˇc´atku i d´elku trv´an´ı. (Jednotliv´e ´ukoly jsou tedy reprezentov´any uzavˇren´ymi intervaly na ˇcasov´e ose.) C´ılem je takov´e pˇridˇelen´ı ´ukol˚ u pracovn´ık˚ um, aby jich celkovˇe bylo potˇreba co nejm´enˇe. Vˇsichni pracovn´ıci jsou si navz´ajem rovnocenn´ı – uniformn´ı, tj. kaˇzd´y zvl´adne vˇsechno. 2 Pro pˇr´ıklad zad´ an´ı takov´e probl´emu si vezmˇeme n´ asleduj´ıc´ı intervaly u ´kol˚ u: 4 s 1 s
s
3 s
s
s
2 s
s 1 s
s2
s s
Kolik je k jejich splnˇen´ı potˇreba nejm´enˇe pracovn´ık˚ u? 2Asi sami snadno zjist´ıte, ˇze 4 pracovn´ıci staˇc´ı, viz zobrazen´e oˇc´ıslov´ an´ı. Ale proˇc jich nem˚ uˇze b´ yt m´enˇe? Pozn´ amka: Uveden´e zad´ an´ı m˚ uˇze b´ yt kombinatoricky pops´ ano tak´e jako probl´em optim´ aln´ıho obarven´ı dan´eho intervalov´eho grafu (vrcholy jsou intervaly u ´kol˚ u a hrany zn´ azorˇ nuj´ı pˇrekr´ yv´ an´ı interval˚ u).
Petr Hlinˇen´ y, FI MU Brno
8
FI: MA010: Kostry, Hladov´ y algoritmus
Algoritmus 5.6. Hladov´ y algoritmus rozdˇ elen´ı pracovn´ıch ´ ukol˚ u. Probl´em 5.5 je vyˇreˇsen n´asleduj´ıc´ı aplikac´ı hladov´eho postupu: ´ 1. Ukoly nejprve seˇrad´ıme podle ˇcas˚ u zaˇc´atk˚ u. 2. Kaˇzd´emu ´ukolu v poˇrad´ı pˇridˇel´ıme voln´eho pracovn´ıka s nejniˇzˇs´ım ˇc´ıslem.
2
D˚ ukaz: Necht’ n´aˇs algoritmus pouˇzije celkem k pracovn´ık˚ u. Dok´aˇzeme jednoduchou ´uvahou, ˇze tento poˇcet je optim´aln´ı – nejlepˇs´ı moˇzn´y. V okamˇziku, kdy zaˇcal pracovat pracovn´ık ˇc´ıslo k, vˇsichni 1, 2, . . . , k − 1 tak´e pracovali (jinak bychom vzali nˇekter´eho z nich). V tom okamˇziku tedy m´ame k pˇrekr´yvaj´ıc´ıch se u ´kol˚ u a kaˇzd´y z nich vyˇzaduje vlastn´ıho pracovn´ıka. 2 2 Pˇr´ıklad neoptim´ aln´ıho pˇridˇelen´ı pracovn´ıch u ´kol˚ u dostaneme napˇr´ıklad tak, ˇze na zaˇc´ atku u ´koly seˇrad´ıme podle jejich ˇcasov´e d´elky. (Tj. ˇc´ım delˇs´ı u ´kol, t´ım dˇr´ıve mu hladovˇe pˇriˇrad´ıme pracovn´ıka.) s s s3 5 s 2 s 3 s
s
2 s
s s
s4
s
1 s
s
Jak vid´ıme na obr´ azku, nalezen´e ˇreˇsen´ı nen´ı optim´ aln´ı – vyˇzaduje 5 m´ısto 4 pracovn´ık˚ u. Je uleˇzit´e, podle jak´eho prinicipu seˇrad´ıme objekty (´ ukoly) na vstupu. tedy velmi d˚ Petr Hlinˇen´ y, FI MU Brno
9
FI: MA010: Kostry, Hladov´ y algoritmus
5.3
Pojem matroidu
Definice 5.7. Matroid na mnoˇzinˇe X, znaˇcen´y M = (X, N ), je takov´y syst´em N podmnoˇzin nosn´e mnoˇziny X, ve kter´em plat´ı n´asleduj´ıc´ı: 1. ∅ ∈ N 2. A ∈ N a B ⊂ A ⇒ B ∈ N 3. A, B ∈ N a |A| < |B| ⇒ ∃y ∈ B \ A : A ∪ {y} ∈ N Mnoˇzin´am ze syst´emu N ˇr´ık´ame nez´avisl´e mnoˇziny. Tˇem ostatn´ım pak ˇr´ık´ame z´avisl´e. Nez´avisl´ym mnoˇzin´am, do kter´ych jiˇz nelze pˇridat ˇz´adn´y prvek tak, ˇze z˚ ustanou nez´avisl´e, ˇr´ık´ame b´aze matroidu. 2 Nejd˚ uleˇzitˇejˇs´ı ˇc´ ast´ı definice matroidu je zv´ yraznˇen´ y tˇret´ı bod. Pˇr´ımo uk´ azkov´ y pˇr´ıklad matroidu n´ am d´ av´ a line´ arn´ı algebra – vˇsechny line´ arnˇe nez´ avisl´e podmnoˇziny vektor˚ u tvoˇr´ı matroid. Odtud tak´e poch´ azej´ı pojmy nez´ avislosti a b´ aze matroidu, kter´e pˇr´ımo odpov´ıdaj´ı pˇr´ısluˇsn´ ym pojm˚ um vektorov´eho prostoru. 2
Lema 5.8. Vˇsechny b´aze matroidu obsahuj´ı stejnˇe mnoho prvk˚ u. D˚ ukaz: Toto pˇr´ımo vypl´yv´a z tˇret´ı vlastnosti definice matroidu: Pokud nez´avisl´a mnoˇzina A m´a m´enˇe prvk˚ u neˇz b´aze B, tak do A lze vˇzdy pˇridat dalˇs´ı prvek x tak, ˇze z˚ ustane A ∪ {x} nez´avisl´a. 2 Petr Hlinˇen´ y, FI MU Brno
10
FI: MA010: Kostry, Hladov´ y algoritmus
Nyn´ı uvedeme nˇekolik poznatk˚ u o stromech, kter´e jsou relevantn´ı pro zaveden´ı “grafov´ych” matroid˚ u. Lema 5.9. Les na n vrcholech s c komponentami souvislosti m´a pˇresnˇe n − c hran.
2
D˚ ukaz: Kaˇzd´y vrchol lesa L n´aleˇz´ı pr´avˇe jedn´e komponentˇe souvislosti z definice. Jak zn´amo, kaˇzd´y strom, tj. komponenta lesa L, m´a o jednu hranu m´enˇe neˇz vrchol˚ u. Ve sjednocen´ı c komponent tak bude pr´avˇe o c m´enˇe hran neˇz vrchol˚ u. 2 ˇ Definice: Rekneme, ˇze podmnoˇzina hran F ⊂ E(G) je acyklick´a, pokud podgraf s vrcholy V (G) a hranami z F nem´a kruˇznici. Lema 5.10. Necht’ F1 , F2 jsou acyklick´e podmnoˇziny hran grafu G a |F1 | < |F2 |. Pak existuje hrana f ∈ F2 \ F1 takov´a, ˇze F1 ∪ {f } je tak´e acyklick´a podmnoˇzina. 2 D˚ ukaz: Jelikoˇz |F1 | < |F2 | a plat´ı Lema 5.9, m´a podgraf G1 tvoˇren´y hranami z F1 v´ıce komponent neˇz podgraf G2 tvoˇren´y hranami z F2 . Potom vˇsak nˇekter´a hrana f ∈ F2 mus´ı spojovat dvˇe r˚ uzn´e komponenty podgrafu G1 , a tud´ıˇz pˇrid´an´ım f do F1 nevznikne kruˇznice. 2
Petr Hlinˇen´ y, FI MU Brno
11
FI: MA010: Kostry, Hladov´ y algoritmus
Definice: Podle Lematu 5.10 tvoˇr´ı syst´em vˇsech acyklick´ych podmnoˇzin hran v (libovoln´em) grafu G matroid. Tento matroid naz´yv´ame matroidem kruˇznic grafu G. V analogi´ı s grafy pouˇz´ıv´ame n´azev kruˇznice pro minim´aln´ı z´avisl´e mnoˇziny matroidu. 2
Dva pˇr´ıklady matroidu jsou hezky ilustrov´ any v n´ asleduj´ıc´ım obr´ azku, kter´ y ukazuje, jak hrany ˇ ary (zvan´e “pˇr´ımky”) v grafu K4 vlevo odpov´ıdaj´ı vektor˚ um v matroidu kruˇznic vpravo. C´ prav´em sch´ematu vyznaˇcuj´ı line´ arn´ı z´ avislosti mezi vektory; tj. nez´ avisl´e jsou ty trojice bod˚ u, kter´e neleˇz´ı na ˇz´ adn´e spoleˇcn´e “pˇr´ımce”. » – 0 0 1
f
K4 a
d
» – 1 0 1
b
d
→
f
e
e
» – 0 1 0
» – 1 0 0
c
a
Petr Hlinˇen´ y, FI MU Brno
» – 1 1 1
12
c
» – 1 1 0
b
FI: MA010: Kostry, Hladov´ y algoritmus
Abstraktn´ı hladov´ y algoritmus V praxi se matroid obvykle nezad´av´a v´yˇctem vˇsech nez´avisl´ych mnoˇzin, protoˇze tˇech je pˇr´ıliˇs mnoho (aˇz 2n pro n-prvkovou mnoˇzinu X). M´ısto toho b´yv´a d´ana extern´ı funkce pro testov´an´ı nez´avislosti dan´e podmnoˇziny. 2 Algoritmus 5.11. Nalezen´ı minim. b´ aze matroidu – hladov´ y algoritmus. vstup: mnoˇzina X s v´ahovou funkc´ı w : X → R, matroid na X urˇcen´y extern´ı funkc´ı nezavisla(Y); 2 setˇ r´ ıdit X=(x[1],x[2],...,x[n]) tak, aby w[x[1]]<=...<=w[x[n]]; B = ∅; for (i=1; i<=n; i++) if (nezavisla(B∪{x[i]})) B = B ∪ {x[i]}; v´ ystup: b´aze B dan´eho matroidu s min. souˇctem ohodnocen´ı vzhledem k w.
2
Pozn´ amka: Pokud X v tomto algoritmu je mnoˇzina hran grafu, w v´ ahov´ a funkce na hran´ ach a nez´ avislost znamen´ a acyklick´e podmnoˇziny hran (matroid kruˇznic grafu), pak Algoritmus 5.2 je pˇresnˇe instanc´ı Algoritmu 5.11.
Petr Hlinˇen´ y, FI MU Brno
13
FI: MA010: Kostry, Hladov´ y algoritmus
Vˇ eta 5.12. Algoritmus 5.11 (hladov´y algoritmus) pro danou nosnou mnoˇzinu X s v´ahovou funkc´ı w : X → R a pro dan´y matroid N na X spr´avnˇe najde b´azi v N s nejmenˇs´ım souˇctem vah. 2 D˚ ukaz: Z definice matroidu je jasn´e, ˇze k v´ysledn´e mnoˇzinˇe B jiˇz nelze pˇridat dalˇs´ı prvek, aby z˚ ustala nez´avisl´a, proto je B b´aze. Seˇrad’me si prvky X podle vah jako v algoritmu w(x[1]) ≤ · · · ≤ w(x[n]). Necht’ indexy i1 , i2 , . . . , ik urˇcuj´ı vybranou kprvkovou b´azi B v algoritmu a necht’ indexy j1 , j2 , . . . , jk vyznaˇcuj´ı (tˇreba jinou?) b´azi {x[j1 ], . . . , x[jk ]} s nejmenˇs´ım moˇzn´ym souˇctem vah. 2 Vezmˇeme nejmenˇs´ı r ≥ 1 takov´e, ˇze w(x[ir ]) 6= w(x[jr ]). Potom nutnˇe w(x[ir ]) < w(x[jr ]), protoˇze n´aˇs algoritmus je “hladov´y” a bral by menˇs´ı w(x[jr ]) jiˇz dˇr´ıve. Na druhou stranu, pokud by druh´a b´aze {x[j1 ], . . . , x[jk ]} d´avala menˇs´ı souˇcet vah, muselo by existovat jin´e s ≥ 1 takov´e, ˇze w(x[is ]) > w(x[js ]). Nyn´ı vezmˇeme nez´avisl´e podmnoˇziny A1 = {x[i1 ], . . . , x[is−1 ]} a A2 = {x[j1 ], . . . , x[js ]}, kde A2 m´a o jeden prvek v´ıce neˇz A1 a vˇsechny prvky A2 maj´ı dle pˇredpokladu menˇs´ı v´ahu neˇz w(x[is ]). 2
Podle definice matroidu existuje y ∈ A2 \ A1 takov´e, ˇze A1 ∪ {y} je nez´avisl´a. Pˇritom samozˇrejmˇe y = x[ℓ] pro nˇejak´e ℓ. Ale to nen´ı moˇzn´e, protoˇze, jak je v´yˇse naps´ano, w(y) < w(x[is ]), takˇze by n´aˇs hladov´y algoritmus musel y = x[ℓ], ℓ < is vz´ıt dˇr´ıve do vytv´aˇren´e b´aze B neˇz vzal x[is ]. Proto jin´a b´aze s menˇs´ım souˇctem vah neˇz nalezen´a B neexistuje. 2 Petr Hlinˇen´ y, FI MU Brno
14
FI: MA010: Kostry, Hladov´ y algoritmus
5.4
Kdy hladov´ y algoritmus (ne)pracuje spr´ avnˇ e
Jak uk´aˇzeme, funkˇcnost hladov´eho algoritmu je pˇr´ımo sv´az´ana s matroidy. Vˇ eta 5.13. Necht’ X je nosn´a mnoˇzina se syst´emem “nez´avisl´ych” podmnoˇzin N splˇnuj´ıc´ı podm´ınky (1,2) Definice 5.7. Pokud pro jakoukoliv v´ahovou funkci w : X → R najde Algoritmus 5.11 optim´aln´ı nez´avislou mnoˇzinu z N , tak N splˇnuje tak´e podm´ınku (3), a tud´ıˇz tvoˇr´ı matroid na X. 2 D˚ ukaz: Tvrzen´ı dokazujeme sporem. Pˇredpokl´adejme, ˇze vlastnost (3) neplat´ı pro dvojici nez´avisl´ych mnoˇzin A, B, tj. ˇze |A| < |B|, ale pro ˇz´adn´y prvek y ∈ B \ A nen´ı A ∪ {y} nez´avisl´a. Necht’ |A| = a, |B| = b, kde 2b > 2a + 1. Zvol´ıme n´asleduj´ıc´ı ohodnocen´ı • w(x) = −2b pro x ∈ A, • w(x) = −2a − 1 pro x ∈ B \ A, • w(x) = 0 jinak.2 Hladov´y algoritmus pˇrirozenˇe najde b´azi B1 obsahuj´ıc´ı A a disjunktn´ı s B \ A podle naˇseho pˇredpokladu. Jej´ı ohodnocen´ı je w(B1 ) = −2ab. Avˇsak optim´aln´ı b´az´ı je v tomto pˇr´ıpadˇe jin´a B2 obsahuj´ıc´ı cel´e B a maj´ıc´ı ohodnocen´ı nejv´yˇse w(B2 ) ≤ (−2a − 1)b = −2ab − b < w(B1 ). To je ve sporu s dalˇs´ım pˇredpokladem, ˇze i pˇri n´ami zvolen´em ohodnocen´ı w nalezne hladov´y algoritmus optim´aln´ı b´azi. Proto je sporn´y n´aˇs pˇredpoklad o mnoˇzin´ach A, B a podm´ınka (3) je splnˇena. 2 Petr Hlinˇen´ y, FI MU Brno
15
FI: MA010: Kostry, Hladov´ y algoritmus
Pˇr´ıklad 5.14. Nakonec uv´ad´ıme dvˇe uk´azky, ve kter´ych hladov´y algoritmus selˇze: um Obarven´ı grafu. 2Probl´em obarven´ı grafu ˇz´ad´a pˇriˇrazen´ı co nejm´enˇe barev vrchol˚ tak, aby sousedn´ı dvojice dostaly r˚ uzn´e barvy. Obecnˇe hladovˇe barv´ıme graf tak, ˇze ve zvolen´em poˇrad´ı vrchol˚ u kaˇzd´emu n´asleduj´ıc´ımu pˇridˇel´ıme prvn´ı volnou barvu. 2 s f s s f s 1 2 3 1 Tˇreba v nakreslen´e cestˇe d´elky 3 m˚ uˇzeme barvit hladovˇe v poˇrad´ı od vyznaˇcen´ych krajn´ıch vrchol˚ u, a pak mus´ıme pouˇz´ıt 3 barvy m´ısto optim´aln´ıch dvou. Vrcholov´ e pokryt´ı. 2Probl´em vrcholov´eho pokryt´ı se pt´a na co nejmenˇs´ı podmnoˇzinu C vrchol˚ u dan´eho grafu takovou, ˇze kaˇzd´a hrana m´a alespoˇn jeden konec v C. Pˇrirozen´ym hladov´ym postupem by bylo vyb´ırat od vrchol˚ u nejvyˇsˇs´ıch stupˇn˚ u ty, kter´e soused´ı s doposud nepokryt´ymi hranami. Bohuˇzel tento postup tak´e obecnˇe nefunguje. s f s s s f s sf sf s s f s s s s s f f s sf sf s 2
Petr Hlinˇen´ y, FI MU Brno
16
FI: MA010: Kostry, Hladov´ y algoritmus
