Szakkörök‎ > ‎Algoritmus szakkör‎ > ‎2011-2012‎ > ‎

9. óra

2011.11.21.

Belekezdünk a mohó algoritmusok vizsgálatába. Átvezetésként egy gráfokon futó mohó algoritmust nézünk meg.

Feladat

"Unió-holvan" adatszerkezet


Az "unió-holvan" adatszerkezet a következő probléma megoldására született: adott véges sok halmaz, amelyeken a következő lépéseket kell - előre nem ismert sorrendben, sokszor egymás után - elvégezni:
  • megkérdezhetjük két elemről, hogy azonos halmazban vannak-e;
  • egyesíthetünk két halmazt
Vázlatosan a következőt csináljuk: a halmazokat (felfelé) irányított fákkal reprezentáljuk. Minden elemnek lesz egy "apa-pointere", a fa gyökerének önmaga. Egy elem halmazát a fája gyökerével azonosítjuk. Az apa-pointerek követésével ez gyorsan meghatározható. Két halmaz egyesítésekor az egyik gyökerének apa-pointerét a másik gyökerére állítjuk.

A műveletek optimalizálhatók, erről a fenti cikkben olvashatunk.

Kruskal algoritmusa


Adott irányítatlan és összefüggő gráf minimális összsúlyú feszítőfáját keressük. Kruskal algoritmusának vázlata:

DB := 0; FA := {}
Ciklus az élek élsúly szerint növekvően rendezett listáján amíg DB < N - 1 
    EL := a soron következő él
    Ha FA+{EL} nem tartalmaz kört akkor
        FA := FA+{EL}
        DB := DB + 1
    Elágazás vége
Ciklus vége

A körmentességet az "unió-holvan" adatszerkezettel ellenőrizhetjük, új él felvételekor az él végpontjainak halmazait egyesítjük.

Az algoritmus helyessége

Két dolgot bizonyítunk:
  1. az algoritmus feszítőfát hoz létre
  2. a kapott feszítőfa minimális összsúlyú

1. feszítőfát kapunk

A felvett élek körmentes gráfot alkotnak, mert teszteltük, hogy a felvett él nem hoz létre kört. A kapott gráf N - 1 élű, és körmentes tehát fa, és minden csúcsot tartalmaz. 

2. minimalitás

A következő invariánst bizonyíthatjuk: ha az algoritmusunk egy bizonyos pillanatig az F élhalmazt választotta, akkor van olyan minimális feszítőfa, aminek F részgráfja. 

Nyilván kezdetben igaz az állítás, hiszen F üres halmaz (és mindig létezik minimális feszítőfa).
 
Tegyük fel, hogy F még nem végleges, és T egy őt tartalmazó minimális feszítőfa. Legyen a következő lépésben felvett él e

Ha e benne van T-ben, akkor továbbra is teljesül az invariáns.
Ha e nincs T-ben, akkor T+{e} kört tartalmaz, és ebben a körben kell lennie egy f élnek, ami nincs F-ben, különben az algoritmus nem választhatta volna e-t, mert kör keletkezett volna. 
A rendezés miatt f nem lehet könnyebb, mint e, mert akkor őt választottuk volna. Nehezebb sem lehet, mert T - {f} + {e} feszítőfa, és T minimális. 

Tehát T - {f} + {e} minimális feszítőfa, és részhalmazként tartalmazza F+{e}-t. Innentől indukcióval következik az eredeti állítás.