|
Oliy va o`rta maxsus ta`lim vazirligi
Samarqand Davlat Universiteti
“Amaliy matematika va informatika” fakulteti
“Amaliy matematika va informatika” yo’nalishi
Algoritmlar va malumotlar strukturasi fanidan tayorlagan
“Eng qisqa masofani(yo’lni)toppish,Deykstra algoritmi va uni tahlil qilish” mavzusidagi
KURS ISHI
Bajardi:
Tekshirdi:
SAMARQAND-2019
Mundarija
Оглавление
KIRISH 3
1.Tarixi 3
2. Eng qisqa yo’llar masalalarining turlari. 4
3.Deykstra algoritmning so’zli tavsifi 4
4.Masalaning qo’yilishi. 5
4.Deyskra Algoritmi. 6
5.Dastur kodi 13
6.Tegishli muammolar va algoritmlar. 20
7.Eng qisqa masofani toppishga doir testlar 21
Xulosa 22
Foydalangan adabiyotlar: 23
KIRISH
Qandaydir masalani xal etishga kirishishdan avval buning uchun eng yaxshi uslub izlanadi va uni qay tarzda tavsiflash aniqlanadi. Boshqacha qilib aytganda, biz doimo maqsadi ba’zi bir zaruriy natijaga erishishdan iborat, amallar ketma-ketligi bilan berilgan turli-tuman qoidalarga duch kelamiz. Bunday amallarning ketma-ketligi algoritm deb ataymiz.
Matematikada algoritmning murakkabligi, xal etish masalalari va ularni ishlab chiqish prinsiplarini o‘rganadigan maxsus “Algoritmlar nazariyasi” bo‘limi xam mavjud.
Algoritmlar nazariyasi – algoritmlarning umumiy xossalari, qonuniyatlari va ularni tasvirlanishining turli-tuman formal modellarini o‘rganish bilan shug'ullanadi. Algoritm tushunchasini formallashtirish asosida ularning samaradorligi taqqoslash, ularning ekvivalentligi tekshirish, qo‘llanilish sohasini aniqlash mumkin.
1.Tarixi
Rotterdamdan Groningenga umuman olganda berilgan shahardan ushbu shahargacha sayohat qilishning eng qisqa yo'li nima? Bu yigirma daqiqada mo'ljallangan eng qisqa yo'l uchun algoritm. Bir kuni ertalab men yosh yigitlar bilan Amsterdamda xarid qilardim va charchagan edik, biz kofe choy ichib, kofe terastasiga o'tirdik va men buni qila olamanmi yoki yo'qmi deb o'ylagandim va keyinchalik eng qisqa yo'l uchun algoritmni yaratdim . Men aytganimdek, yigirma daqiqalik ixtiro bo'ldi. Darhaqiqat, u 59 yil ichida, uch yil o'tib nashr etildi. Bu kitob hali ham o'qilishi mumkin, aslida juda yaxshi. Bu juda yaxshi bo'lgan sabablardan biri men uni qalam va qog'ozsiz tasvirladim. Keyinchalik bilib oldimki, qalam va qog'ozsiz loyihalashtirishning afzalliklaridan biri deyarli barcha oldini olish mumkin bo'lgan murakkabliklardan qochishingiz kerak. Oxir-oqibat, bu algoritm mening shon-shuhratimning asosiy toshlaridan biri bo'lgan.
- Edzger Dijkstra, ACM bilan aloqa, Philip L. Frana, 2001.
Dijkstra 1956 yilda Amsterdamdagi Matematik markazda ARMAC nomli yangi kompyuterning imkoniyatlarini namoyish etish uchun dasturchi sifatida eng qisqa yo'l muammosini o'ylab topdi.Uning maqsadi ham hisoblanmaydigan odamlar tushunishi mumkin bo'lgan muammoni va echimni (kompyuter tomonidan ishlab chiqariladigan) tanlash edi. U eng qisqa yo'l algoritmini ishlab chiqdi va undan keyin uni Gollandiyada 64 ta shaharning biroz soddalashtirilgan transport xaritasi uchun ARMAC uchun amalga oshirdi (64, ya'ni 6 bit shahar raqamini kodlash uchun etarli bo'ladi).Bir yil o'tgach, u institutning navbatdagi kompyuterida ishlaydigan apparat-muhandislardan boshqa muammolarga duch keldi: mashinaning orqa panelidagi pimlarni ulash uchun zarur bo'lgan simni kamaytirish. Yechim sifatida u Primning eng kichik spanning daraxt algoritmi deb nomlanadigan algoritmni (avvalroq Jarnikka ma'lum va shuningdek, Primni qayta kashf qilgan) kashf etdi. Dijkstra 1959 yilda, Primdan ikki yil keyin va Jarnikdan 29 yil o'tgach algoritmi nashr etdi.
2. Eng qisqa yo’llar masalalarining turlari.
Yo’l tarmoqlari atlasi (karta) qismi berilgan bo’lib, undan A va B nuqtalar orasidagi “eng yahshi” marshrutni topish kerak bo’lsin. “Eng yahshi” marshrutni ko’p faktorlar belgilashi mumkin, masalan, tezlik cheklangan holda marshrutni o’tish vaqti, o’tish kerak bo’lgan shaharlar soni va boshqalar.
Biz masalani eng qisqa yo’llar faktori bo’yicha yechamiz. Masalaning modeli turlar yordamida tuziladi. Uzluksiz G turni har bir qirrasiga uning uzunligiga teng qiymat berilgan ko’rinishida tuzamiz. Bunday turda masofa irralar yig’indisiga teng bo’ladi. Masalaning maqsadi ikkita berilgan uchlar orasidagi eng qisqa marshrutni topishdir.
Umuman, eng qisqa yo’llar masalalari kombinator optimallashtirishning fundamental muammolaridandir. Ularning bir necha turlari mavjud, masalan, ikkita berilgan uchlar orasida, berilgan va qolgan barcha uchlar orasida, turdagi har bir uchlar juftliklari orasida va boshqalar.
3.Deykstra algoritmning so’zli tavsifi
Eng qisqa masofani topish masalalarni yechish uchun Deykstra algoritmi ancha qulay va yahshi deb topilgan.
Algoritm quyidagi qadamlardan iborat:
Dastlab, berilgan (Lex) uchidan qolgan barcha uchlargacha bir qirra uzunligidagi masofalar aniqlanadi.
Ulardan eng qisqasi “doimiy eng qisqa masofa” sifatida belgilanadi (Lex va BVa uchlari qirrasi).
Aniqlangan masofa BVa dan boshqa bor uchlargacha masofalarga qo’shiladi.
Hosil bo’lgan yig’indilar dastlab aniqlangan Lex dan qolgan uchlargacha bo’lgan masofalar bilan taqqoslanadi. Natijada masofasi qisqaroq bo’lgan uchning qirrasi tanlanadi.
BVa uchi, eng qisqa masofa aniqlangan uch sifatida, ruyhatdan o’chiriladi. Ruyhatga boshqa uch qo’yiladi, masalan, Roa. Bva o’z navbatida, boshqa, izlanayotgan ruyhatga qo’yiladi.
Keyingi eng qisqa masofani topish uchun butun jarayon qayta bajariladi. BVa dan keyin yana bir uch ruyhatga qo’yiladi. Dastlabkisi esa ruyhatdan o’chiriladi. Sikl Bed va Lex uchlarini bog’lash uchun belgilangan qirralar aniqlanishi bilan to’xtatiladi.
4.Masalaning qo’yilishi.
M tauch va N ta qirralardan iborat uzluksiz grafda V0 uchidan W uchigacha Dist(W) masofani topish kerak. Qirralaruzunliklari A matrisabilanberilgandebhisoblaymiz.
Qadam 0. [uchlarnibelgilash] – buyerda V0 uchini “aniqlangan” debbelgilaymiz, qolganbarchauchlarini “aniqlanmagan” debhisoblaymiz.
Qadam 1. [o’zgaruvchilarni inetsiallashtirish] – bu yerda
Dist(U):=A(V0 ,U) – barcha G ga tegishli U uchlari uchun;
Dist(V0):=0;Next:=V0; Qadam 2. [sikl]. While NEXT<>W do
Begin Qadam 3. [“aniqlanmagan” uchgacha eng qisqa yo’lni yangilash]. Har bir “aniqlanmagan” U uchi uchun
Dist(U):=min(Dist(U):Dist(Next)+A(Next, U)).
Qadam 4. [“aniqlanmagan” uchgacha eng qisqa yo’lni tanlash]. Agar U barcha “aniqlanmagan” uchlari orasida Dist(U) masofasi eng kichik bo’lsa, uni “aniqlangan” deb belgilaymiz va NEXT:=U.
end.
Bu algoritmning va dasturning murakkabligini O(M2) ekanligini ko’rsatish mumkin.
Yo’l tarmoqlari atlasi (karta) qismi berilgan bo’lib, undan A va B nuqtalar orasidagi “eng yahshi” marshrutni topish kerak bo’lsin. “Eng yahshi” marshrutni ko’p faktorlar belgilashi mumkin, masalan, tezlik cheklangan holda marshrutni o’tish vaqti, o’tish kerak bo’lgan shaharlar soni va boshqalar. Biz masalani eng qisqa yo’llar faktori bo’yicha yechamiz. Masalaning modeli turlar yordamida tuziladi. Uzluksiz G turni har bir qirrasiga uning uzunligiga teng qiymat berilgan ko’rinishida tuzamiz. Bunday turda masofa irralar yig’indisiga teng bo’ladi. Masalaning maqsadi ikkita berilgan uchlar orasidagi eng qisqa marshrutni topishdir. Umuman, eng qisqa yo’llar masalalari kombinator optimallashtirishning fundamentalmuammolaridandir. Ularning bir necha turlari mavjud, masalan, ikkita berilgan uchlar orasida,
berilgan va qolgan barcha uchlar orasida, turdagi har bir uchlar juftliklari orasida va boshqalar.
Deykstra algoritmning so’zli tavsifi
Shunday masalalarni yechish uchun Deykstra algoritmi ancha qulay va yahshi deb topilgan.
Algoritm quyidagi qadamlardan iborat:
6. Dastlab, berilgan (Lex) uchidan qolgan barcha uchlargacha bir qirra uzunligidagi masofalar aniqlanadi.
7. Ulardan eng qisqasi “doimiy eng qisqa masofa” sifatida belgilanadi (Lex va BVa uchlari qirrasi).
8. Aniqlangan masofa BVa dan boshqa bor uchlargacha masofalarga qo’shiladi.
9. Hosil bo’lgan yig’indilar dastlab aniqlangan Lex dan qolgan uchlargacha bo’lgan masofalar bilan taqqoslanadi. Natijada masofasi qisqaroq bo’lgan uchning qirrasi tanlanadi.
10. BVa uchi, eng qisqa masofa aniqlangan uch sifatida, ruyhatdan o’chiriladi. Ruyhatga boshqa uch qo’yiladi, masalan, Roa. Bva o’z navbatida, boshqa, izlanayotgan ruyhatga qo’yiladi.
Keyingi eng qisqa masofani topish uchun butun jarayon qayta bajariladi. BVa dan keyin yana bir uch ruyhatga qo’yiladi. Dastlabkisi esa ruyhatdan o’chiriladi. Sikl Bed va Lex uchlarini bog’lash uchun belgilangan qirralar aniqlanishi bilan to’xtatiladi.
4.Deyskra Algoritmi.
Grafdagi eng qisqa marshrutlar uchun ko'plab qidiruv algoritmlari bo'yicha, Habreda faqatgina Floyd-Worschall algoritmining ta'rifi topildi. Ushbu algoritm grafikaning barcha vertikalari va ularning uzunligi o'rtasidagi eng qisqa yo'llarni topadi. Ushbu maqolada Dijkstra algoritmining ishlash printsipini tasvirlab beraman. Bu algoritm optimal yo'nalishlarni va ularning uzunligini ma'lum bir vertikal (manba) va grafikning boshqa vertikalari orasida topadi. Ushbu algoritmning nochorligi, agar grafika salbiy og'irliklarga ega bo'lsa, u noto'g'ri ishlaydi.
Misol uchun, G quyidagi ko'rsatgichni bajaring:
tasvirUshbu grafikani matritsa sifatida taqdim etamiz:tasvir
Keling, vertex 1ni manba sifatida qabul qilaylik, shuning uchun vertex 1dan eng kichkina marshrutlarni 2, 3, 4 va 5-ustungacha topamiz.Ushbu algoritm grafaning barcha verticesida yineleyadi va manba verteksidan muayyan vertexga ma'lum minimal masofa bo'lgan belgilarga ularni belgilaydi. Masalan, ushbu algoritmni ko'rib chiqaylik.Keling, 1 tepalikka tegni 0 ga teng qilamiz, chunki bu vertex manba hisoblanadi. Qolgan tepaliklar abadiylikka teng teglar bilan belgilanadi.
Keyinchalik, minimal yorlig'i (hozirda vertex 1) bo'lgan vertikal W ni tanlang va vertex W dan mediatorlar vertikalarini o'z ichiga olmaydi. W belgisining yig'indisiga teng bo'lgan belgini va hisobga olingan vertikalarning har biriga qarab, Vdan vertikaga yo'llarni belgilang, lekin natijada faqat oldingi qiymatdan kamroq bo'lsa. Agar bu miqdor kam bo'lmasa, oldingi belgini o'zgartirmang.Biz W dan to'g'ridan-to'g'ri yo'lni egallagan barcha vertikalarni ko'rib chiqdik, keyin V ga tashrif buyurib, tepaligini eng past qiymatga ega bo'lganlardan tanlaymiz va u keyingi V tepasida bo'ladi. Bu holda, bu birinchi 2 yoki 5. Agar bir xil teglar bilan bir necha vertikalar mavjud bo'lsa, ularning qaysi biri W ni tanlashimiz muhim emas.
Biz vertex 2 ni tanlaymiz. Biroq, undan bitta chiqish yo'li yo'q, shuning uchun darhol ushbu vertexni tashrif buyurgan deb belgilab olamiz va keyingi vertikaga minimal belgisi bilan kiramiz. Bu safar faqat vertex 5da eng kam belgilar mavjud. 5-dan 5-gacha to'g'ridan-to'g'ri yo'llar mavjud bo'lgan barcha vertikalarni ko'rib chiqing, ammo hozircha ular tashrif buyurilgan deb bo'lmaydi. Shunga qaramay, vertex W yorlig'ining yig'indisi va W dan joriy vertexning chekkasini topamiz va agar bu summa oldingi yorliqdan kamroq bo'lsa, biz natijada olingan qiymat bilan etiketaning qiymatini o'zgartiramiz.
Rasmga asoslanib, biz uchinchi va to'rtinchi zirvalarning yorliqlari kichikroq ekanligini, ya'ni manba tepasidagi bu tepaliklarga nisbatan qisqaroq yo'lni topdik. Keyinchalik, 5 vertexni tashrif buyurgan deb belgilang va eng past belgisi bo'lgan keyingi vertikani tanlang. Yuqorida keltirilgan barcha harakatlar takrorlanmagan vertikalar mavjud ekan, takrorlang.
Barcha amallarni bajarib bo'lgach, biz quyidagi natijani qo'lga kiritamiz:
Dijkstraalgoritmi
Grafikdagi ma'lum bir manba tuguniga ega bo'lgan algoritm bu tugun bilan har bir boshqa o'rtasidagi eng qisqa yo'lni topadi. Bundan tashqari, bitta tugunning eng qisqa yo'llarini to'xtatish yo'li bilan bitta maqsadli tugunga maqsad tuguniga eng qisqa yo'l aniqlanganidan keyin algoritm aniqlandi. Masalan, agar grafika tugunlari shaharlarni ifodalasa va chekka xarajatlari to'g'ridan-to'g'ri yo'l bilan bog'langan shaharlarning juftliklari o'rtasidagi masofani ifodalaydi (oddiylik uchun, qizil chiroqlar, ishlamaydigan belgilar, pullik yo'llar va boshqa to'siqlarni e'tiborsiz qoldirish uchun), Dijkstra algoritmi ishlatilishi mumkin Bir shahar va boshqa shaharlarning eng qisqa yo'lini topish. Qisqa yo'l algoritmining keng tarqalgan qo'llanilishi tarmoqni boshqarish protokollaridir, Shuningdek, Jonson kabi boshqa algoritmlarda ham subroutin sifatida qo'llaniladi.
Dijkstra algoritmida musbat tamsayı yoki haqiqiy sonlar bo'lgan etiketlar ishlatiladi, bu aniq zaif tartibga solingan. Qiziqarli tomoni shundaki, Dijkstra aniq belgilangan qisman tartibga ega bo'lgan va keyingi teglar (bir chekkadan o'tib ketganda keyingi yorliq) monotonik ravishda kamaymaslik sharti bilan aniqlangan teglardan foydalanish uchun umumlashtirilishi mumkin. Ushbu umumlashma umumiy Dijkstra qisqa yo'l algoritmi deb ataladi.
Bu asimptotik jihatdan cheklanmagan bo'lmagan grafikalar uchun eng tez-tez ma'lum bo'lgan yagona manbali eng qisqa yo'l algoritmidir. salbiy og'irliklar. Shu bilan birga, ixtisoslashgan variantlar (masalan, cheklangan / to'liq sonlar, yo'naltirilgan asiklik grafikalar va h.k.) ixtisoslashgan variantlarda batafsil ravishda takomillashtirilishi mumkin.Ba'zi sohalarda, xususan sun'iy aql, Dijkstra algoritmi yoki uning bir nusxasi bir xil xarajat qidiruvi deb nomlanadi va eng yaxshi qidiruvga oid umumiy g'oyaning misoli sifatida shakllanadi.Algoritm Dijkstra algoritmining robot harakati rejalashtirishda boshlang'ich tugunidan (pastki chap, qizil) maqsad tuguniga (yuqori o'ng, yashil) yo'l topish. Ochiq tugunlar "noaniq" to'plamni aks ettiradi ("novisited" tugunlar to'plami). To'ldirilgan tugunlar tashrif buyuriladi, rangi masofani ifodalaydi: yashil, qanchalik yaqin. Dijkstra algoritmida 0 ga teng bo'lgan heuristik usulni qo'llaganidek, barcha yo'nalishdagi tugunlar bir xil tarzda o'rganilib, dyuym to'lqinlari ko'rinishida ko'proq yoki kamroq ko'rinadi.
Biz boshlayotgan tugunni boshlang'ich tugun deb ataymiz. Y tugunining masofa boshlang'ich tugunidan Ygacha bo'lgan masofa bo'lsin. Dijkstra algoritmi ba'zi boshlang'ich masofani qadrlaydi va ularni bosqichma-bosqich takomillashtirishga harakatqiladi.Barcha tugunlarni kutmasdan belgilang. Ko'rinmas to'siq deb nomlangan barcha ko'rinmaydigan tugunlarni yaratish.
Har bir tugunga vaqtinchalik masofa qiymatini belgilang: bizning boshlang'ich tugunimiz uchun nolga va boshqa barcha tugunlar uchun abadiyatga sozlang. Boshlang'ich tugunni dolzarb deb belgilang.
Joriy tugun uchun, hozirgi tugunlar orqali barcha ko'rinmagan qo'shnilarini hisobga oling va o'z vaqt oralig'ini hisoblang. Yangi tayinlangan vaqtinchalik masofani joriy tayinlangan qiymat bilan taqqoslang va undan kichikroqni tayinlang. Masalan, agar A tugmasi 6 ga teng bo'lsa va qo'shni B bilan bog'laydigan chetning uzunligi 2 bo'lsa, B dan Agacha masofa 6 + 2 = 8 bo'ladi. Agar B ilgari belgilangan bo'lsa, 8dan katta masofa, keyin uni 8 ga o'zgartiring. Aks holda, joriy qiymatni saqlang.
Biz tugunning barcha ko'rinmagan qo'shnilarini hisobga olgan holda tugallangandan so'ng, joriy tugunni tashrif buyurgan deb belgilab qo'ying va uni ko'rinmas to'siqdan olib tashlang. Tashlangan tugma hech qachon tekshirilmaydi.
Agar maqsad tugunni tashrif buyurilgan deb belgilansa (ikki maxsus tugma o'rtasida marshrutni rejalashtirganda) yoki ko'rinmagan guruhdagi tugunlar orasida eng kichik masofa cheksiz bo'lsa (to'liq traversalni rejalashtirayotganda, boshlang'ich tugun bilan va bekor qilinmagan tugunlarni) keyin to'xtating. Algoritm tugadi.
Aks holda, eng kichik vaqt oralig'i bilan belgilanmagan ko'rinmaydigan tugunni tanlang, uni yangi «joriy tugun» deb o'rnating va 3-bosqichga qayting.
Marshrutni rejalashtirishda, aslida maqsadli tugun yuqorida ko'rsatilgan "kutilgan" bo'lguncha kutishning hojati yo'q: maqsadli tugun barcha "kutilmagan" tugunlar orasidagi eng kichik masofani egallab olgandan so'ng to'xtashi mumkin
Izoh: tushunish qulayligi uchun bu munozarada choralar, yo'llar va xarita atamalaridan foydalaniladi, ammo rasmiy terminologiyada bu atamalar navbati bilan vertex, kenar va grafika hisoblanadi.
Bir shahar xaritasida ikkita kavşak o'rtasida eng qisqa yo'lni topmoqchiman: boshlang'ich nuqtasi va borar joyi. Dijkstra algoritmi dastlab masofani masofani (boshlang'ich nuqtadan) xaritada har bir kesib o'tish joyiga abadiylik bilan belgilaydi. Bu cheksiz masofa mavjudligini anglatmaslik uchun emas, balki bu chorrahalar hali kelmaganligini ta'kidlash uchun qilingan. Ushbu usulning ayrim variantlari kesishmalarning masofalaridan ajralmagan holda qoldiriladi. Endi har bir iteratsiyada joriy kesishni tanlang. Birinchi iteratsiya uchun joriy kesish boshlanish nuqtasi bo'ladi va unga masofa (kesishma yorlig'i) nol bo'ladi. Keyingi izlanishlar uchun (keyingi birinchi), joriy kesishish boshlang'ich nuqtaga eng yaqin ko'rinmaydigan kesishish bo'ladi (bu oson topiladi).Joriy kesishuvdan to'g'ridan-to'g'ri bog'langan har qanday ko'rinishdagi kesishma masofani yangilang. Buning sababi, mavjud bo'lmagan kesishma va joriy kesishma qiymatlari o'rtasidagi masofaning umumiy miqdorini belgilash va keyinchalik kiritilmagan kesishishning ushbu qiymatga (summaga) kiritilmasligi, agar u kutilmagan kesishma oqimining qiymatidan kamroq bo'lsa. Haqiqatdan ham, agar kesishma yo'li orqali unga yo'l oldindan ma'lum bo'lgan yo'llardan qisqartirilsa, kesishma qayta belgilanadi. Eng qisqa yo'lni identifikatsiyalashni engillashtirish uchun, qalamda yo'lni ko'rsatgich bilan belgilab qo'ying va uni ko'rsatgan barcha belgilarni o'chirib tashlang. Har bir qo'shni kesib o'tish joyiga masofani yangilaganingizdan so'ng, joriy kesishuvni tashrif buyurilgan deb belgilang va eng kichik masofani (boshlang'ich nuqtadan) yoki eng pastki belgini - mavjud kesishma sifatida tanlamang. Ko'rilgan deb nomlangan uchastka boshlang'ich nuqtadan eng qisqa yo'l bilan etiketlanadi va qayta ko'rib chiqilmaydi yoki qaytarilmaydi.
Qo'shni uchastkalarni eng qisqa masofalar bilan yangilab borish, mavjud kesishishni tashrif buyurgan deb belgilash va maqsadni tashrif buyurgan deb belgilaguningizcha eng yaqin ko'rinmaydigan kesma tomonga o'tish jarayonini davom ettiring. Belgilangan joyni tashrif buyurganingiz kabi belgilab qo'yganingizdan so'ng (siz tashrif buyurgan har qanday kesishmada bo'lgani kabi), siz boshlash nuqtasidan eng qisqa yo'lni belgilab oldingiz va orqadagi o'qlar orqasidan yo'lni orqaga qaytarasiz. Algoritmni amalga oshirishda, bu odatda tugma tugunlaridan boshlang'ich tuguniga qadar tugunlarni ota-onalariga rioya qilish yo'li bilan amalga oshiriladi (algoritm maqsadli tugunga yetgandan keyin); Shuning uchun biz har bir tugunning ota-onasini kuzatib boramiz.Ushbu algoritm kutilayotgan maqsadga yo'naltirilgan to'g'ridan-to'g'ri "qidiruv" harakatlariga yo'l qo'ymaydi. Aksincha, kelgusi "joriy" kesishishni aniqlashda yagona e'tibor uning boshlang'ich nuqtasigacha bo'lgan masofasidir. Shuning uchun ushbu algoritm boshlang'ich nuqtadan tashqariga chiqadi, interaktiv ravishda maqsadga etgunga qadar eng qisqa yo'l masofasi jihatidan yaqinroq bo'lgan har bir tugunni hisobga oladi. Shu tarzda tushunilsa, algoritm qanday qilib eng qisqa yo'lni topish kerakligi aniq. Shu bilan birga, u algoritmning zaif tomonlaridan birini ham ko'rsatishi mumkin: ba'zi bir topologiyalardagi nisbiy sekinligi
Do'stlaringiz bilan baham: |
