Toshkent 2020 Reja: Algoritm

1-MUSTAQIL ISHI

MAVZU:

Bellman-Ford algorithm
Toshkent 2020

Reja:

1. Algoritm

2. To`g`ri ekanligini isbotlash

3. Salbiy tsikllarni topish

4. Yo`nalishdagi dasturlar

5. Yaxshilashlar

6. Izohlar

7. Adabiyotlar

7.1. Asl manbalar

7.2. Ikkilamchi manbalar

Kirish.

Bellman-Ford algoritmi - bu bitta manbali tepalikdan tortib tortilgan digraftdagi boshqa barcha tepaliklarga eng qisqa yo`llarni hisoblab chiquvchi. Xuddi shu muammo bo`yicha Dijkstra algoritmiga qaraganda sekinroq, ammo ko`p qirrali, chunki u ba`zi chekka og`irliklar salbiy sonlar bo`lgan grafikalar bilan ishlashga qodir. Algoritm birinchi bo`lib Alfonso Shimbel (1955) tomonidan taklif qilingan, ammo uning o`rniga 1958 va 1956 yillarda nashr etilgan Richard Bellman va kichik Lester Ford nomlari berilgan. Edvard F. Mur ham xuddi shu algoritmni 1957 yilda nashr etgan va shu sababli uni ba`zan Bellman-Ford-Mur algoritmi ham deyishadi. Salbiy qirrali og`irliklar grafiklarning turli xil ilovalarida uchraydi, shuning uchun bu algoritmning foydaliligi. Agar grafada manba orqali erishish mumkin bo`lgan "manfiy tsikl" (ya`ni chekkalari yig`ilib, manfiy qiymatga ega bo`lgan tsikl) bo`lsa, unda eng arzon yo`l yo`q: manfiy tsikldagi nuqtasi bo`lgan har qanday yo`lni arzonlashtirish mumkin salbiy tsikl atrofida yana bitta yurish. Bunday holatda Bellman-Ford algoritmi salbiy tsiklni aniqlay oladi va xabar beradi.

Dijkstra algoritmi singari, Bellman-Ford ham bo`shashishga to`g`ri keladi, bunda to`g`ri masofaga yaqinlashishlar oxirigacha yechim topguncha yaxshiroq bilan almashtiriladi. Ikkala algoritmda ham har bir cho`qqiga taxminiy masofa har doim haqiqiy masofani haddan tashqari oshirib yuboradi va uning dastlabki qiymati va yangi topilgan yo`l uzunligi minimal bilan almashtiriladi. Biroq, Dijkstra algoritmi hanuzgacha ishlov berilmagan eng yaqin cho`qqini ochko`zlik bilan tanlash uchun ustuvor navbatdan foydalanadi va bu bo`shashish jarayonini uning barcha chiquvchi qirralarida amalga oshiradi; Aksincha, Bellman-Ford algoritmi barcha qirralarni bo`shashtiradi va buni {\ displaystyle | V | -1} | V | -1 marta bajaradi, bu erda {\ displaystyle | V |} | V | bu grafadagi tepalar soni. Ushbu takrorlashlarning har birida to`g`ri hisoblangan masofalar bilan tepalar soni ko`payib boradi, shundan kelib chiqadiki, oxir-oqibat barcha tepaliklar o`zlarining to`g`ri masofalariga ega bo`lishadi. Ushbu usul Bellman-Ford algoritmini Dijkstra-ga qaraganda kengroq kirish sinfiga tatbiq etishga imkon beradi.

Oddiy qilib aytganda, algoritm manbaga bo`lgan masofani 0 ga va boshqa barcha tugunlarga cheksizgacha boshlaydi. Keyin barcha qirralar uchun, agar belgilangan joyga masofani chekkani olish bilan qisqartirish mumkin bo`lsa, masofa yangi pastki qiymatga yangilanadi. Har bir takrorlashda qirralarning skanerdan o`tkazilishida algoritm maksimal uzunlikdagi qirralarning barcha eng qisqa yo`llarini topadi (va, ehtimol, i qirralardan uzunroq yo`llar). Tsiklsiz mumkin bo`lgan eng uzun yo`l {\ displaystyle | V | -1} | V | -1 qirralar bo`lishi mumkinligi sababli, eng qisqa bo`lishini ta`minlash uchun qirralarni {\ displaystyle | V | -1} | V | -1 marta skanerlash kerak barcha tugunlar uchun yo`l topildi. Barcha qirralarning yakuniy skaneri amalga oshiriladi va agar biron bir masofa yangilansa, u holda uzunlik yo`li {\ displaystyle | V |} | V | qirralar topilgan, ular grafada kamida bitta salbiy tsikl mavjud bo`lganda yuzaga kelishi mumkin.
Algoritmning to`g`riligini induksiya orqali ko`rsatish mumkin: Lemma. For loopining takrorlanishidan so`ng, masofa (u) cheksiz bo`lmasa, u s dan u gacha bo`lgan yo`lning uzunligiga teng; va agar s dan u tomonga eng ko`p i qirralar bilan yo`l bo`lsa, masofa (u) ko`pi bilan s dan u tomonga va eng ko`p i qirralar bilan eng qisqa yo`lning uzunligi. Isbot. Induksiyaning asosiy ishi uchun i = 0 ni ko`rib chiqing va loop uchun oldingi moment birinchi marta bajariladi. Keyin manba vertex uchun source.distance = 0, bu to`g`ri. Boshqa tepaliklar uchun u, u.distance = abadiylik, bu ham to`g`ri, chunki 0 qirralari bilan manbadan u tomonga yo`l yo`q. Induktiv holat uchun biz avval birinchi qismni isbotlaymiz. Tepalikning masofasi v.distance: = u.distance + uv. weight bilan yangilangan lahzani ko`rib chiqing. Induktiv taxmin bo`yicha, u.distance - bu manbadan u gacha bo`lgan yo`lning uzunligi. Keyin u.distance + uv.weight - bu manbadan vgacha yo`lning davomiyligi, u manbadan u ga o`tib, keyin v ga o`tadi. Ikkinchi qism uchun eng qisqa P yo`lni ko`rib chiqing (bir nechta bo`lishi mumkin) manbadan v ga eng ko`p i qirralar bilan. U bu yo`lda v dan oldingi so`nggi tepalik bo`lsin. So`ngra, manbadan u tomon yo`lning qismi eng ko`p i-1 qirralar bilan manbadan u tomonga eng qisqa yo`ldir, chunki agar u bo`lmasa, u holda eng ko`p i- gacha bo`lgan manbadan u tomonga qat`iy qisqa yo`l bo`lishi kerak. 1 qirralar, keyin biz uv chekkasini ushbu yo`lga qo`shib, eng ko`p i qirralarning P dan qat`iyan qisqaroq yo`lini olishimiz mumkin - ziddiyat. Induktiv farazga ko`ra, u.-i takrorlashdan keyingi masofa ko`pi bilan bu manbadan u gacha bo`lgan yo`lning uzunligi. Shuning uchun uv.weight + u.distance eng katta P. uzunligini tashkil etadi, takrorlashda v.distance uv.weight + u.distance bilan taqqoslanadi va uv.weight + u.distance bo`lsa, unga teng o`rnatiladi. kichikroq. Shuning uchun, i takrorlashdan so`ng, v.distance ko`pi bilan P uzunligi, ya`ni ko`pi bilan i qirralardan foydalanadigan manbadan v ga eng qisqa yo`lning uzunligi. Agar salbiy vaznli tsikllar mavjud bo`lmasa, unda har bir eng qisqa yo`l har bir tepaga bir martadan ko`proq tashrif buyuradi, shuning uchun 3-bosqichda qo`shimcha yaxshilanishlarni amalga oshirish mumkin emas. Aksincha, hech qanday yaxshilanish mumkin emas deb taxmin qiling. Keyin v [0], ..., v [k-1] tepaliklari bo`lgan har qanday tsikl uchun.
Algoritmdan eng qisqa yo`llarni topish uchun foydalanilganda, salbiy tsikllarning mavjudligi muammo bo`lib, algoritm to`g`ri javob topishiga xalaqit beradi. Biroq, u salbiy tsikl topilgandan so`ng tugaydi, shuning uchun Bellman-Ford algoritmi ushbu maqsadni qidiradigan dasturlar uchun ishlatilishi mumkin, masalan, tarmoq oqimini tahlil qilishda tsiklni bekor qilish texnikasida.
Bellman-Ford algoritmining taqsimlangan varianti masofaviy-vektorli marshrutlash protokollarida qo`llaniladi, masalan, Routing Information Protocol (RIP). Algoritm tarqatiladi, chunki u odatda Internet-provayderga tegishli bo`lgan IP-tarmoqlar to`plami bo`lgan Avtonom tizim (AS) ichidagi bir qator tugunlarni (routerlarni) o`z ichiga oladi. U quyidagi bosqichlardan iborat:

1.har bir tugun o`zi va AS tarkibidagi boshqa tugunlar orasidagi masofani hisoblab chiqadi va bu ma`lumotlarni jadval sifatida saqlaydi.

2.Har bir tugun o`z jadvalini barcha qo`shni tugunlarga yuboradi.

3.Tugun qo`shnilaridan masofaviy jadvallarni qabul qilganda, boshqa barcha tugunlarga eng qisqa yo`nalishlarni hisoblab chiqadi va har qanday o`zgarishlarni aks ettirish uchun o`z jadvalini yangilaydi.

Bellman-Ford algoritmining ushbu parametrdagi asosiy kamchiliklari quyidagilardan iborat:

• 
  u yaxshi masshtabga ega emas.
  
• 
  Tarmoq topologiyasidagi o`zgarishlar tezda aks etmaydi, chunki yangilanishlar tugunma-tugun tarqaladi.
  
• 
  Agar ulanish yoki tugun ishlamay qolsa, tugunni boshqa ba`zi tugunlar bilan aloqa o`rnatib bo`lmaydigan qilib qo`ysa, bu tugunlar unga masofani asta-sekin oshirib borishi uchun abadiy sarflashi mumkin va shu bilan birga marshrutlash tsikllari bo`lishi mumkin.
  

Bellman-Ford algoritmi amalda yaxshilanishi mumkin (eng yomon holatda bo`lmasa ham), agar algoritmning asosiy tsiklining iteratsiyasi hech qanday o`zgartirish kiritmasdan tugasa, algoritm darhol tugatilishi mumkin, chunki keyingi takrorlashlar boshqa o`zgarishlar qilmang. Ushbu erta tugatish sharti bilan, asosiy tsikl ba`zi hollarda | V | dan kamroq foydalanishi mumkin - Algoritmning eng yomon holati o`zgarishsiz qolishiga qaramay, 1 ta takrorlash. Yen (1970) Bellman-Ford algoritmida salbiy vaznli tsikllarsiz grafikaning yana ikkita yaxshilanishini tasvirlab berdi; yana, algoritmni amalda tezroq qilish bilan birga, ular uning {\ displaystyle O (| V | \ cdot | E |)} O (| V | \ cdot | E |) vaqtini o`zgartirmaydi. Uning birinchi yaxshilanishi algoritmning har bir takrorlanishida bajarilishi kerak bo`lgan bo`shashish bosqichlarini kamaytiradi. Agar v tepalik masofa qiymatiga ega bo`lsa, oxirgi marta v ning qirralari bo`shashtirilgandan buyon o`zgarmagan bo`lsa, u holda ikkinchi marta va chetlarini bo`shashtirishga hojat yo`q. Shu tarzda, to`g`ri masofa qiymatlariga ega bo`lgan tepalar soni o`sib borishi bilan, har bir iteratsiyada bo`shashishi kerak bo`lgan chiqadigan qirralari kichrayib, zich grafikalar uchun vaqtni doimiy ravishda tejashga olib keladi. Yenning ikkinchi yaxshilanishi avval barcha tepaliklarda bir nechta o`zboshimchalik bilan chiziqli tartibni tayinlaydi va keyin barcha qirralarning to`plamini ikkita pastki qismga ajratadi. Birinchi kichik to`plam Ef barcha qirralarni (vi, vj) o`z ichiga oladi, ular i <j; ikkinchisi, Eb, i> j ga teng qirralarni (vi, vj) o`z ichiga oladi. Har bir tepaga v1, v2, ..., v | V | tartibida tashrif buyurib, Efdagi ushbu vertikadan har bir chiquvchi chekka bo`shashtiriladi. Keyin har bir tepaga v | V |, v | V | -1, ..., v1 tartibida tashrif buyurib, Eb-dagi ushbu tepadan har bir chiquvchi chekka bo`shashtiriladi. Algoritmning asosiy tsiklining har bir takrorlanishi, birinchisidan so`ng, bo`shashgan masofalari to`g`ri yo`lning eng qisqa masofalariga to`g`ri keladigan qirralarning to`plamiga kamida ikkita qirrani qo`shadi: biri Ef dan, ikkinchisi Eb dan. Ushbu modifikatsiya algoritmning asosiy tsiklining eng yomon takrorlanish sonini | V | dan kamaytiradi - 1 dan {\ displaystyle | V | / 2} | V | / 2 gacha. [5] [6] Bannister & Eppstein (2012) tomonidan ishlab chiqilgan yana bir yaxshilanish, Yenning ikkinchi yaxshilanishida ishlatiladigan tepaliklarning o`zboshimchalik bilan chiziqli tartibini tasodifiy almashtirish bilan almashtiradi. Ushbu o`zgarish Yenning yaxshilanishi uchun eng yomon holatni keltirib chiqaradi (bunda eng qisqa yo`lning chekkalari Ef va Eb ikkita kichik to`plamlari o`rtasida qat`iy ravishda o`zgarib turadi). Tasodifiy permute vertex tartibida asosiy tsiklda kutilayotgan takrorlanish soni ko`pi bilan {\ displaystyle | V | / 3} | V | / 3 ga teng. [6] Bellman-Ford algoritmiga birinchi navbatda birinchi navbatni qo`shadigan algoritmning o`zgarishi, "Eng qisqa yo`l tezroq algoritmi" deb nomlangan, Edvard Mur tomonidan 1959 yilda nashr etilgan. Dastlabki algoritm bilan bir xil yomon tahlilga ega ammo ba`zi holatlarda yaxshiroq ishlaydi.
Asl manbalar

• 
  Shimbel, A. (1955). Structure in communication nets. Proceedings of the Symposium on Information Networks. New York, New York: Polytechnic Press of the Polytechnic Institute of Brooklyn. pp. 199–203.
  
• 
  Bellman, Richard (1958). "On a routing problem". Quarterly of Applied Mathematics. 16: 87–90. doi:10.1090/qam/102435. MR 0102435.
  
• 
  Ford, Lester R. Jr. (August 14, 1956). Network Flow Theory. Paper P-923. Santa Monica, California: RAND Corporation.
  
• 
  Moore, Edward F. (1959). The shortest path through a maze. Proc. Internat. Sympos. Switching Theory 1957, Part II. Cambridge, Massachusetts: Harvard Univ. Press. pp. 285–292. MR 0114710.
  
• 
  Yen, Jin Y. (1970). "An algorithm for finding shortest routes from all source nodes to a given destination in general networks". Quarterly of Applied Mathematics. 27 (4): 526–530. doi:10.1090/qam/253822. MR 0253822.
  
• 
  Bannister, M. J.; Eppstein, D. (2012). Randomized speedup of the Bellman–Ford algorithm. Analytic Algorithmics and Combinatorics (ANALCO12), Kyoto, Japan. pp. 41–47. arXiv:1111.5414. doi:10.1137/1.9781611973020.6.
  

Ikkilamchi manbalar

• 
  Bang-Jensen, Jørgen; Gutin, Gregory (2000). "Section 2.3.4: The Bellman-Ford-Moore algorithm". Digraphs: Theory, Algorithms and Applications (First ed.). ISBN 978-1-84800-997-4.
  
• 
  Schrijver, Alexander (2005). "On the history of combinatorial optimization (till 1960)" (PDF). Handbook of Discrete Optimization. Elsevier: 1–68.
  
• 
  Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L. Introduction to Algorithms. MIT Press and McGraw-Hill., Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Section 24.1: The Bellman–Ford algorithm, pp. 588–592. Problem 24-1, pp. 614–615. Third Edition. MIT Press, 2009. ISBN 978-0-262-53305-8. Section 24.1: The Bellman–Ford algorithm, pp. 651–655.
  
• 
  Heineman, George T.; Pollice, Gary; Selkow, Stanley (2008). "Chapter 6: Graph Algorithms". Algorithms in a Nutshell. O'Reilly Media. pp. 160–164. ISBN 978-0-596-51624-6.
  
• 
  Kleinberg, Jon; Tardos, Éva (2006). Algorithm Design. New York: Pearson Education, Inc.
  
• 
  Sedgewick, Robert (2002). "Section 21.7: Negative Edge Weights". Algorithms in Java (3rd ed.). ISBN 0-201-36121-3. Archived from the original on 2008-05-31. Retrieved 2007-05-28.