Matematika | Diszkrét Matematika » Podobni Katalin - Legrövidebb útkereső algoritmusok

http://www.doksihu EÖTVÖS LÓRÁND TUDOMÁNYEGYETEM TERMÉSZETTUDOMÁNYI KAR Legrövidebb útkereső algoritmusok A diplomamunkát készítette: Podobni Katalin Matematika Bsc Matematikai elemző szakirány Témavezető: Nagy Adrienn PhD hallgató Eötvös Lóránd Tudományegyetem Természettudományi kar Operációkutatási tanszék Budapest, 2009 http://www.doksihu Tartalomjegyzék Tartalomjegyzék 1 Bevezetés . 2 2 Gráfelméleti fogalmak, jelölések . 3 2.1 Gráfok ábrázolási módjai . 5 3 „Legrövidebb út?” Mit jelent ez? . 7 4 Az algoritmusok . 9 4.1 5 Egy kezdőpontból az összes többi pontba vezető legrövidebb út . 9 4.11 Szélességi keresés . 9 4.12 A Dijkstra algoritmus . 12 4.13 A Bellman-Ford-algoritmus. 21 4.2 Két adott csúcs közötti legrövidebb út . 26 4.3 Egy adott csúcsba érkező legrövidebb utak . 28 4.4 Legrövidebb utak minden csúcspárra . 28 4.41 Floyd algoritmusa . 28 4.42 Warshall algoritmusa. 32

4.43 Johnson algoritmusa . 34 A matematikában kevésbé ismert módszerek . 38 5.1 Informált keresési stratégiák . 38 5.11 A mohó legjobbat-először keresés. 38 5.12 Az A* algoritmus . 40 6 Összefoglalás . 43 7 Irodalomjegyzék. 44 8 Köszönetnyilvánítás . 45 1 http://www.doksihu 1. Bevezetés 1 Bevezetés A gráfok rendkívül gyakran használt struktúrák és a gráfokkal foglalkozó algoritmusok alapvető szerepet játszanak a számítástudományban. Számos érdekes probléma fogalmazható meg gráfok segítségével. Ezek közül talán az egyik legjelentősebb a legrövidebb utak problémája. A legkézenfekvőbb példa: hogyan jutunk el a leggyorsabban A városból a B városba? De számos más kérdés is megoldható vele, mint például az ütemezéselmélet témakörébe tartozó J | n  2 | Cmax probléma, vagy az informatikában a mesterséges intelligencia területén előforduló nehézségek. A probléma sokszínűsége miatt

megoldására számos algoritmus született. A szakdolgozat legfőbb célja, hogy bemutassa ezen eljárások legnépszerűbbjeit, rámutatva előnyeikre, hátrányaikra valamint a közöttük lévő különbségekre, hasonlóságokra. A dolgozat végén bemutatjuk a már fent említett mesterséges intelligencia területén használt két alapvető módszert is, amelyek a matematikai algoritmusokhoz képest már jelentősebb változtatásokat mutatnak. Elsőként alapvető, a szakdolgozat megértéséhez elengedhetetlen gráfelméletbeli fogalmakról esik szó, utána pedig magát a problémát definiáljuk. Ezek után következik az algoritmusok részletes elemzése, melyeket aszerint csoportosítunk, hogy a probléma mely altípusát oldják meg. Természetesen sok példa és ábra is segíti érthetőbbé tenni a témát, illetve hangsúlyozni annak fontosságát. Ezen kívül, a túlzott matematikai („száraz”) jelleg elkerülése végett a dolgozatban helyet kap a

történelmi háttér, valamint az algoritmusok szülőatyjainak főbb életmozzanatai, egyéb szerepük a matematikában. Néhány helyen az algoritmus létrehozóitól vett idézetekkel díszítjük a leírásokat, hogy megismerhessük az ő véleményüket is. 2 http://www.doksihu 2. Gráfelméleti fogalmak, jelölések 2 Gráfelméleti fogalmak, jelölések Ebben a fejezetben foglaljuk össze azokat a jelöléseket és fogalmakat, amelyekre elengedhetetlenül szükségünk van a téma kifejtéséhez, és amelyeket a szakdolgozatban használni fogunk. Definíció (gráf): Egy G gráf két halmazból áll: a csúcsok vagy pontok V halmazából, mely egy véges, nem üres halmaz; és az élek E halmazából, melynek elemei bizonyos V-beli párok. Jelölések: - � : egy H halmaz elemszámát jelöli. Az egyszerűség kedvéért legyen most � az adott gráf csúcshalmazának száma. - � − ��� az élhalmazának elemszámát jelöljük. Tehát � = (�, �) gráf

esetében � = � és � = � . Egy gráf nagyon sok probléma szemléltetésére szolgálhat, a legegyszerűbb például az úthálózat, telefonhálózat, de akár terület-felosztási illetve házassági problémát is ábrázolhatunk vele. A gráfokat többféle szempontból is szokás csoportosítani. A legjelentősebb szempont az irányítottság. Definíció (irányított gráf): Az irányított gráfban minden él irányított (másképp fogalmazva a csúcsok rendezettek). Az irányítást nyilak segítségével jelöljük Az (�, �) irányított él jelölésére használni fogjuk a � � változatot is. 1. ábra: Irányított gráf 3 http://www.doksihu 2. Gráfelméleti fogalmak, jelölések Amennyiben nincs irányításunk, vagy ha minden él oda és vissza is irányítva van, akkor irányítatlan gráfról beszélünk. Ekkor nem teszünk különbséget az (�, �) és a (�, �) élpár között. 2. ábra: Irányítatlan gráf Mint ahogy már fentebb

utaltunk rá, az objektumok (csúcsok) közötti kapcsolat sokszor jelentheti út létezését vagy kommunikáció lehetőségét. Ilyenkor gyakran költségek vagy súlyok tartoznak az élekhez, amelyek az út esetében időt vagy akár pénzt is jelenthetnek (gondoljunk csak az autópályákra, amelyek használatáért fizetni kell). Ezt a kapcsolatot egy valós értékű függvénnyel fogjuk leírni, melynek értelmezési tartománya a gráf élhalmaza, az érték készlete pedig a valós számok halmaza és �-val, a költség szó kezdőbetűjével jelöljük, tehát �: � ℝ. A súlyokat az élekre szokás írni 3. ábra: Súlyozott gráf Definíció (út): Egy út – akár irányított, akár irányítatlan gráfban – csúcsok olyan �1 , , �� sorozata (lehet egyelemű is), melyben minden (�� , ��+1 ) é�� (1 ≤ � ≤ � − 1) a gráfnak. Irányított gráfoknál az �-ból �-be menő útra � ↝ � jelöléssel is fogunk utalni

Definíció (út hossza): Legyen adott egy � = (�, �) irányított vagy irányítatlan gráf a �(�), � ∈ � élsúlyokkal. A G gráf egy �-ból �-be menő útjának hossza az úton szereplő élek súlyának összege. 4 http://www.doksihu 2. Gráfelméleti fogalmak, jelölések 2.1 Gráfok ábrázolási módjai Két módszert szokás alkalmazni egy � = (�, �) gráf ábrázolására. Az első az éllistás ábrázolási mód. Definíció (éllista): A gráf minden csúcsához egy lista tartozik. Az i V csúcs listájában tároljuk az i -ből kimenő éleket, és (amennyiben vannak) a súlyukat is. A listák összességét egy tömbben tároljuk. Legyen a tömb neve Szomszéd . Vagyis Szomszéd [ i ] elemei az i csúcs G-beli szomszédjai. Ha G irányított, akkor a szomszédsági listák hosszainak összege | E |, hiszen egy (i , v) élt úgy ábrázolunk, hogy v -t felvesszük a Szomszéd [ i ] listába. Ha G irányítatlan, akkor az összeg 2 | E |

mert (i , v) irányítatlan él ábrázolása során i -t beletesszük a Szomszéd [ v ]-be, míg v -t a Szomszéd [ i ]-be. Akár irányított, akár irányítatlan a gráfunk, a szomszédsági listás ábrázoláshoz szükséges tárterület mérete O(max(V , E))  O(V  E) . Az éllistás ábrázolás legjobban a ritka gráfok esetében alkalmazható. Definíció (ritka gráf): Egy gráfot ritkának nevezünk, ha | E | sokkal kisebb, mint | V |2. (Thomas H. Cormen, Charles E Leiserson, Ronald L Rivest, 2001) 4. ábra: Súlyozott irányítatlan gráf és a hozzá tartozó éllisták 5 http://www.doksihu 2. Gráfelméleti fogalmak, jelölések 5. ábra: Irányított gráf és a hozzátartozó éllisták A második módszer, a szomszédsági (adjacencia)-mátrix. Definíció (szomszédsági mátrix): A � = (�, �) gráf szomszédsági-mátrixa a következő - a V elemivel indexelt – n  n -es mátrix: A i , j   0 (i , j )  E 1 (i , j )  E .

Irányítatlan gráfok esetén a szomszédsági mátrix szimmetrikus lesz (azaz A i , j   A  j , i  teljesül minden i , j csúcspárra). Ha az élekhez még költségeket is nyilván kell tartani, akkor egy olyan K mátrixot szokás használni, amelyben K i , j   0 , ha i  j , K i , j   k(i , j ) , ha i  j és (i , j ) éle G-nek, K i , j    egyéb esetben. Tulajdonképpen a  jelzi egy él nemlétét Ezek alapján a fentebb látható 4. ábra adjacencia-mátrixai: 0  1 A  1  1 0  1 0 0 0 0 1 0 0 1 1 1 0 1 0 0 0  0 1  0 0  0  3 K  10  6 *  3 10 6 *   0 *  * 0 5 12   * 5 0  * 12 0  Az éllisták együttesen aszimptotikusan kevesebb tárterületet igényelnek, mint a csúcsmátrix, azonban a használat során a hatékonyságban ugyanennyivel elmaradnak attól, így ha a gráf nem túl nagy,

