Bellman-Ford algoritmus

Ez a cikk egy vázlatot kapcsolatos elméleti számítógép-tudomány .

Megoszthatja ismereteit fejlesztésével ( hogyan? ) A megfelelő projektek ajánlásai szerint .

Felfedezők vagy feltalálók	Richard Bellman (1958), LR Ford Jr. (1956), Edward F. Moore (1957)
Kapcsolódó kérdések	Útkeresési algoritmus ( d ) , gráfelméleti algoritmus ( d ) , matematikai koncepció ( d )
Adatszerkezet	Grafikon
Kezdetekor	Routing Information Protocol

Az idő összetettsége

Legrosszabb esetben	${\ displaystyle \ Theta (\| V \|\| E \|)}$
Legjobb eset	${\ displaystyle \ Theta (\| E \|)}$

A tér összetettsége

Legrosszabb esetben	${\ displaystyle \ Theta (\| V \|)}$

A Bellman-Ford algoritmus , más néven Bellman - Ford - Moore algoritmus , olyan algoritmus , amely egy adott forráscsúcsból a legrövidebb utakat számítja ki egy súlyozott irányított gráfban . Feltalálói, Richard Bellman és Lester Randolph Ford junior (megjelent 1956-ban és 1958-ban), valamint Edward Forrest Moore nevét viseli , aki 1959-ben fedezte fel újra.

Dijkstra algoritmusától eltérően a Bellman-Ford algoritmus lehetővé teszi bizonyos negatív súlyú ívek jelenlétét, és lehetővé teszi az abszorpciós áramkör , vagyis a szigorúan negatív össztömeg létezésének detektálását , amely elérhető a forráscsúcsról.

Az algoritmus bonyolultsága az, ahol a csúcsok száma az ívek száma. ${\ displaystyle O (| S || A |)}$ $| S |$ ${\ displaystyle | A |}$

Leírás

A Bellman-Ford algoritmus egy negatív súlyciklus nélküli gráf és egy forráscsúcs alapján kiszámítja a legrövidebb utat az egyes csúcsokhoz . Lehetővé teszi egy ilyen út megtalálását is azáltal, hogy az egyes csúcsok elődjeit visszaküldi egy ilyen útra. Ezenkívül lehetővé teszi azoknak az eseteknek a felderítését, amikor negatív súlyú ciklus van, és ezért nem feltétlenül van rövidebb út két csúcs között. $G = (S, A)$ $s \ -ban S$ $s$ $G$

Az algoritmus a dinamikus programozás elvét használja (egyes algoritmikus könyvekben a dinamikus programozásról szóló fejezet foglalkozik vele). Az alproblémák a következők:

${\ displaystyle d [t, k]}$ az a s csúcs s távolsága a t-hez, amelynek útja legfeljebb k ívet tartalmaz.

Nekünk van :

${\ displaystyle d [t, 0] = + \ infty}$ A és ; ${\ displaystyle t \ neq s}$ ${\ displaystyle d [s, 0] = 0}$
${\ displaystyle d [t, k] = min \ bal [d [t, k-1], min _ {{\ text {arc}} (u, t)} (d [u, k-1] + súly (u, t)) \ jobbra]}$ .

Az algoritmus az értékeket k értékének növelésével számítja ki . Az s és t közötti távolság . ${\ displaystyle d [t, k]}$ ${\ displaystyle d [t, | S | -1]}$

Álkód

A Bellman-Ford algoritmust tehát közvetlenül az előző szakaszban megadott megismétlődési reláció felhasználásával írjuk meg.

Végén a végrehajtás ezen algoritmus, a hosszát jelenti rövidebb utat , hogy az , mivel képviseli az elődje egy rövidebb utat az . A null érték azt jelenti, hogy még nem rendeltek elődöt . ${\ displaystyle d [u]}$ $s$ $u$ $G$ ${\ displaystyle pred [u]}$ $u$ $s$ $u$ ${\ displaystyle pred [u]}$

A Bellman-Ford algoritmus csak egy negatív súlyciklus nélküli grafikonon helyes. Egy ilyen ciklus jelenléte a következőképpen detektálható (feltéve, hogy felülről elérhető ): csak akkor van negatív súlyciklus, ha a hurok új köre csökkenti a távolságot. Tehát az algoritmus végén: $s$

pour chaque arc (u, v) du graphe faire | si d[v] > d[u] + poids(u, v) alors | afficher "il existe un cycle absorbant"

Bonyolultság

Az algoritmus bonyolultsága ahol a csúcsok száma és az ívek száma. Ez a sűrű, egyszerű gráf összetettségének felel meg . ${\ displaystyle O (| S || A |)}$ $| S |$ ${\ displaystyle | A |}$ ${\ displaystyle O (| S | ^ {3})}$

A korrekció igazolása

Az algoritmus helyességének igazolása indukcióval történhet :

Lemma. A fő hurok megismétlése után : $én$

