Bevezetés

A gyakorlati alkalmazásokban az egyik legfontosabb, legtöbbször használt hálózati algoritmus a legkedvezőbb útvonalak keresése. A "legkedvezőbb útvonal" fogalmat természetesen pontosítani kell ahhoz, hogy algoritmusokat adhassunk a meghatározására. E célból vezessünk be néhány eddig még pontosan nem definiált új fogalmat.

A természetes szemlélettel megegyezően út a gráf egy olyan pont illetve élsorozata, amelynek a felsorolás (bejárás) sorrendjében szomszédos pontjai közt van a megelőző pontból a következő pontba mutató él (pl. az 1. ábrán a vastag vonal, az a-e-f-d-c-b-g út). A körös út olyan út, amelyben van legalább egy olyan pont, amely ismétlődik (2. ábra, vastag vonal). Körmentes út az, amelyben ilyen pont nincs. Az út első pontját kiinduló, utolsó pontját pedig cél pontnak nevezzük. Egy kiinduló pont - célpont párt egy viszonylatnak nevezünk. Egy gráfban általában több út is van egy adott viszonylatban (minél nagyobb a gráf, általában annál több a lehetséges utak száma). Összefüggő gráf az olyan gráf, amelyben bármely két pont között van legalább egy út.

 

1. ábra

2. ábra

Ha már hálózatról beszélünk, vagyis az éleknek van mérő, súlyozó száma, akkor az utakat is minősíthetjük, mérhetjük. Az él mérőszámát az egyszerűség kedvéért általában élhossznak szoktuk nevezni, így az utat élei hosszának összegével mérjük, és ezt úthossznak nevezzük. (Az alkalmazásokban ez a "hossz" természetesen sok minden lehet, pl. idő, költség, munkaigény stb.). Így már beszélhetünk két út hossz szerinti összehasonlításáról, rövidebb, hosszabb utakról. Közlekedési analógiával élve, itt számunkra a "kedvezőbb" a kisebb hosszúságút, a rövidebbet jelenti, a legkedvezőbb a minimális hosszúságút. (Megjegyezzük, hogy ilyen, minimális hosszú útból egy adott viszonylatban több is lehet.)

Bár elvben egy élhez rendelt szám negatív vagy nulla is lehet, de ettől az esettől itt tekintsünk el, legyenek az éleink, így az utjaink is mind pozitív hosszúak. Ebből rögtön következik az, hogy amikor minimális hosszúságú utat keresünk, akkor biztosan körmentes utat kapunk, hiszen egy kör levágása csökkenti a hosszt.

A minimális hosszúságú út (rövidebben kifejezve a minimális út ) keresése több szempontból is érdekes problémakör. Jól demonstrálja például azt, hogy a keresési, optimalizálási problémák "naív" megközelítése sokszor nem vezet célhoz, sőt gyakorlati méretekben egyszerűen használhatatlan. Itt egy ilyen jellegű módszer lenne az, hogy : "egy adott viszonylatban vizsgáljuk meg az összes körmentes utat, számítsuk ki mindegyiknek a hosszát és így megkapjuk a keresett minimális hosszút". Ez esetleg menne igen kis hálózatokra, de gondoljuk meg, hogy már egy 15 pontos hálózatnál is több milliárd esetet kellene vizsgálni. (A kezdő és végpontot rögzítve, a többi pontok az összes lehetséges részhalmazát és az egyes részhalmazbeli pontok összes sorrendjét kellene képezni, mindegyikről eldönteni, hogy út -e vagy sem, és ha út, akkor mennyi a hossza.) Nagyobb hálózatoknál ez még az elképzelhető leggyorsabb számítógépekkel is lehetetlen lenne.

A feladat egy másik jellegzetessége, hogy jól mutatja a választott számítástechnikai adattárolási mód, tehát az adatstruktúra és a feladatmegoldó algoritmus erős összefüggését, ami más problémáknál is fennáll, de itt viszonylag egyszerűen szemléltethető. Mint majd látni fogjuk egészen más jellegű algoritmus vezet célhoz a hálózat mátrixos tárolása esetén mint pl. az éltárolási módszernél. Az a számítási, keresési mód, ami az egyiknél nagyon hatékony, a másiknál gyakorlatilag kivitelezhetetlen.