szerencsésebb szomszédsági mátrixszal ábrázolni. Ha a gráf nem súlyozott, akkor az adjacencia mátrixos leírás tovább javítható. Ebben az esetben a mátrix elemei lehetnek bitek, így jelentősen csökkenthető a szükséges tárterület mérete. 6 http://www.doksihu 3. „Legrövidebb út?” Mit jelent ez? 3 „Legrövidebb út?” Mit jelent ez? Definíció (legrövidebb út): Legrövidebb út alatt a gráfelméletben egy minimális hosszúságú utat értünk egy gráf két különböző � és � csúcsa között. Amennyiben a gráfunk éleihez nem tartoznak súlyok, akkor ez egyet jelent egy olyan úttal � és � csúcs között, amelyben a legkevesebb él szerepel. Ha vannak súlyok a gráf élein, akkor pedig olyan útról beszélünk, amelynek élein szereplő súlyok összege minimális. Vagyis ha adott egy � = (�, �) gráf a �(�), � ∈ � élsúlyokkal, akkor d(u , v)  min f P k( f ) ahol P út � és � között. Egyes

könyvekben ez a definíciója az u és v csúcsok közötti távolságnak, illetve a legrövidebb út súlyának, ha u  v , ha u  v akkor ez a távolság, illetve súly 0, ha nincs út u és v között, akkor ∞. Az alábbi változatokra osztható a probléma (és a továbbiakban ez alapján csoportosítjuk az algoritmusokat): 1. Legrövidebb út egy kiinduló pont és az összes többi pont között: meg szeretnénk találni az összes v V csúcshoz egy adott s V kezdőcsúcsból odavezető legrövidebb utat. 2. Legrövidebb út két különböző csúcs között: keressük egy adott u csúcsból egy adott v csúcsba vezető egyik legrövidebb utat. 3. Legrövidebb út egy végpont és az összes többi pont között (ez az 1 megfordítása). 4. Legrövidebb út az összes csúcspár között: keressük az összes u és v csúcspárra egy u -ból a v csúcsba vezető legrövidebb utat. Természetesen akadhat olyan legrövidebb út probléma, amelyben előfordulnak

negatív élek. Definíció (negatív kör): A � = (�, �) irányított gráf olyan köre, amelyben az élek súlyának összege negatív. Amennyiben nincs a gráfban negatív kör bármelyik v V csúcs esetén a legrövidebb út súlya jóldefiniált marad. Ha vannak u -ból elérhető negatív körök, 7 http://www.doksihu 3. „Legrövidebb út?” Mit jelent ez? akkor viszont a legrövidebb út súlya definiálatlan lesz, ugyanis ilyen esetben mindig van kisebb súlyú rövidebb út, ha a feltételezett legrövidebbhez hozzávesszük a negatív kör egy bejárását. Ilyen esetekben ezt a távolságot  -nek definiáljuk. (Thomas H Cormen, Charles E Leiserson, Ronald L Rivest, 2001) 8 http://www.doksihu 4. Az algoritmusok 4 Az algoritmusok 4.1 Egy kezdőpontból az összes többi pontba vezető legrövidebb út 4.11 Szélességi keresés A szélességi keresés az egyik legegyszerűbb gráfbejáró algoritmus, ezen alapul sok fontos gráf algoritmus, többek

között Dijkstra algoritmusa is. Ez az eljárás az egységnyi súlyokkal ellátott gráf esetén keresi meg az u V kezdőpontból az összes többi pontba vezető legrövidebb utakat (ebben az esetben a legrövidebb út alatt a legkevesebb élből álló utat értjük) úgy, hogy G éleit szisztematikusan megvizsgálja és kiszámítja az elérhető csúcsok távolságát (legkevesebb él) u -tól. Elnevezése onnan ered, hogy az algoritmus az u -tól k távolságra lévő csúcsokat még azelőtt eléri, mielőtt egy k  1 távolságra levőt elérne, szemléletesen: egy egyre szélesedő körben vizsgálódik. A továbbiakban feltesszük, hogy a � = (�, �) gráfot éllistásan ábrázoljuk. Egyszerű szavakkal megfogalmazva az eljárás a következő: meglátogatjuk az első csúcsot, majd ennek a csúcsnak az összes szomszédját. Azután ezen szomszédok összes olyan szomszédját, ahol még nem jártunk, és így tovább. A legjobb ismert módszer ennek

megszervezésére egy sort alkalmaz. Először beletesszük a kezdőcsúcsot, majd „meglátogatottsági sorrend szerint” annak az összes szomszédját, majd a kezdőcsúcs elsőként meglátogatott szomszédjának összes szomszédját, majd a kezdőcsúcs másodikként meglátogatott szomszédjának összes szomszédját és így tovább. Definíció (sor): A sor adatszerkezet alapja egy elemekből álló kettős láncolt lista. Két alapművelet van: sorba (v, Q) a v elemet a Q sor végére illeszti; első (v, Q) pedig visszaadja és kitörli Q -ból annak első elemét. A sort szokás még FIFO-listának (first in, first out) is nevezni. A módszer általános lépéseinek lényege, hogy vesszük a sor elején levő u csúcsot. Ezt töröljük a sorból, meglátogatjuk azokat a v szomszédjait, amelyeket 9 http://www.doksihu 4. Az algoritmusok eddig még nem láttunk, majd ezeket a v csúcsokat a sor végére tesszük. Jelentse D  v  a v csúcsnak az u -tól való

távolságát. BEJÁR (G, u) eljárás 1. procedure bejár 2. begin 3. for s  1 to n do 4. bejárva  s  :=HAMIS 5. for s : 1 to n do 6. if bejárva  s  =HAMIS then 7. szb ( s ) 8. end 9. procedure szb ( s ) 10. var 11. Q :csúcsokból álló sor 12. u, v :csúcsok 13. begin 14. bejárva  s  :=IGAZ 15. sorba ( s, Q) 16. while Q nem üres do 17. begin u :=első (Q) 18. 19. for minden u  v  E élre do 20. if bejárva  v  =hamis then 21. begin 22. bejárva  v  :=IGAZ 23. sorba (v, Q) 24. 25. 26. 27. D  v   D u   1 end end end A bejárás során felépíthetjük a gráf egy szélességi feszítő erdejét. E fákban osztályozhatjuk az éleket: Definíció (éltípusok): Tekintsük a G irányított gráf egy szélességi bejárásaként kapott T szélességi erdőt, G egy u  v éle:  faél, ha u  v éle T -nek,  előreél, ha u  v nem faél, v leszármazottja u -nak T -ben, és u  v ;  visszaél, ha u

leszármazottja v -nek T -ben, 10 http://www.doksihu 4. Az algoritmusok  keresztél, ha u és v nem leszármazottai egymásnak. Az alábbi 6. ábra szemlélteti az éltípusokat: 6. ábra: e-előreél, f-faél, k-keresztél, v-visszaél A szélességi bejárás költsége O(n  e) , mert minden csúcsot pontosan egyszer teszünk be a sorba, és minden irányított élet egyszer vizsgálunk meg (amikor a kezdőpontja kikerül a sorból). A szélességi bejárás segítségével a d (u, v) távolságok lineáris időben meghatározhatók, ugyanis a következők teljesülnek: Tétel: Legyen u  x1 , x2 ,., xn a csúcsoknak a szélességi bejárás szerinti sorrendje Ekkor 1. D  x1   D  x2    D  xn  2. Ha u  v éle G-nek, akkor D v   D u   1 3. D v   d (u, v) teljesül minden v V csúcsra Bizonyítás: 1. Könnyen látható, hogy a csúcsok az u  x1 , x2 ,, xn sorrendben kerülnek bele a Q sorba, tehát így is

kerülnek ki. Tehát ha egy xi  u csúcs előbb van mint xi 1 , akkor x szülője is megelőzi xi 1 szülőjét a sorban, ebből könnyen látszik, hogy D  x1  ,., D  xn  számsorozat nem csökkenő Indukció alapján ez könnyen belátható a gyökérre és a fiaira, később pedig D  xi   D  szülő ( xi )  1 és 11 http://www.doksihu 4. Az algoritmusok D  xi 1   D  szülő ( xi 1 )  1 , ha az apák D  szülő ( xi )  D  szülő ( xi 1 )  D  xi   D  xi 1 . különbözők, Amennyiben a akkor szülők megegyeznek, akkor D  xi   D  xi 1 . 2. Vizsgáljuk meg, mi történik, ha v kikerül a Q sorból, és tekintsük (u, v) élet Ha bejárva u  = hamis , akkor u szülője v , tehát D u   D v   1 . Ha u -t már korábban láttuk, akkor nyilván u szülője előbb van a sorban, mint v , vagyis az előző alapján: D  szülő (u )

 D v  . Ebből pedig világosan látszik a bizonyítani kívánt egyenlőtlenség, csak mindkét oldalhoz egyet kell hozzáadni. 3. Nyilvánvaló, hogy D v   d (u, v) érvényes minden v V csúcsra, elég tehát a fordított egyenlőtlenséget igazolni. Legyen u  y0 , y1 ,, yk  v egy minimális hosszúságú G-beli irányított s -ből v -be vezető út. Ennek éleire sorra alkalmazzuk a tétel előzőleg már bebizonyított 2. állítását és láthatjuk, hogy ez az állítás is helyénvaló. ∎ 4.12 A Dijkstra algoritmus Dijkstra algoritmusa egy adott kezdőcsúcsból az összes többi csúcsba vezető legrövidebb utak problémáját egy súlyozott, irányított � = (�, �) gráfban, abban az esetben oldja meg, ha a nincsenek negatív súlyok az éleken, vagyis ha minden u  v élre k (u, v) ≥0 teljesül. Az algoritmust Edsger Wybe Dijkstra, holland matematikus és informatikus alkotta meg 1956-ban. 4.121 Edsger Wybe Dijkstra 7. ábra:

Edsger Wybe Dijkstra 12 http://www.doksihu 4. Az algoritmusok Edsger Wybe Dijkstra 1930-ban született a hollandiai Rotterdamban. Szülei elismerten jó végzettségű értelmiségiek voltak, édesapja kémikus, édesanyja matematikus volt. 1942-ben, 12 éves korában bekerült egy igen magas színvonalú gimnáziumba, az Erasminium Gimnáziumba, ahova kivételes tehetségek jártak. Dijkstra sok különböző tárgyat tanult, mint például: görög, latin, francia, német és angol nyelv, valamint biológia, matematika és kémia. 1945-ben még jogi pályára készült, hogy utána képviselőként dolgozzon. Azonban abból kifolyólag, hogy kémiából, biológiából és matematikából jó eredményei voltak, úgy döntött, hogy a leideni egyetemen folytatja tanulmányait és elméleti pszichológiát hallgat. 1951 nyarán a cambridge-i egyetemen ismerkedett meg először a programozással. 1952 márciusától részmunkaidőben dolgozott egy amsterdami matematikai