Ha , akkor a súlya egy útvonal a ; ${\ displaystyle d [u] \ neq + \ infty}$ ${\ displaystyle d [u]}$ $s$ $u$
Ha van egy út a , hogy a legfeljebb széleit, majd legfeljebb a hossza a legrövidebb utat a köztük legfeljebb élek. $s$ $u$ $én$ ${\ displaystyle d [u]}$ $s$ $u$ $én$

Bizonyíték. Abban az esetben, amely a hurok első végrehajtásának felel meg , akkor először is, és az egyes csúcsok esetében az első pont igazolására, másodsorban pedig ez az egyetlen olyan csúcs, amelyen legfeljebb "0 él van összekötve . $i = 0$ for ${\ displaystyle d [s] = 0}$ $u \ neq s$ ${\ displaystyle d [u] = + \ infty}$ $s$ $s$

Bármely nem nulla eset esetén : $én$

Tegyük fel egyrészt, hogy frissíteni kell a . Tehát, mint (mert különben a frissítés nem kerül sor), képviseli a tömeg egy utat , hogy . Így, az építőipar, a súlya egy útvonalat , hogy ; ${\ displaystyle d [v]}$ ${\ displaystyle d [v]: = d [u] + {\ text {weight}} (u, v)}$ ${\ displaystyle d [u] \ neq + \ infty}$ ${\ displaystyle d [u]}$ $s$ $u$ ${\ displaystyle d [v]}$ $s$ $v$
Másrészt, vagyis egy rövidebb utat , hogy legfeljebb élek. Vagy az utolsó csúcs ezen az úton. Hagy az al-útját haladva a . Aztán indukció útján egy rövidebb utat , hogy legfeljebb élek (sőt, egyébként létezik egy szigorúan rövidebb utat kell . Azáltal, hogy a széle a találunk egy utat szigorúan rövidebb haladva az , ami ellentétes a meghatározása ). Így, indukciós hipotézis, a végén az iteráció , volt a legtöbb a hossza a legrövidebb út a , hogy a legtöbb élek. Így a -edik iterációnál ,, az algoritmus felépítése miatt. Azonban ez utóbbi hossza legfeljebb hossza rövidebb utat kell . $VS$ $s$ $v$ $én$ $u$ $v$ $VS ”$ $VS$ $s$ $u$ $VS ”$ $s$ $u$ ${\ displaystyle i-1}$ $s$ $u$ $u$ $v$ $VS$ $s$ $v$ $VS$ ${\ displaystyle i-1}$ ${\ displaystyle d [u]}$ $s$ $u$ ${\ displaystyle i-1}$ $én$ ${\ displaystyle d [v] \ leq d [u] + {\ text {weight}} (u, v)}$ $s$ $v$

A lemma tehát bebizonyosodott. Ebből következik, hogy a hossz egy rövidebb út hossza a- tól , ami bizonyítja a Bellman-Ford algoritmus helyességét abban az esetben, ha nincs negatív súlyciklusa. ${\ displaystyle d [u]}$ $s$ $u$ $G$

Fejlesztések

A fő hurok végrehajtása megállítható, ha a távolságok változatlanok. Ezután a fő hurok testét kevesebbszer hajtják végre . A legrosszabb eset összetettsége változatlan. Yen két olyan fejlesztést írt le a Bellman-Ford algoritmusban, amelyek a legrosszabb esetben sem változtatják meg a bonyolultságot, de a gyakorlatban gyorsabbá teszik. ${\ displaystyle | S | -1}$

Az első fejlesztés csökkenti a relaxációk számát. Ha d [u] az ív (u, t) lazítása óta nem módosult, akkor nincs szükség az ívek (u, t) második kiadására. Tehát, ahogy az algoritmus során növekszik a megfelelő távolsággal rendelkező csúcsok száma, az egyes iterációk során csökken a felszabadítandó ívek száma. A sűrű gráfok komplexitására állandó tényezőt kapunk.
A Yen második fejlesztése abból áll, hogy tetszőleges teljes sorrendet választunk <a csúcsokon, majd az ívkészletet két disszjunkt részhalmazra osztjuk. Az első alcsoport E F tartalmazza az íveket (u, t) u <t és a második, E b , tartalmazza az íveket (u, t) u> t. A do gráf minden ívéhez (u, t) a hurok a következőképpen kerül végrehajtásra. Minden u csúcsot növekvő sorrendben látogatunk meg <. Ezután minden ívet (u, t) elengedünk E f-ben . Ezután csökkenő sorrendben meglátogatjuk az u csúcsokat>. Elengedjük az E b íveket (u, t) . Minden iteráció a fő hurok (kivéve az első) egészíti legalább két ív, amelynek csúcsai vannak a helyes távolságokat, egy E f és egy E b . Ez a javulás csökkenti az iterációk számát a fő hurok a . ${\ displaystyle | S | -1}$ ${\ displaystyle {\ frac {| S |} {2}}}$