A minimális út keresése és a hasonló jellegű hálózati algoritmusok kutatása a matematika és számítástechnika egy viszonylag fiatal közös területének, az operációkutatásnak a produktuma, csak néhány évtizedes múltat mondhatnak magáénak. (A kezdet a negyvenes évek vége - ötvenes évek eleje időszakra esik.) Ennek fő oka az, hogy ezek az algoritmusok feltételezik a mai értelemben vett számítógépeket, a modern számítástechnikát, végrehajtásuk gyakorlati méretekben csak számítógéppel lehetséges.

Ezek előrebocsátása után nézzünk két, a témakörben klasszikusnak számító és jól ismert konkrét eljárást. Az eljárások helyessége (az, hogy a kapott utak ténylegesen a minimális utak) egzaktan bizonyítható, de ezzel itt nem foglalkozunk.

Mátrix algoritmus

Az alább ismertetendő eljárást a szakirodalom - első publikálójáról - Warshall féle eljárásnak nevezi. Akkor alkalmazzuk, ha minden viszonylatban (vagy legalábbis a viszonylatok nagy részében) meg akarjuk határozni a minimális utat, és van elegendő operatív tárterületünk az algoritmus által igényelt két darab pontszám*pontszám méretű mátrix tárolására.

Az algoritmus könnyebb leírásához vezessünk be egy újabb fogalmat : Az, hogy egy x-y viszonylat minimális útját egy w pont bevonásával keressük, azt jelenti, hogy az utat egy x-w kezdő és egy w-y befejező részútból próbáljuk összerakni (vagyis az x - ből az y -ba a w - n keresztül megyünk).

Az algoritmus egy T távolságmátrixot és egy C címkemátrixot használ. Mindkettő pontszám*pontszám méretű és soronként és oszloponként is a pontokkal (vagy a pontsorszámokkal) van indexelve (úgy mint a hálózat mátrixos tárolásánál). A sorindex egy viszonylat kezdőpontjának, az oszlopindex egy viszonylat végpontjának felel meg.

A T elemei a viszonylatok aktuális távolságát vagyis az aktuális minimális útjának hosszát tartalmazzák, tehát a T[x,y] az x-y viszonylat ilyen távolsága. A C elemei pontok (vagy pontindexek) és a minimális út összerakásához, tehát a megfelelő pontsorozat előállításához szükséges adatokat tartalmazzák abban a formában, hogy a C[x,y] az a pont, amely az x-y viszonylat aktuális minimális útján az x kezdőpont után jön (merre induljunk a kezdőpontból a végpont felé).

Az algoritmus a T és a C egy kezdőállapotából kiindulva, a mátrixokat lépésenként javítva, több lépés megtétele után jut el a végeredményhez. Mint látni fogjuk, pontosan annyi lépés kell, ahány pont van a hálózatban. Ezek után az algoritmust a következőképpen definiálhatjuk:

  • Kezdőállapot

T : ha a kezdő és végpont között van közvetlen összeköttetés (él), akkor ennek hossza a távolság, egyébként a távolság végtelen nagy. (Mint látható, ez tulajdonképpen a hálózat mátrixos tárolásának megfelelő mátrix.)

C : a viszonylat címke eleme a végpont. Minden oszlop az oszlopindexet tartalmazza, annak megfelelően, hogy a T kezdőállapota tulajdonképpen egy élből álló utakat jelent

  • Javító lépések

A hálózat minden w pontjára (egyszer) és ezen belül minden x-y viszonylatra (egyszer) végrehajtandó: kíséreljük meg a w -t bevonni a viszonylatba, vagyis ha T[x,y]>T[x,w]+T[w,y] (vagyis a w bevonásával rövidítünk), akkor legyen az új távolság T[x,y]=T[x,w]+T[w,y] és az új címke C[x,y]=C[x,w] (vagyis az y -hoz vezető minimális úton ugyanúgy kell indulni, mint a w -hez vezető minimális úton).

  • Végállapot