központnál, ekkor kezdte el igazán érdekelni az informatika. Amilyen gyorsan csak lehetett befejezte a pszichológiai tanulmányait és elkezdett hódolni ennek az új szenvedélyének. Miután 1957-ben megházasodott, folytatta munkáját a matematikai központban, miközben az 1970-es évek elején az egyesült államokbeli Borroughs Corporation kutatási tagja is volt. 1972-ben megkapta az ACM Turing Díjat, 1974ben az AFIPS Harry Good Memorial Díjat Az 1980-as évek elején a texasi Austinba költözött, majd 1984-ben állást is kapott az Informatikai Tudományok Egyetemén, ahol 69 éves koráig dolgozott. 1999-ben lett professor emeritus Rákban halt meg nueneni otthonában 2002. augusztus 6-án Főbb publikációi: - Go To Statement Considered Harmful Communications of the ACM (1968), - A note on two problems in connexion with graphs. Numerische Mathematik (1959) - Structured Programming, melyet O.-J Dahl-el és C A R Hoare-val írt 1972ben Néhány cikke: -

„The Humble Programmer” (1972. augusztus) - „How do we tell truths that might hurt?”(1982. május) (Wikipedia, 2007) A másodikként említett publikációja alapján, hogyan is gondolkodott ő a gráfok problémáiról: 13 http://www.doksihu 4. Az algoritmusok „Összefüggő gráfok két problémája” „Tekintsünk n darab pontot, melyek közül néhányat vagy mindegyiket él köt össze, az élek hossza adott. Tegyük fel, hogy legalább egy él létezik valamely két pont között Nézzük az alábbi két problémát: Első probléma: Készítsük el az n csúcs minimális költségű fáját. (Azt a fát, amelyben minden csúcs között egy és csakis egy út vezet.) Az algoritmus első lépéseként három csoportra osztjuk az éleket. I. Az eljárás során már elfogadott élek. II. A következő lépésben az I. csoportba választandó élek halmaza III. A kimaradó élek (vagy már elutasítottuk őket, vagy még nem vizsgáltuk meg). A csúcsokat két

csoportba sorolhatjuk. A: Azon élek végpontjai, amelyek az I. csoportban vannak B: A kimaradó csúcsok (egy és csakis egy II. csoportbeli él vezet minden ilyen kimaradó csúcshoz) Kezdjük az eljárást egy tetszőleges A csoportbeli csúccsal, majd válasszuk ki azokat a II. csoportbeli éleket, amelyeknek egyik végpontja az A csúcs. Kezdetben az I csoport üres Ezek után ismételjük az alábbi két lépést: 1. lépés: A II csoport legrövidebb élét tegyük I-be és az eddig a B csoportban lévő végpontját tegyük Aba 2. lépés: Tekintsük azokat az éleket, amelyek az éppen előbb az A csoportba helyezett csúcsból indulnak és egy B csoportbeli csúcsba érkeznek. Ha ezen élek közül valamelyik hosszabb, mint a neki megfelelő II. csoportbeli él, akkor elutasítjuk; amennyiben rövidebb annál, akkor kicseréljük őket és ezt az élt tesszük a II. csoportba, és a másikat vetjük el Ezután visszatérünk az 1. lépéshez és a két lépést addig

ismételgetjük, amíg a B és a II csoport üres nem lesz. Végül az I csoportban lévő élek megadják a keresett fát Ez a megoldás használhatóbb, mint a Kruskal-, a H.Loberman- vagy a AWeinberger-féle módszer Az ő megoldásukban az összes élek elsősorban a hosszúság szerint vannak osztályozva. Még akkor is, ha az a csúcsok koordinátáiból kiszámolható, az eljárásukban az összes él egyidejű tárolása szükséges. A fenti eljárás során legfeljebb csak n darab él adatát kell tárolni, ugyanis a 2. lépés során csak az I és a II csoportbeli éleket vizsgáljuk. ()” (E.WDijkstra, 1959) 4.122 Dijksta algoritmusa éllistával A Dijkstra algoritmus azoknak a csúcsoknak az S halmazát tartja nyilván, amelyekhez már meghatározta az u kezdőcsúcsból odavezető legrövidebb út 14 http://www.doksihu 4. Az algoritmusok súlyát. Az algoritmus minden lépésben a legkisebb legrövidebb-út becslésű x V  S csúcsot választja ki, beteszi az x

-t S -be, és minden x -ből kivezető éllel egy-egy közelítést végez. A V  S csúcsok nyilvántartására egy Q sort alkalmazunk, amelyet azok d értékeivel töltünk fel. DIJKSTRA (G, u) eljárás 1. 2. 3. 4. procedure Dijkstra begin for minden v V csúcsra do D v  :  szülő v  :  5. 6. end D u   0 7. 8. var S :  9. 10. Q : csúcsokból álló sor 11. begin 12. while Q nem üres do 13. begin x : minimális Q 14. 15. S : S   x 16. for minden v  Szomszéd  x  -re do if D v  D  x  k ( x, v) then begin D v  : D  x  k ( x, v) 17. 18. 19. 20. 21. 22. 23. szülő v   x end end end A Dijkstra algoritmus mohó stratégiát alkalmaz, hiszen mindig a „legközelebbi” csúcsot választja ki V  S -ből, hogy azután az S halmazba tegye. A mohó stratégiák általában nem adnak optimális eredményt, de az alábbi tétel mutatja, hogy a Dijkstra algoritmus

szükségszerűen a legrövidebb utakat állítja elő. Tétel (Dijkstra algoritmus helyessége): Ha Dijkstra algoritmusát egy nemnegatív k súlyfüggvénnyel súlyozott, u kezdőcsúcsú irányított � = (�, �) gráfban futtatjuk, akkor annak befejezésekor minden x V csúcsra teljesül, hogy D  x   d  u, x  . 15 http://www.doksihu 4. Az algoritmusok Bizonyítás: Indirekten tegyük fel, hogy x az első olyan csúcs, amire az S halmazba történő beillesztésekor igaz, hogy D  x   d ( x, u ) . Nyilván x  u , tehát S   közvetlenül x beillesztése előtt, tehát léteznie kell egy u és x csúcs közötti útnak, különben D  x   d (u, x)   egyenlőség fennállna, és ez ellentmondana a kezdeti D  x   d ( x, u ) feltevésünknek. Ezek alapján léteznie kell egy p legrövidebb útnak u és x között, ahol u  S és x V  S . Legyen y az első olyan csúcs a p úton, amely már a V  S halmazban

van, és legyen y szülője a p úton a z csúcs. Ezek alapján a p -t felbonthatjuk két részre: p1  re és p2  re, ahol p1 az u és a z csúcs közötti út, amelynek csúcsai S -ben vannak, p2 pedig az y és az x csúcs közötti út, amelynek minden pontja V  S halmazban van. Mivel y egy u és x csúcs közötti legrövidebb úton az x előtt van, a súlyok nemnegatívak valamint d (u, y)  d (u, x) és így D  y   d (u, y)  d (u, x)  D  x  . De x és y is a V  S halmazban van, ahonnan az algoritmus 8. sora az x -et úgy választja ki, hogy a D  x   D  y  egyenlőtlenség fennáll. Tehát D  x   d (u, x) , amely ellentmond a kezdeti feltevésünknek, vagyis D  x   d (u, x) .∎ (Thomas H Cormen, Charles E Leiserson, Ronald L. Rivest, 2001) 8. ábra: Dijkstra algoritmusának működése 4.123 Az algoritmus futási ideje Amennyiben a Q sort tömbbel valósítjuk meg: a kezdőértékek beállítása O(n) elemi

lépést vesz igénybe. A 14 sorban a minimumkeresés és a 17 sorban lévő 16 http://www.doksihu 4. Az algoritmusok vizsgálat szintén O(n) -et, mivel a 14. sorban levő minimumkeresés n  1 -szer fut le, így az algoritmus összidőigénye O(n2 ) művelet. A további elemzéshez szükséges bevezetni néhány új fogalmat: Definíció (kupac): Egy olyan adatszerkezet, amely segítségével egy rendezett halmaz egy S részhalmazát tároljuk. A kupac elemeit bináris fában tároljuk Definíció (minimumtörlés): A kupacszerkezet egyik alapművelete. Az adott rendezés szerinti legkisebb elem törlése. Definíció (kupac-tulajdonság): Egy tetszőleges csúcs elem nem lehet nagyobb a fiaiban levő elemeknél. Definíció ( d -kupac): Az S elemit egy teljes d -fa csúcsaiban helyezzük el úgy, hogy teljesüljön a kupac-tulajdonság. Ha a gráf ritka, akkor célszerű a Q sort bináris kupaccal implementálni a D   értékek szerint. A kezdeti kupacépítés O(n)

költséggel végezhető el A 14 sorban lévő minimumkeresést egy O(log n) költségű minimumtörlés művelettel oldjuk meg. A D   értékeinek újraszámolását és a kupac-tulajdonság helyreállítását csak a választott csúcs szomszédjaira kell elvégezni. Minden csúcsot pontosan egyszer választunk ki, és a szomszédok számának összege e . Tehát az összidőigény O((n  e) log n) . Sűrű gráfok esetén még komolyabb gyorsítás érhető el alkalmas d -kupaccal. Ekkor a futási idő O(n  nd log d n  e log d n) lesz. 4.124 Az utak nyomon követése Sokszor nemcsak a legrövidebb utak hosszára vagyunk kíváncsiak, hanem magukra az utakra is: az algoritmus 20. sora tartalmazza ezt, hiszen minden csúcs szülőjét feljegyezzük és akár egy újabb tömbben elhelyezhetjük, anélkül, hogy a futási időt megnövelnénk. 17 http://www.doksihu 4. Az algoritmusok 4.125 Érdekességek Természetesen a módszer működik irányítatlan gráfok