A Bannister & Eppstein további javítása az, hogy a második Yen-javulás csúcsain lévő teljes sorrendet véletlenszerű permutációval helyettesíti. Így a Yen javulásának legrosszabb esete ritkán fordul elő (az a tény, hogy egy rövidebb út ívei néha E f-ben, néha pedig E b-ben vannak ). Véletlenszerű permutációval, mint teljes sorrenddel, a fő hurok iterációinak számára vonatkozó elvárás legfeljebb . ${\ displaystyle {\ frac {| S |} {3}}}$

1993-ban Bahar és mtsai. a Bellman-Ford algoritmus megvalósítását adta szimbolikusan ábrázolt grafikonokhoz az Algebrai Döntési Diagramok (ADD) nevű adatszerkezet felhasználásával , amely a bináris döntési diagramok általánosítása .

Használ

A számítógépes hálózatokban a Bellman-Ford algoritmust használják az üzenetek áramlásának meghatározására a RIP útválasztási protokollon keresztül . A Bellman-Ford algoritmust felhasználhatjuk egy lineáris programozási probléma megoldására, ahol a korlátok eltérések. Például: x - y ≤ 5, y - t ≤ 10 stb. Pontosabban, egy ilyen rendszernek akkor és csak akkor van megoldása, ha a társított grafikonnak nincsenek negatív súlyú ciklusai.

Megjegyzések és hivatkozások

Például: „A Bellman - Ford - Moore legrövidebb út algoritmusának optimalizálásáról” , Stasys Jukna és Georg Schnitger megjegyzése, Theoretical Computer Science 628 (2016) 101–109.
" Lecture Slides for Algorithm Design by Jon Kleinberg And Tardos Éva " , www.cs.princeton.edu, (hozzáférés : 2016. március 15. ) .
Thomas H. Cormen, Charles Leiserson, Ronald Rivest és Clifford Stein, Bevezetés az algoritmikába: leckék és gyakorlatok , Dunod ,2009, P. 24. fejezet: Hosszabb egy eredetű utak.
(in) "Bellman-Ford algoritmus" a Wikipedia ,1 st május 2021( online olvasás )
" MR: Matches for: MR = 253822 " , www.ams.org (megtekintve 2016. március 15-én ) .
Michael J. Bannister és David Eppstein , „ A Bellman-Ford algoritmus véletlenszerű felgyorsítása ”, az Analitikus Algoritmika és Kombinatorika Találkozója , Ipari és Alkalmazott Matematikai Társaság, aNALCO '12,1 st január 2012, P. 41–47 ( online olvasás , konzultáció 2016. március 15-én ).
R. Iris Bahar , Erica A. Frohm , Charles M. Gaona és Gary D. Hachtel , „ Algebrai döntési diagramok és alkalmazásuk ”, ICCAD '93 Az 1993-as IEEE / ACM nemzetközi konferencia anyagai a számítógéppel segített tervezésről , IEEE Computer Society Press,1993. november 7, P. 188-191 ( ISBN 0818644907 , olvasható online , elérhető 9 február 2018 )
(in) Megjegyzések iránti kérelem, n o 1058 .
Robert Shostak , " A lineáris egyenlőtlenségek eldöntése a hurokmaradványok kiszámításával ", J. ACM , vol. 28,1 st október 1981, P. 769–779 ( ISSN 0004-5411 , DOI 10.1145 / 322276.322288 , online olvasás , hozzáférés : 2016. április 22. ).

Bibliográfia

Eredeti források

(en) Richard Bellman , „ On a routing problem ” , Quarterly of Applied Mathematics , 1. évf. 16,1958, P. 87–90 ( matematikai vélemények 0102435 )
(en) Lester R. Ford Jr. , Network Flow Theory , Santa Monica, Kalifornia, RAND Corporation, koll. "P-923 papír",1956. augusztus 14( online olvasás )
(fr) Edward F. Moore (1959). „A legrövidebb út egy labirintuson keresztül” a Proc. Bentlakásos iskola. Szép. Switching Theory 1957, II . Rész : 285–292 p., Cambridge, Mass.: Harvard Univ. Nyomja meg.
(en) Jin Y. Yen , „ Algoritmus a legrövidebb útvonalak megtalálásához az összes forrás csomóponttól az adott célig az általános hálózatokban ” , Quarterly of Applied Mathematics , vol. 27,1970, P. 526–530 ( matematikai vélemények 0253822 )
(en) MJ Bannister és D. Eppstein (2012) „ A Bellman - Ford algoritmus véletlenszerű felgyorsítása ” (pdf) in Analytic Algorithmics and Combinatorics (ANALCO12), Kiotó, Japán : 41–47 p.

Francia könyvek

Michel Gondran és Michel Minoux , grafikonok és algoritmusok , Éditions Eyrolles , coll. "Franciaország villamos energia tanulmányai és kutatása",1979( újranyomás 1984, 1995, 2009 Lavoisiernél, 4. kiadás), 548 p. , "2 - A legrövidebb út probléma"

Lásd is

Dijkstra algoritmusa