A T végállapota megadja a tényleges minimális út hosszát egy - egy viszonylathoz. Ez az érték már nem csökkenthető, tehát ennél rövidebb út nem található. (Ez persze azt nem zárja ki, hogy esetleg több út is legyen ezzel a minimális hosszal.) Ha van olyan pont a hálózatban, amelyből vagy amelybe egyáltalán nincs út, tehát a pont valamelyik, vagy mindkét értelemben elszigetelt (izolált), akkor a megfelelő mátrixelemek végtelen értékűek maradnak. Ha magukra az útvonalakra is szükségünk van, ezeket viszonylatonként kiolvashatjuk a C - ből, ennek definíciója alapján.

3. ábra

Az algoritmushoz a 3.ábra hálózatán adunk példaadatokat. Az ábrán az irányítás nélküli szakaszok kétirányú, és mindkét irányban azonos hosszú éleket jelölnek. A 4. ábra a kezdőállapotot, az 5. ábra az első javítás (w=a), a 6. ábra a második javítás (w=b) utáni állapot, a 7. ábra a végállapot. Például határozzuk meg a példahálózatban az f-g viszonylatra az utat, a 7. ábra segítségével C[f,g]=d, C[d,g]=c, C[c,g]=b, C[b,g]=g, tehát az út: f-d-c-b-g.

4. ábra

5. ábra

6. ábra

7. ábra

A javító lépések algoritmusa tehát három egymásba ágyazott ciklus, a külső a bevonandó pont szerinti, ezen belül van a viszonylat kezdőpontja szerinti, és a legbelső a viszonylat végpontja szerinti ciklus. Az elvi algoritmus sorrendet nem ír elő, de a programban - mint legegyszerűbbet - a növekvő sorrendet alkalmazzuk mind a három ciklusban.

A programokban a végtelen helyébe egy megfelelően nagy számot veszünk (pl. az összes élhossz összegénél nagyobb szám már megfelelő) és ezt "végtelenként" kezeljük, tehát bármit is hozzáadva értéke nem változhat.

Mint az eddigiekből láthatjuk, az algoritmus egyszerű és számításigénye a pontszám köbével jellemezhető (ld. a három ciklus).

Az viszont megint csak látható, hogy a tárigény eléggé nagy, a két mátrixot tárolnunk kell az operatív tárban. Ha a T egy elemére 4 bájtot, a C egy elemére 2 bájtot számítunk, akkor pl. egy 8 MB operatív tárral rendelkező PC -n kb. 1000 pontig, míg 16 MB operatív tárral kb. 1500 pontig mehetünk el. Az algoritmus nagyon kihasználja, hogy a T és C mátrixok (elemeik két index segítségével közvetlenül, egy lépésben elérhetők) így ezeket ténylegesen operatív tárbeli mátrixként kell tárolni, mert egyéb megoldásoknál (pl. lemezen tárolás) az eljárás egyszerűségét és hatékonyságát veszti.

Fa - építő algoritmusok

Elöljáróban részben megismételve, de bővítve is, idézzünk fel egy már korábban (a bevezető cikkben) előfordult fogalmat: Irányított fa egy olyan gráf, amelynek minden éle egyirányú és van egy olyan pont - amelyet gyökérpontnak nevezünk - amelyből minden más pontba egy és csakis egy út vezet (bevezető cikk 5. ábra). Ezekből következik, hogy minden pontba - kivéve a gyökérpontot - egy és csakis egy él mutat, ennek kezdőpontját a pont elődjének nevezzük a fában. Az is következik, hogy az ebben nem képezhető körös út.