esetén is hiszen, ahogy már említettük minden irányítatlan él felfogható úgy, mintha mindkét irányban irányított lenne. Ezek alapján már nem csodálkozunk azon, hogy mennyi mindenre jó ez az eljárás. Többek között az ütemezéselméletben előforduló J | n  2 | Cmax problémára, melynek jelentése: két olyan munkának a befejezési idejét szeretnénk minimálisra szorítani, amelyek számos kisebb részmunkából tevődnek össze. A részmunkákat több különböző gép végzi el, a gépek sorrendje tetszőleges. Legyen adott a két munka megmunkálási ideje, jelöljük ezt pi , j -vel, ahol az i a gépek, a j pedig a munkák sorszáma. Például a p4,3  5 óra jelentése: a harmadik munkát a negyedik gép 5 óra alatt végzi el. Ebben a feladatban j  1 vagy 2, i  m , ahol mℤ+. Ezen kívül adottak még minden j -re a gépek egy  j sorrendje A megadott sorrendek alapján könnyen ábrázolhatjuk a folyamatot. 9. ábra: A folyamat

szemléltetése Az ábra y tengelyén a  2 szerinti pi ,2 hosszú részek adják a felosztást, míg az x tengelyén a 1 szerinti pi ,1 hosszú részek. A kép egy hatgépes esetet mutat be A 18 http://www.doksihu 4. Az algoritmusok szürkével jelzett négyzetek a tiltott négyzetek, az azonos hosszúságú szakaszok metszete, az ábra O pontjából F pontjába tartó sötétszürke görbe a megengedett görbe. Jól látható, hogy vízszintes, függőleges és 45∘-os szakaszok alkotják Fontos tulajdonsága, hogy nem lép be tiltott négyzetbe, valamint ha vízszintesen halad, akkor y nem lehet belső koordináta, ha függőlegesen, akkor pedig x nem lehet az. Lemma: Minden megengedett ütemezés megad egy ilyen P megengedett görbét, S továbbá Cmax  h( P) , ahol h( P) = vízszintes szakaszok hossza + függőleges szakaszok S hossza + a 45∘-os szakaszok vetületének hossza ( Cmax : az S ütemezés által kapott minimális befejezési idő). (A lemma fordított

irányban is igaz) Ezek után könnyű meghatározni a célt: a legrövidebb görbe meghatározása. Van még egy szembetűnő dolog az ábrán: a tiltott négyzetek bal felső és jobb alsó sarkában látható pontok, ezek az úgynevezett speciális pontok. Ezek segítségével definiáljuk a speciális részgörbéket és a speciális görbét. Definíció (speciális részgörbe, speciális görbe): A speciális részgörbe speciális pontokat köt össze. A speciális görbe pedig a speciális részgörbék uniója Lemma: Minden megengedett P görbéhez P speciális görbe úgy, hogy h( P)  h( P ) . Vagyis keressük azt a legrövidebb speciális görbét, amely O -ból F -be megy. Ez alapján a feladat ekvivalens egy legrövidebb út problémával, ahol a gráfunk pontjai a speciális pontok, az élei a speciális pontokból indulnak az onnan induló speciális részgörbék másik végpontjába, melyekből egy vagy kettő lehet. Az élhosszúságot a h alapján kapjuk,

amelyek nemnegatívak, hiszen megmunkálási időkről beszélünk. A másik érdekes dolog, hogy a Dijkstra algoritmus módosításával legbiztonságosabb utat is lehet keresni. Legyenek az élsúlyok a tönkremenés valószínűségei, vagyis minden e élhez adott egy p valószínűség, hogy az adott él tönkremegy-e. Ezek alapján egy P út „el 19 http://www.doksihu 4. Az algoritmusok nem romlási”, „megmaradási” esélye  (1  p(e)) . Ezt szeretnénk maximalizálni eP Vegyük ennek a kifejezésnek a logaritmusát (ezt megtehetjük, mert a logaritmus függvény monoton) és ezt maximalizáljuk: max  (1  p(e)) eP max log  (1  p(e))  max  log(1  p(e))   min  ( log(1  p(e))) eP eP eP Ezek alapján írjuk át a gráfunk költségeit, legyen az új költség: k (e)   log(1  p(e)) . Erről tudjuk, hogy nemnegatív, vagyis alkalmazható a Dijkstra algoritmus erre az új költségekkel ellátott

gráfra. Lássunk egy egyszerű példát: tegyük fel, hogy egy háborús övezet katonái az alábbi 10. ábra lévő térképet kapják az ellenséges területről A katonáknak el kell jutni az egyessel jelzett városból a kettessel jelzett városba. A gráf élein szereplő valószínűségek azt mutatják, hogy az i -dik városból a j -dik városba mekkora eséllyel nem sikerül eljutni. 10. ábra: A kapott térkép A következő 11. ábra mutatja, hogy melyik utat kell választaniuk, hogy a legnagyobb eséllyel eljussanak a kettes jelzésű városba. 11. ábra: A legbiztonságosabb út 20 http://www.doksihu 4. Az algoritmusok 4.13 A Bellman-Ford-algoritmus A Bellman-Ford-algoritmus az adott kezdőcsúcsból induló legrövidebb utak problémáját abban az esetben oldja meg, amikor vannak az élek között negatív súlyúak, de nem találunk a gráfban negatív kört. Az algoritmus szülőatyjaként Richard Bellmant és ifjabb Lester Randolph Fordot tisztelik. 4.131

Lester Randolph Ford, Richard Bellman Ifjabb Lester Randolph Ford 1927. szeptember 23-án született A „Network Flow” programozás egyik úttörője. Édesapja az idősebbik LR Ford, aki maga is elismert matematikus, a Farey sorozatokra adott egy bámulatos értelmezést. Ifjabb L.R Ford nevéhez fűződik többek között a Ford-Fulkerson algoritmus is, amely a maximális folyam problémát oldja meg. (Singh Nayandeep, 2001) Richard Ernest Bellman (1920. augusztus 26- 1984 március 19) alkalmazott matematikus volt, az 1953-as dinamikus programozás terén elért felfedezéséért volt méltán ünnepelt, valamint nevéhez köthető, sok a matematika más területén elért eredmény is. 12. ábra: Richard E Bellman New Yorkban született, ahol édesapja, John James Bellman egy élelmiszerüzletet vezetett a Bergen utcában a Prospest Park közelében Brooklynban. Bellman a középiskolát 1937-ben fejezte be az Abraham Lincoln Középiskolában (New York), és

matematikát hallgatott a brooklyni főiskolán, ahol 1941-ben szerezett BA diplomát, a későbbiekben pedig a Wisconsin-Madison Egyetemen megszerezte az MA diplomát is. A II világháború idején a hadseregnél az Elméleti Pszichológia Részlegen dolgozott Los Alamosban. 1946-ban megszerezte a Ph.D titulust a Princetonon A dél kaliforniai egyetem professzora 21 http://www.doksihu 4. Az algoritmusok volt, ösztöndíjas kutatója az amerikai Tudományok és Művészetek Akadémiájának (1975), valamint tagja a nemzeti Mérnöki Akadémiának (1977). 1979-ben az IEEE Becsület Medállal tüntették ki „A döntési eljárások és az ellenőrző rendszerek területén elért eredményéért, különösen a dinamikus programozásban alkotottakért.” Legfőbb műve a Bellman-Egyenlet (Wikipedia, 2009) 4.132 Az eljárás Adott egy k : E  ℝ súlyfüggvénnyel súlyozott irányított G  (V , E ) gráf, ahol a kezdőcsúcs az s . Az algoritmus visszajelzi, ha van a

gráfban s -ből elérhető negatív kör, ha nincs benne, akkor előállítja a megoldást. BELLMAN-FORD ( D, k , s) eljárás. 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. 19. 20. 21. 22. 23. procedue Bellman-Ford begin for minden v V csúcsra do D v  :  szülő v  :  end begin for i  1 to n  1 do begin for minden (u, v) élre if D v  D u   k (u, v) then begin D v : D u   k (u, v) szülő v  : u end end end begin for minden (u, v) élre do if D v  D u   k (u, v) then return HAMIS return IGAZ end Az 1-6. sorok a kezdeti értékek beállítását mutatják Aztán a 7-17 sorok ugyanazt az ellenőrzést végzik el mint a Dijkstra algoritmus esetében, végül a 1823. sorok keresnek negatív köröket 22 http://www.doksihu 4. Az algoritmusok Mielőtt az eljárás helyességének bizonyítására térnénk, definiáljuk a legrövidebb-utak fa fogalmát, valamint

bevezetünk két jelölést is. Definíció (legrövidebb-utak fa): Legyen G  (V , E ) egy irányított, k : E  ℝ súlyfüggvénnyel súlyozott gráf, és feltesszük, hogy G nem tartalmaz s kezdőcsúcsból elérhető negatív kört, azaz a legrövidebb utak jól definiáltak. Egy s-gyökerű legrövidebb-utak fa egy olyan G  (V , E ) részgráf, ahol V  V és E  E úgy, hogy - V az s-ből elérhető G-beli csúcsok halmaza, - G egy s gyökerű fa, és - minden v V csúcsra G -beli s-ből vezető út egy legrövidebb s-ből v-be vezető út a G-ben. Jelölések: - Vszülő: a nem  szülőjű G-beli csúcsokat tartalmazza és az s kezdőcsúcsot: Vszülő= v V : szülő v     s . - Eszülő: azok az irányított élek, amelyek a szülő értékekből vezetnek a Vszülő-beli   csúcsokba: Eszülő=  szülő v  , v   E : v Vszülő  s . Tétel (A Bellman-Ford-algoritmus helyessége):

