Algoritmusok és optimalizálás

A Kruskal-algoritmus egy mohó stratégia. A gráf összes élét súlyuk szerint növekvő sorrendbe állítja, majd sorban megvizsgálja őket. Minden lépésben hozzáadja az adott élt a feszítőfához, feltéve, hogy az nem hoz létre kört a már kiválasztott élekkel. Ezt az eljárást addig folytatja, amíg a kiválasztott élek száma pontosan $n-1$ nem lesz, ahol $n$ a csúcsok száma.

Dijkstra algoritmusa nem alkalmazható megbízhatóan olyan gráfokban, amelyek negatív súlyú éleket tartalmaznak. A mohó természetéből fakadóan az algoritmus feltételezi, hogy egy már rögzített (véglegesített távolságú) csúcshoz nem vezethet rövidebb út a későbbiekben. Negatív élek jelenléte esetén ez a feltételezés megdőlhet.

Legyen a kifizetendő összeg 6 egység. A mohó algoritmus először választ egy 4-es érmét, ekkor marad 2 egység, amit két darab 1-es érmével tud kifizetni. Így a felhasznált érmék száma 3 darab ($4+1+1$). A valódi optimális megoldás azonban két darab 3-as érme felhasználása ($3+3=6$), ami mindössze 2 érmét jelent.

Egy $n$ csúcsú összefüggő gráf minden feszítőfája (súlyoktól függetlenül) pontosan $n-1$ élt tartalmaz. Ha ennél kevesebb lenne, a gráf nem lenne összefüggő, ha pedig több, akkor a gráf biztosan tartalmazna kört, így nem lenne fa.

Kruskal algoritmusa az élek halmazából indul ki, és egy "erdőt" épít, amelynek komponensei a folyamat végén egyetlen fává olvadnak össze. Prim algoritmusa ezzel szemben egyetlen, egyre növekvő fát épít fel úgy, hogy egy kezdőcsúcsból kiindulva mindig azt a legkisebb súlyú élt adja hozzá, amely a már megépített fát egy még nem vizsgált csúccsal köti össze.

Ha egy összefüggő gráfban minden él súlya különböző, akkor a gráfnak pontosan egy (egyértelmű) minimális súlyú feszítőfája van. Ezt könnyen beláthatjuk a vágási tulajdonság (cut property) alkalmazásával, mivel minden lehetséges vágásnál egyértelműen meghatározható egy szigorúan legkisebb súlyú él.

Az úgynevezett kör-tulajdonság (cycle property) kimondja, hogy egy kör egyértelműen maximális súlyú éle biztosan nem szerepelhet egyetlen minimális súlyú feszítőfában sem. Ha szerepelne, akkor azt elhagyva a kör egy másik élével helyettesíthetnénk, ezáltal csökkentve a fa összsúlyát.

A helyes és optimális mohó stratégia az, hogy a tevékenységeket a befejezési idejük szerint növekvő sorrendbe rendezzük. Mindig a legkorábban befejeződő, a már kiválasztottakkal nem ütköző tevékenységet választjuk. Ez biztosítja, hogy a lehető legtöbb szabad idő maradjon a további tevékenységek számára.

A módosítás rendkívül egyszerű. Az éleket nem növekvő, hanem csökkenő sorrendbe kell rendezni a súlyuk alapján. Ezt követően az algoritmus logikája változatlan marad: mindig a legnagyobb elérhető súlyú élt adjuk a fához, amennyiben az nem zár be kört.

Egy csúcs távolsága akkor válik véglegessé, amikor a még nem véglegesített csúcsok közül a legkisebb aktuális távolságértékkel rendelkezik, és emiatt az algoritmus kiválasztja feldolgozásra. Mivel az élsúlyok nem negatívak, egyetlen más, hosszabb részúton keresztül sem lehet a későbbiekben rövidebb utat találni ehhez a csúcshoz.