Ha a hálózatunk a számítástechnikai kapacitásunkhoz képest nagy, vagy csak a viszonylatok kisebb részében akarunk minimális utat keresni, akkor alkalmazhatjuk az un. fa - építő eljárásokat. Ezek nem az összes viszonylatra, hanem csak az azonos kezdőpontú viszonylatokra - tehát egy kezdőpontból az összes többi pontba mint végpontba - határozzák meg a minimális utakat. Az ilyen utak egy irányított fa struktúrájú részgráfot alkotnak a hálózatban a kezdőponttal mint gyökérponttal, ezt a fát konstruálja meg, építi fel több lépésben az eljárás, innen származik a módszer elnevezése. Az ilyen fát röviden minimális fának fogjuk nevezni.

Számítástechnikai szempontból az irányított fa nagy előnye, hogy kis memóriaigénnyel, könnyen megadható, tárolható egy darab egydimenziós tömbbel, amely pontokat tartalmaz és pontokkal (vagy pontindexekkel) van indexelve. A tömbelem az index elődjét adja meg a fában, ezt címkének, magát a tömböt címketömbnek nevezzük. (A kezdőpontnak elvben nincs címkéje, csupán technikai okokból önmagát írjuk be.) Ha a címketömb mellé még felveszünk egy ugyanúgy indexelt távolságtömböt is, amely az indexhez megadja a gyökérponttól a pontba (természetesen a fán belül) vezető út hosszát, akkor a két tömbbel megadtuk a teljes információt a minimális fához.

8. ábra

A fa - építés módszerét a 8. ábra hálózatával fogjuk szemléltetni. Ez a hálózat csupa kétirányú, és a két irányban azonos hosszú éleket tartalmaz. A 9a. ábra az a gyökérpontú minimális fát mutatja be a hálózatban, a 9b. ábrán láthatjuk a megfelelő címke és távolságtömböt, amelyeket itt is C és T jelöl.

9a. ábra

9b. ábra

Többféle fa-építő alapeljárás - alapmódszer ismert. Mi itt egy olyat mutatunk be, amelynek a működése könnyen követhető és a módszeren alapuló konkrét algoritmusok a gyakorlatban is jól alkalmazhatók. Az alapeljárást a szakirodalom első leírójáról Dijkstra - féle eljárásnak nevezi. Mi itt halmazok, pontosabban a hálózat pontjaiból képzett különböző részhalmazok segítségével írjuk le.

Vezessünk be három jelölést:

  • a K a kész pontok halmaza, elemei már végleges (nem rövidíthető) távolsággal és végleges (nem áthelyezhető) címkével rendelkeznek
  • az A az aktív pontok halmaza, elemei már rendelkeznek távolsággal és címkével de ezek még változhatnak.
  • az x kezdő és y végpontú él hossza H(x,y)

(Természetesen a fa-építés folyamán van még egy harmadik halmaz is, azon pontokból, amelyeknek még egyáltalán nincs címkéje, de ezt nem kell külön jegyezni. )

Az algoritmus a T és a C egy kezdőállapotából kiindulva, a tömböket - tehát a fát - lépésenként építve és korrigálva, több lépés megtétele után jut el a végeredményhez. Mint látni fogjuk, pontosan eggyel kevesebb lépés kell, mint ahány pont van a hálózatban. Ezek után az algoritmust a következőképpen definiálhatjuk:

  • Kezdőállapot

Legyen az a a kezdőpont. Rendeljük a kezdőponthoz a 0, a többihez a végtelen távolságértéket, a K legyen üres, az A tartalmazza csak a kezdőpontot, tehát C[a]=a,T[a]=0,K=[],A=[a].Ez tehát az a fa, amely egy pontból, a gyökérpontból áll.

  • Javító lépések

  1. Válasszuk ki az A minimális távolságú elemét, jelölje ezt x, ezt töröljük az A- ból és vegyük hozzá a K-hoz (ez már kész, nem változik), tehát K=K+[x],A=A-[x].

  2. Az x -ből kiinduló minden él végpontjára végrehajtandó: Jelölje a végpontot y. Megvizsgáljuk, hogy y útja x -en keresztül rövidíthető-e. Ha igen, a pont címkéjét x -re, távolságát a rövidebbre állítjuk, és (ha még nem volt benn) hozzávesszük az A halmazhoz. Tehát ha y még nem volt a fában, akkor x előddel bekerül, ha már bent volt, akkor elődjét lecseréljük x -re. Képletekben: ha T[y]>T[x]+H[x,y] akkor T[y]=T[x]+H[x,y] és C[y]=x, A=A+[y].

  3. Ha van még aktív elem, vagyis ha az A nem üres, akkor folytatjuk a b) ponttól.

  • Végállapot