Egy G  (V , E ) irányított gráfon futtassuk a BELLMAN-FORD-eljárást, ahol a súlyfüggvény a k : E  ℝ, és a kezdőcsúcs az s. Ha G nem tartalmaz az s-ből elérhető negatív köröket, akkor 1. minden v V csúcsra D v   d (s, v) , 2. a végeredményül kapott fa egy s gyökerű legrövidebb-utak fa (jelöljük ezt Gszülő=(Vszülő,Eszülő)-vel) 3. az algoritmus IGAZ értéket ad vissza, vagyis megadja a keresett legrövidebb utat 4. Ha G tartalmaz s-ből elérhető negatív kört, akkor az eljárás HAMIS értékkel tér vissza. Bizonyítás: Tegyük fel, hogy G nem tartalmaz s -ből elérhető negatív kört. 1. Tegyük fel, hogy v elérhető s -ből, legyen p  v0 , v1 ,, vk egy s -ből v -be vezető legrövidebb út (v0  s, vk  v) . A p út egyszerű (nincs benne ismétlődő 23 http://www.doksihu 4. Az algoritmusok csúcs), tehát k  n  1. Indukcióval könnyen bizonyíthatjuk, hogy minden i  0,1,., k  ra D vi   d

(s, vi ) Kezdetben D v0   d (s, s)  0 nyilván teljesül. Tegyük fel, hogy D vi 1   d (s, vi 1 ) fennáll, az i  dik lépésben az (vi 1 , vi ) éllel való összehasonlítás hatására D vi   d (s, vi ) , és ez meg is őrződik az eljárás során, mert: D v  D u   k (u, v)  d (s, u)  k (u, v)  d (s, v) . (Tudjuk, hogy d ( s, v) alulról korlátozza D  v  értékét.) Ha nem vezet út s -ből v -be, akkor az eljárás D v    értékkel tér vissza. Tehát D v   d  s, v    , mert definíció szerint, ha két csúcs között nincsen út, akkor a távolságuk végtelen. 2. Az első tulajdonság bebizonyítása nagyon egyszerű Definíció szerint egy legrövidebb út akkor és csak akkor véges, ha van a két csúcs között út. Az algoritmus során egy s -től különböző v csúcs akkor és csak akkor kap véges értéket, ha szülő v    . A második

tulajdonság bizonyítása indirekten történik. Tegyük fel, hogy Gszülő ben van kör, bizonyítandó, hogy ez negatív kör (Ekkor G -ben is kell lennie, de az ellentmondáshoz vezet.) A körön minden csúcs D   értéke véges, vagyis elérhetők s -ből. Indukció és az algoritmus 10-15 sorai alapján az alábbi egyenlőtlenség kapható: k k k i 1 i 1 i 1  D vi    D vi1    k (vi1, vi ) ahol c  v0 , v1 ,., vk a kör  vk  v0  Mivel a c kör minden csúcsa pontosan egyszer szerepel az egyes összegekben: k k  D v    D v  i 1 i i 1 i 1 Ebből következik, hogy k 0   k (vi 1 , vi ) i 1 Vagyis azt kaptuk, hogy G tartalmaz negatív kört, ami viszont elvezet a keresett ellentmondáshoz. 24 http://www.doksihu 4. Az algoritmusok A harmadik tulajdonság bizonyításának első lépése hogy igazoljuk, hogy ezek az utak valóban léteznek. Ez teljes indukcióval

könnyedén megtehető Azt kell még belátni, hogy legfeljebb egy út megy s -ből minden v Vszülő -beli csúcshoz. Indirekten tegyük fel, hogy két út is létezik valamely v Vszülő csúcshoz. 13. ábra: Annak bizonyítására, hogy csak egy s-ből v-be menő út van Gszülő-ben A p1 út s -ből v -be: s ↝ u ↝ x z ↝ v , a p2 út s -ből v -be: s ↝ u ↝ y z ↝ v , ahol x  y . Ám ekkor szülő  z   x és szülő  z   y , ami csak x  y esetén teljesül. 3. A befejezéskor minden (u, v)  E élre: D v  d (s, v)  d (s, v)  k (u, v)  D u   k (u, v) Tehát a 20. sorban lévő ellenőrzés után sem kapunk HAMIS értéket 4. Tegyük fel, hogy G -ben van negatív kör, jelöljük c  v0 , v1 ,, vk -vel, ahol  vk  v0  , és tegyük fel, hogy az eljárás IGAZ értékkel tér vissza. Mivel c egy negatív kör, ezért: k  k (v i 1 i 1 , vi )  0 . A feltevésünk miatt (IGAZ értékkel

tér vissza az algoritmus) az alábbi egyenlőtlenség teljesül: k k k  D v    D v    k (v i 1 i i 1 i 1 i 1 i 1 , vi ) Mivel a c kör mindegyik csúcsa pontosan egyszer szerepel az első két összegben, így k k  D v    D v  i 1 i i 1 i 1 k Vagyis 0   k (vi 1 , vi ) , ami ellentmondás.∎ i 1 (Thomas H. Cormen, Charles E Leiserson, Ronald L Rivest, 2001) 25 http://www.doksihu 4. Az algoritmusok 14. ábra: A Bellman-Ford eljárás működése 4.133 Az eljárás futási ideje és a legrövidebb út nyomon követése Az algoritmus futási ideje O(ne) , mivel a kezdő értékek beállítása O(n) az n  1 darab csúcson végzett összehasonlítás mindegyike O(e) ideig tart és a 18-23. sorokban lévő ellenőrzés O(e) idejű. A legrövidebb út nyomon követése ugyanúgy megy, mint a Dijkstra algoritmusnál. A szülő v  értékeket eltesszük egy tömbbe, ez nem

növeli a futási időt. 4.2 Két adott csúcs közötti legrövidebb út Nyilvánvalóan, ha megoldjuk az adott csúcsból az összes többi csúcsba vezető legrövidebb utak problémáját, akkor a két adott csúcs közötti legrövidebb út problémát is megoldottuk. Érdekes azonban, hogy nem ismert ennek a problémának olyan megoldó algoritmusa, amelyik aszimptotikusan gyorsabb lenne az adott csúcsból az összes többi csúcsba vezető legrövidebb utak problémájánál. Dijkstra a következőképpen elmélkedett erről a problémáról Numerische Mathematik című művében. „Összefüggő gráfok két problémája” „Tekintsünk n darab pontot, melyek közül néhányat vagy mindegyiket él köt össze, az élek hossza adott. Tegyük fel, hogy legalább egy él létezik valamely két pont között Nézzük az alábbi két problémát: () Második probléma: Keressük meg a legrövidebb utat két adott pont, P és Q között. Használjuk ki azt a tényt, hogy az R

csúcs rajta van a P és Q közti legrövidebb úton, a majdani ismeretek tartalmazzák a P és R közti legrövidebb utat. A megoldás során megkapjuk az összes többi csúcsba menő legrövidebb utat, melyek a hosszúságok sorrendjében keletkeznek, egészen addig, amíg Q-t el nem érjük. 26 http://www.doksihu 4. Az algoritmusok A megoldás első lépése, hogy a pontokat három csoportba osztjuk. A: Azok a csúcsok, amelyeknek P-től vett távolsága minimális. Ebbe a csoportba csak a P-től minimális távolságra lévő csúcsokat vesszük bele. B: A következő lépésben az A csoportba választható csúcsok halmaza. Ebben a csoportban az A halmazbeli pontokhoz kapcsolódó csúcsok vannak (a belőlük kiinduló él másik végpontja már Aban van). C: Kimaradó csúcsok. Az éleket is 3 csoportba soroljuk: I. A P csúcs és az A csoportbeli pontok közötti minimális utat alkotó élek. II. Azoknak az éleknek a halmaza, amelyekből kiválasztjuk a I. csoportba

helyezendő élet; egy és csakis egy él vezet ebből a halmazból mindegyik B halmazbeli csúcshoz. III. A kimaradó csúcsok (vagy már elutasítottuk őket, vagy még nem vizsgáltuk meg). Kezdetben minden csúcs C-ben, és minden él a III csoportban van. Először tegyük a P csúcsot az A csoportba, majd az alábbi lépéseket ismételgessük. Első lépés: Tekintsük az összes olyan r élet, amely az éppen az A csoportba tett csúcs és R között mennek, ahol R lehet a B illetve a C csoportban is. Ha R a B csoportban van, akkor vizsgáljuk meg, hogy ennek az r élnek a használata egy rövidebb utat eredményez-e, mint a neki megfelelő (ugyanabba a csúcsba menő) eddig ismert II. csoportbeli út Ha nem kapunk rövidebb utat az r él használatával, akkor r-et elutasítjuk (a III. csoportba tesszük), ha az r él használatával a kapott út rövidebb, mint a neki megfelelő út, akkor az eddig ismert utat lecseréljük erre az új, r élet használó útra. Amennyiben

az R csúcs C-ben van, tegyük B-be és az r élet pedig a II. csoportba Második lépés: Minden B csoportbeli csúcs és a P csúcs között egy és csakis egy út vezet, ha csak az I. és II. csoportba tartozó éleket vizsgáljuk, tehát minden egyes B csoportbeli csúcsnak véges távolsága van P csúcstól: azt a csúcsot, amelynek a legkisebb a távolsága P-től, tegyük az A halmazba, és a megfelelő élet helyezzük a II. csoportból az I csoportba Ezután térjünk vissza az első lépéshez és ismételgessük őket addig, amíg a Q csúcs az A halmazba nem kerül. Ekkor megkapjuk a keresett utat Megjegyzések: 1. A fenti eljárás abban az esetben is alkalmazható, ha az élek hossza függ attól, hogy elutasítjuk, vagy megtartjuk őket. 2. Az I és a II csoportban lévő élek esetében érdemes feljegyezni a csúcsaik távolságát P-től (növekvő sorrendben). Az I csoportbeli élek esetén ez a tényleges minimális távolságot jelenti, míg a II csoportbeli élek

esetén az eddig ismert minimális távolságot. Ez a megoldás hatékonyabb, mint a L.RFord-féle megoldás, abból a szempontból, hogy nem kell az összes élről egyidejűleg eltárolni az adatokat, elegendő csupán az I. és a II csoportbeli élek adatait 27 http://www.doksihu 4. Az algoritmusok tudnunk, és ez a szám mindig kevesebb, mint n. Ezen kívül a futási ideje is lényegesen kevesebb (E.WDijkstra, 1959) 4.3 Egy adott csúcsba érkező legrövidebb utak Ennek a problémának a megoldása nagyon egyszerű: csupán annyi a teendőnk hogy megfordítjuk a gráfunk irányítását. Ezáltal visszavezetjük a feladatot az egy csúcsból kiinduló legrövidebb utak kérdésére, amely megoldásának módszereit már fentebb, a 4.1 fejezetben taglaltuk 4.4 Legrövidebb utak minden csúcspárra Ebben a fejezetben célunk, hogy egy gráf valamennyi rendezett csúcspárjára a két csúcs közötti legrövidebb út megkeresése. Ha például egy autóstérképhez

elkészítjük a városok egymástól vett távolságainak táblázatát, akkor éppen ezt a problémát oldjuk meg. Természetesen a 4.1-es fejezetben bemutatott algoritmusok itt is használhatók, ha minden csúcsra lefutatjuk őket, amennyiben a távolságok nem negatívak, akkor a Dijkstra eljárást, ha vannak negatív élek, akkor a kicsit költségesebb BellmanFord módszert. Vannak azonban ennél következetesebb módszerek is 4.41 Floyd algoritmusa Ez az algoritmus abban az esetben oldja meg az összes csúcspár közötti legrövidebb utak problémáját, ha a bemenő gráfban nincsenek negatív körök (negatív élek lehetnek). 4.411 Robert W Floyd 15. ábra: Robert W Floyd Robert W. Floyd (1936 június 8 – 2001 szeptember 25) egy kivételesen tehetséges informatikus volt. New Yorkban született, 14 évesen már maga mögött 28 http://www.doksihu 4. Az algoritmusok tudta a középiskolát és 17 évesen, 1953-ban a chichagoi egyetemen BA diplomát szerzett

bölcsész szakon, majd 1958-ban pszichológiából. Az 1960-as évek elején kezdett el operátorként dolgozni, számos érdekes cikket publikált, mígnem 27 éves korában a Caregie Mellon Egyetemen helyettes professzornak ki nem nevezték. 6 évvel később, miután megszerezte a PhD címet a Stanford Egyetem professzora lett. Floyd Donald Knuth közeli munkatársa volt, és mint bíráló segített neki elkészíteni könyvét: The Art of Computer Programming, emiatt Donald nagy hatással volt Floyd munkásságára. 1994-ben Richard Beigellel elkészítették a The Language of Machines: an Introduction to Computability and Formal Languages című tankönyvüket. 1978-ban kapta meg a Turing-díjat az informatika számos területén elért eredményéért, különösen a formális nyelvek témakörében alkotottakért. Floyd élete során kétszer házasodott meg, és kétszer is vált el, négy gyermeke volt. Hobbijai a túrázás és a „backgammon”1 voltak (Wikipedia, 2009)

4.412 Az algoritmus Tegyük fel, hogy a G  (V , E ) gráf K adjacencia mátrixszal van megadva. A pontpárok távolságának kiszámítására egy szintén n  n -es F mátrixot fogunk használni. Kezdetben F i, j  : K i, j  Ezután egy ciklust hajtunk végre, amelynek k -adik lefutása után F i, j  azon i ↝ j utak legrövidebbjeinek a hosszát tartalmazza, amelyek közbülső pontjai k -nál nagyobb sorszámúak. Az új Fk i, j  értékeket a következőképpen számíthatjuk ki a k  1 -edik iteráció utáni Fk 1 i, j  értékekből (itt az index az F különböző pillanatnyi értékeire utal). Nyilván egy legrövidebb i ↝ j út, amelyen a közbülső pontok sorszáma legfeljebb k (természetesen a kezdő- és végpontok nem számítanak közbülső pontnak), vagy tartalmazza a k csúcsot vagy nem. - Ha k nincs rajta az i ↝ j úton, akkor Fk 1 i, j  . - Ha rajta van a k csúcs az i ↝ j úton, akkor A backgammon

egy két személyes társasjáték, ahol a korongokat a dobókocka dobások alapján kell mozgatni. 1 29 http://www.doksihu 4. Az algoritmusok  amennyiben ennek a csúcsnak a használatával előálló út rövidebb, mint az eddig ismert út, akkor ennek az új útnak a hosszát írjuk be Fk i, j  -be, ha hosszabb, akkor a régi út hosszát, vagyis Fk 1 i, j  -t,  ha több út is vezet az adott csúcson keresztül, akkor értelemszerűen a rövidebb értékét írjuk bele Fk i, j  -be. FLOYD ELJÁRÁS (G, k ) 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. procedure Floyd begin for minden i V csúcsra do begin for minden j V csúcsra do F i, j  : K i, j  end end P i, j  : 0 begin for minden k V csúcsra do begin for minden i V csúcsra do begin for minden j V csúcsra do 16. F i, j  : min F i, j  , F i, k   F k , j  17. if F i, j  értéke csökken then 18.

19. 20. 21. P i, j   k end end end 4.413 Az utak nyomon követése és a futási idő A kód magában rejti az utak nyomon követésének módszerét, ami futási időt nem befolyásolja. A 9 sorban definiálunk egy P   tömböt, amelybe akkor tesszük be a k csúcsot, ha a F i, j  érték megváltozik (17-18. sorok) Tehát P i, j  egy legrövidebb i ↝ j út „középső” csúcsát fogja tartalmazni. Ezek alapján az i ↝ j út összeállításához találnunk kell egy i -ből ebbe a „közbülső” csúcsba vezető legrövidebb utat, és egy ebből a csúcsból j -be vezető legrövidebb utat. De ezen utaknak is ismerjük egy-egy „középső” csúcsát, és így tovább. 30 http://www.doksihu 4. Az algoritmusok Az algoritmus lépésszáma n3 -bel arányos, hiszen a domináló rész három egymásba ágyazott for ciklus. Mondhatnánk, hogy ez nagyságrendben ugyanannyi, mintha a Dijkstra mátrixos változata, de pontosabb elemzéssel

kiderül, hogy a Floyd-módszer 50%-kal gyorsabb. Ha a gráf éleinek száma jóval kisebb, mint n 2 , és az élsúlyok nemnegatívak, akkor viszont érdemesebb a Dijkstra-algoritmus éllistás változatát használni. 4.414 Az eljárás működése egy példán keresztül 16. ábra: Példagráf a Floyd-eljárás működésének szemléltetéséhez  0   F0       2  1  0 1  0    2   4 0 1   3    0   0   F1       2  1  0 1  0   1 2  0   F2       2  1 0 0 1  0   1 2 3  4 0 1   3    0   0   F3  F4       2   0   5 F5       2  1 0 0 1  0   1 2 3 4 4 0 1 2  3    0    4 0 1 1 0 0 1  0   1 2   3

   0  3 5 4 0 1 2  3    0  Az F3 és az F4 egyenlősége abból ered, hogy a 4. csúcsból nem indul ki él, így az nem lehet közbülső csúcs. 31 http://www.doksihu 4. Az algoritmusok 4.42 Warshall algoritmusa Ez az algoritmus a fent említett Floyd algoritmusnál idősebb, de a módszer lényegében ugyanaz. A szakirodalomban gyakran a hasonlóság miatt egybe vonják a két algoritmust és Floyd-Warshall néven tüntetik fel. A különbség köztük az, hogy ez az algoritmus „csak” azt mondja meg, hogy mely pontok között megy irányított út, a hosszukat már nem adja meg. 4.421 Stephen Warshall Stephen Warshall 1935-ben született New York-ban. Karrierje során sok kutatást végzett az operációs rendszerek területén, a programozási nyelvek fejlesztésénél és sok más informatikai témakörben. Warshall a brooklyni általános iskolába járt, a Mount Vernon (New York) középiskolában érettségizett,

majd a Harward egyetemen szerezte meg a Bsc diplomáját matematikából 1956-ban. Magasabb végzettséget nem szerezett, ennek ellenére különböző egyetemeken (köztük francia iskolákban is) tartott előadásokat, ezzel is elősegítve az informatika és a szoftverfejlesztés fejlődését. Miután megszerezte a Bsc diplomáját, az ORO-nál (Operation Research Office) helyezkedett el. John Hopkins által létrehozott program keretein belül végzett kutatásokat az amerikai hadseregnek. 1958-ban eljött innen és egy Technical Operations nevű vállalkozásnál vállalt munkát, a munkája hasonló volt az előzőhöz: katonai szoftverek fejlesztése. 1961-ben a massachusettsi Informatikai Egyesület tagja lett, később ez az egyesület egybeolvadt az Apllied Data Research (ADR) céggel. Ekkor Warshall vezetői kitüntetést kapott és felügyelte a projecteket és szervezeteket. 1982-ben vonult nyugdíjba, végül 2006 december 11-én halt meg rákban. (Wikipedia, 2009) 4.422

Az algoritmus Mielőtt az eljárás lépéseire térnénk definiálni kell a tranzitív lezárt fogalmát. Definíció (tranzitív lezárt): Legyen G=(V,E) egy irányított gráf, A az adjacencia mátrixa. Legyen továbbá T a következő n  n -es mátrix: 1 T i, j    0 ha i-ből j elérhető irányított úttal különben. 32 http://www.doksihu 4. Az algoritmusok Ekkor a T mátrixot – illetve az általa meghatározott gráfot – az A mátrix – illetve az általa meghatározott G gráf – tranzitív lezártjának nevezzük. A fent részletezett Floyd-eljárásban csupán néhány változtatást kell tenni. A 6 sorban a kezdőértékek beállítása helyett: ha i=j vagy Ai, j   1 , 1 T i, j    0 különben. A 16. sorban F értékeinek változása helyett: T i, j   T i, j   T i, k   T  k , j  , valamint a 17. sorban nem az F értékeinek csökkenése esetén tesszük bele a k csúcsot a

P tömbbe, hanem amikor a T i, j  érték változik meg. Nyilvánvalóan a futási idő változatlan marad: O  n3  , és az utak nyomon követése is megegyezik a Floyd algoritmusnál leírtakkal. Tekintsük az alábbi példát a működésére: 17. ábra: Példagráf a Warshall-algoritmus működésének bemutatásához T (0) 1  0  1  0 0  1 1 0 0 0 0 1 1 0 0 0 0 1 1 1 1  0 0  0 1  T (2) 1  0  1  0 0  1 1 1 0 0 1 1 1 0 0 1 0 1 1 1 1  1 1  0 1  T (1) 1  0  1  0 0  1 1 1 0 0 0 1 1 0 0 T (3)  T (4)  T (5) 33 0 0 1 1 1 1  1  1  0 0  1  0 1  0 1  1 1 1 0 0 1 1 1 0 0 1 1 1 1 1 1  1 1  0 1  http://www.doksihu 4. Az algoritmusok A T (3)  T (4) azért igaz, mert a 4 csúcsból nem indul ki él, így az nem lehet közbülső csúcs. T (5)

egyenlősége az előző kettőhöz „látszólagos”, a T (5) 1, 4 értéknél szemmel nem látható változás történt. Ugyanis az 1 csúcsból megy él a 2 és a 3-as csúcson keresztül ezt jelzi, hogy T (2) 1, 4  T (3) 1, 4  1 , de az 5. csúcson keresztül is vezet egy másik út, így a T i, j   T i, j   T i, k   T  k , j  képlet alapján mindegy, hogy melyiket választjuk ki. 4.43 Johnson algoritmusa Johnson módszerével az összes csúcspár közti legrövidebb utakat O(n2 lg n  ne) időben találhatjuk meg, tehát ritka gráfokon ez lényegesen gyorsabb, mint az eddig ismert módszerek. Johnson eljárásának megértéséhez szükségünk van a Dijkstra- és a BellmanFord algoritmusok pontos ismeretére, mert az eljárás magában foglalja ezeket. A Johnson algoritmus (hasonlóan a Bellman-Fordhoz) HAMIS értéket ad vissza, ha a gráf tartalmaz negatív kört. A módszer alapötlete a

következő átsúlyozó technika. Amennyiben a gráfban nincsenek negatív élek, akkor a természetesen használhatjuk a Dijkstraalgoritmust minden csúcsra, mint forrásra. Ahhoz hogy a fenti futási időt elérjük Fibonacci-kupacokat kell alkalmaznunk. Definíció (Fibonacci-kupac): A bináris kupacokkal ellentétben a Fibonaccikupacban levő fák nem rendezettek. Minden x csúcsnak van egy p  x  pointere (mutató) a szülőjére, és egy gyerek  x  pointere az egyik gyerekére. Az x csúcs gyerekei egy kétirányú ciklikus listával vannak összekapcsolva, ezt a listát az x gyerek listájának nevezik. A gyerekek sorrendje a gyerek listában tetszőleges Ebben az adatszerkezetben a műveletek gyorsabban elvégezhetők a pointerek miatt. Ha vannak negatív éleink, akkor a következőképpen kell eljárnunk: olyan új k̂ nemnegatív értékeket kell találnunk, melyeken azután az előző megoldás alkalmazható. A k̂ súlyoknak a következő két feltételnek

kell eleget tenniük: 34 http://www.doksihu 4. Az algoritmusok a) Minden u, v V csúcspárra a k súlyozás szerint vett bármely legrövidebb u -ból v -be menő út a k̂ szerint is az. b) Minden (u, v)  E élre az új kˆ(u, v) súly nemnegatív. Az a) tulajdonságnak eleget tevő átsúlyozást az alábbi lemma alapján igen egyszerű elkészíteni. Lemma (átsúlyozás): Legyen h : V  ℝ tetszőleges valós értékű függvény egy G  (V , E ) irányított gráf csúcsain. Legyen k : E  ℝ ugyanennek a gráfnak az élsúlyozása. Minden (u, v)  E élre legyen kˆ(u, v)  k (u, v)  h(u)  h(v) Ekkor 1. minden v0 , vk csúcspárra és minden p  v0 , v1 ,, vk útra pontosan akkor lesz k ( p)  d (v0 , vk ) , ha kˆ( p)  dˆ (v0 , vk ) , ahol dˆ (v0 , vk ) a k̂ súlyozással keletkező út súlya; 2. továbbá pontosan akkor van a G gráfban negatív kör a k súlyozás szerint, ha k̂ súlyozás szerint is van. Bizonyítás: 1. Először

belátjuk, hogy kˆ( p)  k ( p)  h(v0 )  h(vk ) A kˆ( p) súly a következő teleszkópos összeggé alakítható: k k i 1 i 1 kˆ( p)   kˆ(vi 1 , vi )   (k (vi 1 , vi )  h(vi )  h(vi 1 ))  k k k i 1 i 1 i 1   k (vi 1 , vi )   h(vi )   h(vi 1 )  k ( p)  h(v0 )  h(vk ). Tegyük fel, hogy a k̂ súlyozással valamely v0 , vk csúcspár között találtunk egy p utat, amely rövidebb, mint a k súlyozás esetén kialakult p út. Alkalmazzunk a p és p utakra a fenti kˆ( p)  k ( p)  h(v0 )  h(vk ) egyenlőséget: k ( p )  h(v0 )  h(vk )  kˆ( p )  kˆ( p)  k ( p)  h(v0 )  h(vk ) , amelyből k ( p )  k ( p) következik. Ez azonban ellentmond annak a feltevésnek, hogy p a legrövidebb út v0 és vk csúcsok között. 35 http://www.doksihu 4. Az algoritmusok 2. Legyen c  v0 , v1 ,, vk egy tetszőleges kör a k súlyozás szerint, ahol v0  vk .

Ekkor a kˆ( p)  k ( p)  h(v0 )  h(vk ) egyenlőség szerint: kˆ(c)  k (c)  h(v0 )  h(vk ) , így a c súlya pontosan akkor negatív a k súlyozás szerint, ha k̂ szerint is az.∎ A b) feltételnek eleget tevő nemnegatív értékű átsúlyozás pedig a következőképpen zajlik: 1. A G  (V , E ) irányított gráfot egészítsük ki egy s V csúccsal egy G  (V , E ) gráffá, ahol tehát V  V  s és E  E  (s, v) : v V  . A k súlyozást terjesszük ki G éleire úgy, hogy k (s, v)  0 minden v V esetén. Fontos megjegyezni, hogy s -be él nem lép, ezért nem haladhat át rajta kör, ezáltal ha van kör, akkor az csak G -ben lehet. Valamint ugyanebből az okból kifolyólag csak G -beli legrövidebb utak tartalmazzák s -t. 2. Tegyük fel, hogy nincsen negatív kör a gráfban Legyen h(v)  d (s, v) minden v V csúcsra. Ekkor a korábban látottak alapján h(v)  h(u)  k (u, v) fennáll minden (u, v)

 E élre. Ha tehát az új k̂ súlyozást a kˆ(u, v)  k (u, v)  h(u)  h(v) egyenlet szerint végezzük, kˆ(u, v)  k (u, v)  h(u)  h(v)  0 , akkor a nemnegativitást megkövetelő tulajdonság teljesül. (Thomas H. Cormen, Charles E Leiserson, Ronald L Rivest, 2001) 4.431 Az eljárás lépései 1. Felvesszük az s csúcsot, és kiegészítjük a gráfot az új élekkel (megkapjuk G -t). 2. A Bellman-Ford algoritmus segítségével megvizsgáljuk, hogy van-e negatív kör a G gráfban, ha igen akkor az algoritmus ezen a ponton megáll. 3. Ha nincsen negatív kör a gráfban, akkor a Bellman-Ford által kapott d ( s, vi ) értékekkel feltöltjük a G gráf csúcsait (vagyis: h(vi )  d (s, vi ) ). 4. Átsúlyozzuk G éleit a kˆ(u, v)  k (u, v)  h(u)  h(v) szabály szerint 5. Az így kapott átsúlyozott (már csak nemnegatív élet tartalmazó) G gráf minden csúcsára (mint forrásra) végrehajtjuk a Dijkstra algoritmust. 36