A Bellman-Ford algoritmus képes kezelni a negatív súlyú éleket is (amíg nem alkotnak negatív összsúlyú kört). Továbbá az eljárás képes detektálni, ha a gráfban negatív súlyú kör található, míg Dijkstra algoritmusa ilyen esetekben téves eredményt adna.

Ebben az extrém esetben a gráf bármelyik feszítőfája egyben minimális súlyú feszítőfa is. Mivel minden feszítőfa pontosan $n-1$ élt tartalmaz, és minden él azonos súlyú, az összes lehetséges feszítőfa összsúlya egyenlő lesz.

Nem alkalmazható. A legközelebbi szomszéd elve (Nearest Neighbor) egy tipikus mohó heurisztika, amely gyors, de az utazó ügynök problémája esetén nagyon ritkán adja meg a globális optimumot. A mohó lépések az út végére gyakran kényszerítik az ügynököt egy extrém hosszú él használatára a visszatéréshez.

A töredékes hátizsák-probléma esetén a tárgyakat az "egységnyi súlyra eső értékük" (fajlagos érték) szerint kell csökkenő sorrendbe rendezni. A mohó algoritmus sorban beleteszi a legértékesebb tárgyakat a hátizsákba teljes egészében, amíg férnek. Amikor egy tárgy már nem fér be teljesen, a maradék kapacitást feltölti a tárgy megfelelő törtrészével.

Ha a gráf csúcsait két diszjunkt halmazra bontjuk (ez egy vágás), akkor a két halmazt összekötő élek közül a legkisebb súlyú él biztosan része lesz a minimális súlyú feszítőfának. Ez a tulajdonság adja a Prim-algoritmus helyességének matematikai alapját.

Nem, ez nem lehetséges. Bár egy gráfnak lehet több minimális súlyú feszítőfája (ha vannak azonos súlyú élek), matematikailag bizonyítható, hogy minden minimális súlyú feszítőfa pontosan ugyanazokat az élsúlyokat tartalmazza, pontosan ugyanannyiszor.

A probléma megoldható Dijkstra algoritmusának módosításával. A távolságok összeadása helyett a részúton lévő minimális élsúlyt (a szűk keresztmetszetet) tartjuk nyilván, a csúcsok frissítési szabálya pedig az útvonalak sávszélességének maximalizálására változik: $S(v) = \max(S(v), \min(S(u), \text{súly}(u,v)))$. Másik lehetséges megoldás a maximális súlyú feszítőfa megkeresése Kruskal algoritmussal, a fában futó egyetlen út a két pont között a keresett optimális út lesz.

Ha az élsúlyokat negáljuk a leghosszabb út megkereséséhez, a gráfban könnyen kialakulhatnak negatív összsúlyú körök (ha eredetileg volt pozitív súlyú kör). Dijkstra algoritmusa eleve képtelen kezelni a negatív éleket, a negatív körök pedig végtelenül hosszú látszólagos utakat eredményeznek. A leghosszabb út problémája általános gráfokon NP-teljes feladat.

Igen, a jelenlegi magyar forint érmerendszere kanonikus. Ennek az az oka, hogy a címletek jól skálázódnak (jellemzően 2-szeres, illetve 2,5-szeres ugrásokkal követik egymást), így sosem áll elő olyan szituáció, ahol egy nagyobb érme kihagyásával és kisebbek halmozásával kevesebb darabszámból lehetne kifizetni a kért összeget.

Ebben az esetben Dijkstra algoritmusa egy úgynevezett 0-1 BFS (Szélességi Keresés) algoritmussá egyszerűsíthető le. A prioritási sor (priority queue) helyettesíthető egy egyszerű kétvégű sorral (deque). Ha egy csúcsot egy 0 súlyú élen érünk el, az a sor elejére kerül, ha 1 súlyú élen, akkor a sor végére. Ezzel az időbonyolultság $O(V + E)$-re csökken.