Ha már nincs aktív pont, akkor az eljárás véget ért, a minimális fa készen van, a C és T meghatározzák. Az egyes végpontokhoz tartozó utak a C -ből (a végpontból visszafelé haladva) egyszerűen összerakhatók.

Az algoritmus első négy lépését a példahálózaton bemutatjuk. A 10b.ábra táblázatain követhetjük a halmazok és a tömbök változását, a 10a.ábra a negyedik lépés után kialakult állapotot mutatja be. Az itteni fának a kész pontok által meghatározott része már végleges, míg a többi pont elődje, így a fa szerkezete még módosulhat. Összevetve a 9a.ábrával - ami a végállapotot mutatja - láthatjuk, hogy az eljárás még hátralévő részében módosul pl. a c és j pont elődje.

10a. ábra

10b. ábra

Megjegyezzük, hogy a K halmazt csak a jobb szemléltetés kedvéért használtuk, az algoritmusból el is hagyható.

Az eljárást tárigény szempontjából elemezve láthatjuk, hogy végrehajtásához csak 3 darab, egyenként pontszám elemű tömb szükséges (feltéve, hogy mint a példában, az aktív pontok halmazát is egy tömb tárolja). Ez lehetővé teszi az alkalmazását nagy (több ezer vagy tízezer pontos) hálózatoknál is. Az is könnyen látható, hogy a fa - építés jól illeszkedik a hálózatnak az éltárolás formájú tárolási módjához is, hiszen az egy kezdőpontból kimutató élek (amiket az eljárás b) pontjában kell sorra vennünk) egymás mellett vannak ennél a tárolási formánál.

Az eljárás számításigénye a pontszám négyzetével arányos, mivel minden lépésben (az a) pontban) átkerül egy pont a kész halmazba (külső ciklus) és ezen belül a b) pontban egy maximum pontszámszor futó ciklus megy. Tehát ha az összes utat (minden minimális fát) ki kell számolnunk, akkor sem rosszabb elvi nagyságrendben mint a mátrixos módszer. Ténylegesen persze itt több a számolás a több adminisztrációs számítás miatt.

A tényleges számításigény attól is függ, hogy hogyan kezeljük az A halmazt. A példában ezt egy - a távolság szerint növekvően rendezett - tömbben tartjuk, az új aktív pontot eszerint besoroljuk, ennek következtében a kész halmazba mindig az első aktív pont kerül át. Ez egy egyszerű, könnyen követhető módszer, de nem a legjobb. Az A speciális tárolásával és kezelésével lényegesen csökkenthető a besorolás - kiválasztás számításigénye és ezzel a fa - építés ideje is. Egy ilyen lehetőség például a kupacrendezés, ami önmagában is érdekes feladat és amire egy későbbi cikkben még vissza fogunk térni.

Az eddigiek után az Olvasó logikusan felvetheti a kérdést, hogy mi van akkor, ha csak egy viszonylatban keresünk utat, van -e erre még egyszerűbb, gyorsabb eljárás. A válasz nem, mivel nem ismert olyan algoritmus ami csak egy utat ad, más utak építése nélkül. Ehhez a problémához kapcsolódik a jelen témához adott záró feladatunk is: gondolja meg az Olvasó, hogyan kellene módosítani a fa - építést, ha a cél csak egyetlen (vagy több azonos kezdőpontú, de nem minden pontra mint végpontra kiterjedő) viszonylat minimális útjának meghatározása.