http://www.doksihu 4. Az algoritmusok 18. ábra: A Johnson algoritmus működése (a) Az s csúccsal és az új (szürkével jelzett) élekkel kiegészített gráf, valamint a Bellman-Ford eljárás által kapott értékekkel feltöltött csúcsok. (b) Az élek átsúlyozása (c)-(f) A Dijkstra-algoritmus segítségével kapott legrövidebb utak, a szürkével jelzett csúcsok az aktuális források. A csúcsokban szereplő /-jellel elválasztva dˆ (u, v) és d (u, v) áll. 4.432 Futási idő Mint ahogy már fentebb említettük, ha Fibonacci-kupacot használunk, akkor O(n2 lg n  ne) lesz a futási idő. Egyszerű bináris kupac alkalmazása esetén O(ne lg n) . 37 http://www.doksihu 5. A matematikában kevésbé ismert módszerek 5 A matematikában kevésbé ismert módszerek Ez a fejezet a matematika számára már kevésbé ismert módszerek közül kettőt hivatott bemutatni. Ezeket az eljárásokat a modern kor egyik új területe a mesterséges intelligencia (MI)

tudománya alkalmazza. Hogy mi is az MI? Ahány ember, annyi válasz: „Izgalmas újszerű kísérlet, hogy a számítógépet gondolkodásra késztessüktudatos gépek, e fogalom teljes és szó szerinti értelmében” (Haugeland, 1985) „Az MI a műtárgyak intelligens viselkedésével foglalkozik” (Nilsson, 1998) Az eddig megismert eljárásokkal ellentétben itt nem az élek, hanem az csúcsok vannak súlyozva a céltól függően. 5.1 Informált keresési stratégiák Az általunk vizsgált általános megközelítést a legjobbat-először keresésnek nevezzük. A módszer alapötlete, hogy a gráfunk azon csúcsa felé indulunk el, amelynek az értéke a legkisebb. A csúcsok értékét egy ún kiértékelő függvény f ( n) segítségével kapjuk. A LEGJOBBAT-ELŐSZÖR-KERESÉS algoritmus tulajdonképpen egy keresési algoritmus család, amelynek elemeit az eltérő kiértékelő függvények különböztetik meg. Ezeknek az algoritmusoknak a kulcseleme a h(n) -nel

jelölt heurisztikus függvény. Definíció (heurisztikus függvény): Az n csomóponttól a célig vezető legolcsóbb út becsült útköltsége. Egy egyszerű példa az ilyen heurisztikus függvényre: a városok közötti légvonalban mért távolság, melyet mindig a célvárostól számolunk. Például ha Aradról akarunk Bukarestbe eljutni, akkor a közbülső városok súlyait a Bukaresttől mért távolságuk fogja adni. 5.11 A mohó legjobbat-először keresés A mohó legjobbat először keresés annak a csúcsnak az irányába indul el, amelyiket a legközelebbinek ítéli meg a célállapothoz, tehát ebben az esetben a kiértékelő- és a heurisztikus függvényünk megegyezik ( f (n)  h(n) ). 38 http://www.doksihu 5. A matematikában kevésbé ismert módszerek Nézzük meg, hogy hogyan is működik az előbb említett romániai útkeresés esetében. 19. ábra: A mohó legjobbat először keresés lépései Bukarest esetén a légvonalban mért távolságot

– mint heurisztikát – alkalmazva. Ebben a konkrét példában a mohó legjobbat-először keresés úgy talál megoldást, hogy soha nem megy olyan pont felé, amely nem a megoldási (legrövidebb) úton fekszik, következésképpen minimális a költsége. Azonban nem optimális: vegyük szemügyre az alábbi táblázatot, amely a légvonalbeli távolságokat tartalmazza Bukarestig. Távolság Város Távolság 366 Mehadia 241 Bukarest 0 Neamt 234 Craiova 160 Nagyvárad 380 Dobreta 242 Pitesti 100 Eforie 161 Rimnicu Vilcea 193 Fogaras 176 Nagyszeben 253 Giurgiu 77 Temesvár 329 Hirsova 151 Csalános 80 Iasi 226 Vaslui 199 Lugos 244 Nagyszerénd 374 Rögtön észrevesszük, hogy a fent kapott Arad - Nagyszeben – Fogaras – Arad Város Bukarest útvonal 32 kilométerrel hosszabb, mint a Arad - Nagyszeben – Rimnicu Vilcea – Pitesti Bukarest útvonal. Az eljárás egyetlen út végigkövetését preferálja a célig, ha zsákutcába kerül, visszalép. Két nagy

problémája van: nem optimális (például a fenti esetben sem) és 39 http://www.doksihu 5. A matematikában kevésbé ismert módszerek nem teljes (mert elindulhat egy végtelen úton, és így soha sem fog visszalépni más lehetőségeket kipróbálni). A legrosszabb esetre számított idő-és tárigénye O(bm ) , ahol m a gráf mélységét jelöli, a b pedig az egy csúcsból kiinduló élek átlagos száma. (Stuart Russell, Peter Norvig, 2005) 5.12 Az A* algoritmus A legjobbat-először keresés leginkább ismert változata, amelyet Bertram Raphael, Nils Nilsson és Peter Hart alkotott meg 1968-ban. 5.121 Bertram Raphael, Nils Nilsson, Peter Hart 20. ábra: Nils Nilsson, Peter Hart, Bertram Raphael Nils Nilsson az MI tudomáynának egyik alapítója. A mérnőki tudományok professzora, a stanfordi egyetem nyugalmazott testületi tagja. Hírnevét a kutatás, a tervezés a robotika területén elért sikerei hozták meg. A stanfordi egyetemen szerezte meg a PhD titulust

1958-ban, majd karrierjének nagy részét az SRI-nél építette. 1985-ben a stanfordi egyetem a tantestületébe választja, és 1990-ig nyugdíjazásáig itt is marad. 1982 és 1983 között negyedikként elfoglalhatta az AAAI elnöki székét. Nilsson számos az MI témakörébe tartozó könyvet írt és lektorált. (Wikipedia, 2008) Peter Hart az 1940-es években született, informatikus és vállalkozó. A Msc diplomáját és a Ph.D címét a stanfordi egyetemen szerezte meg Az 1997-ben az általa alapított Ricoh Vállalkozás elnöke volt. Alapvető eredményeket ért el az MI területén. 1967 és 1975 között az SRI Nemzetközi laboratóriumban a Mesterséges Intelligencia részlegen dolgozott igazgatóként, és ezalatt számos publikációja jelent meg az informatika ezen területéről. (Wikipedia, 2009) Bertram Raphael 1936-ban született és az MI terén elért eredményeiért híres. A Bsc diplomáját fizikából a rensselaeri műszaki egyetemen szerezte meg

1957ben, a Ph.D címet pedig az MIT-n 1964-ben (Wikipedia, 2008) 40 http://www.doksihu 5. A matematikában kevésbé ismert módszerek 5.122 Az eljárás Ebben az eljárásban a kiértékelő függvényünk a heurisztikus függvény és az aktuális csúcsig megtett út költségének ( g ( n) ) kombinációja. Tehát f (n)  g (n)  h(n) . Átfogalmazva f (n)  a legolcsóbb, az n csúcson keresztül vezető megoldás becsült költsége. Az A* optimalitását könnyű elemezni, ha h(n) egy elfogadható heurisztika. Definíció (elfogadható heurisztika): h(n) soha nem becsüli felül a cél eléréséhez szükséges költséget. Ennek a feltételnek a légvonalban mért távolság, mint heurisztikus függvény eleget tesz, hiszen e távolság bármely két pont között a legrövidebb. Állítás: Az A* optimális, ha h(n) elfogadható heurisztika. Bizonyítás: Indirekten tegyük fel, hogy az eljárás során eljutottunk egy olyan célcsúcsba melynek az értéke

szuboptimális (nem megfelelő). Jelöljük ezt a csúcsot G -vel. Legyen az optimális megoldás költsége C * . Mivel G szuboptimális és h(G)  0 (ez minden célcsúcsra igaz), tudjuk, hogy: f (G)  g (G)  h(G)  g (G)  C * . Tekintsünk most egy A csúcsot, amely a megoldási útvonalon van (ilyennek léteznie kell, ha a megoldás létezik). Mivel h(n) heurisztikus, vagyis nem becsüli túl, tehát tudjuk, hogy: f ( A)  g ( A)  h( A)  C * . Ezek alapján f ( A)  C*  f (G) , tehát G nem kerülhet kifejtésre. Ellentmondásba ütköztünk, vagyis az A* optimális megoldással fog visszatérni.∎ (Stuart Russell, Peter Norvig, 2005) Ez a bizonyítás azonban néhány esetben nem helytálló. Ezen esetek kifejtése viszont komoly és igen szerteágazó informatikai ismereteket igényel, így mellőzzük is őket. 41 http://www.doksihu 5. A matematikában kevésbé ismert módszerek Az alábbi ábrák illusztrálják az eljárás fázisait. 21.

ábra: Az A* algoritmus lépései. A csomópontok az f  g  h értékeivel vannak felcímkézve Az első lépésben Nagyszebent választja az algoritmus, majd Rimnicu Vilcea-t, de itt miután összehasonlítja a Rimnicu Vilcea-ból elérhető csúcsok értékeit visszalép és Fogaras csúcsot fogja választani (mivel annak a legkisebb az értéke). A további lépéseket a következő 22. ábra szemlélteti 22. ábra: A Fogarasból feldolgozott minden csúcs értéke nagyobb, mint a Rimnicu Vilcea-ból elérhető Pitesti, így az eljárás a következő lépésben ezt a csúcsot választja. Ezután pedig megérkezik Bukarestbe, és jól látható, hogy a mohó legjobbat-először algoritmushoz képest 32 kilométert javított. Az eljárás egyik nagy hibája a hatalmas memóriaigény, mivel a meglátogatott csúcsokat a memóriában tárolja. Ezért az A* algoritmus sok nagyméretű problémához nem praktikus. 42 http://www.doksihu 6. Összefoglalás 6 Összefoglalás A

szakdolgozat célja volt, hogy bemutassam és rávilágítsak a legrövidebb útkereső algoritmusok sokszínűségére, valamint arra, hogy szerteágazóan sok gyakorlati hasznuk van. A gráfelméletbeli alapfogalmak bemutatása után a probléma alesetei szerint csoportosított algoritmusok részletezése következett. Igyekeztem minél több ábrával és példával szemléltetni a folyamatok lépéseit, ezzel megkönnyíteni azok megértését. Végül a modern kor tudományában az informatikában kialakult változatai közül és kettőt bemutattam. Az életrajzok és idézetek célja volt a túlzottan száraz jelleg elkerülése mellet az általános tudás növelése, valamint az, hogy milyen más területen alkottak illetve a mai napig alkotnak ezek a zseniális elmék. Mielőtt elkezdem volna írni a szakdolgozatomat, ódzkodtam a témától. Annak idején mikor tanultam ezen algoritmusok némelyikét, nem láttam, hogy mennyi mindenre alkalmasak, milyen sok területen lehet

használni őket. Most, hogy a témát – véleményem szerint – alaposan megvizsgáltam és kielemeztem, állíthatom, hogy fejlődő világunknak igenis nagy szüksége van ezekre a fantasztikus matematikai és informatikai megállapításokra. 43 http://www.doksihu 7. <Irodalomjegyzék 7 Irodalomjegyzék E.WDijkstra (1959) Numerische Mathematik Haugeland. (1985) Artificial Intelligence: The very idea Cambridge: MIT Press Nilsson, N. (1998) Artifical Intelligence: A new synthesis San Mateo: Morgan Kaufmann. Singh Nayandeep. (2001 január 10) Yahoo Letöltés dátuma: 2009 március 3, forrás: L. R Ford: http://wwwgeocitiescom/nayan vt/lester randolph ford1htm Stuart Russell, Peter Norvig. (2005) Mesterséges Intelligencia Budapest: Panem. Thomas H. Cormen, Charles E Leiserson, Ronald L Rivest (2001) Algoritmusok. Műszaki Könyvkiadó Wikipedia. (2007 november 23) Letöltés dátuma: 2009 március 3, forrás: http://www.thocpnet/biographies/dijkstra edsgerhtm Wikipedia.

(2008 november 24) Letöltés dátuma: 2009 máecius 15, forrás: http://en.wikipediaorg/wiki/Nils Nilsson Wikipedia. (2008 november 4) Letöltés dátuma: 2009 március 15, forrás: http://en.wikipediaorg/wiki/Bertram Raphael Wikipedia. (2009 január 28) Letöltés dátuma: 2009 március 11, forrás: http://en.wikipediaorg/wiki/Robert W Floyd Wikipedia. (2009 január 31) Letöltés dátuma: 2009 március 11, forrás: http://en.wikipediaorg/wiki/Stephen Warshall Wikipedia. (2009 február 14) Letöltés dátuma: 2009 március 09, forrás: http://en.wikipediaorg/wiki/Richard Bellman Wikipedia. (2009 január 27) Letöltés dátuma: 2009 március 15, forrás: http://en.wikipediaorg/wiki/Peter E Hart 44 http://www.doksihu 8. Köszönetnyilvánítás 8 Köszönetnyilvánítás Végezetül szeretnék köszönetet mondani mindazoknak, akik munkámat segítették. Külön köszönet Nagy Adriennek, aki bokros teendői mellett, nem kevés segítséget és figyelmet szentelt nekem.

Köszönöm továbbá Podobni Dóra és Kocsis Olivér támogatását, hasznos tanácsait és segítségét. 45