deykstr algoritmi

DOC 42 стр. 472,5 КБ Бесплатная загрузка

Предварительный просмотр (5 стр.)

Прокрутите вниз 👇
1 / 42
o‘zbekiston respublikasi oliy ta’lim, fan va innovatsiyalar vazirligi __universiteti kurs ishi mustaqil ish referatmavzu:________________ deykstr algoritmi mundarija оглавление 3kirish 4deykstra algoritmining tarixi 41.1 deykstra algoritmining kelib chiqishi 61.2 deykstra algoritmining tuzilishi 10ii. algoritmni amaliyotda qo’llash 102.1 dijkstra algoritmini dasturlash tillaridagi ko’rinishi 142.2 dijkstra algoritmini jadvalda ifodalash. 182.3 tegishli muammolar va algoritmlar 20xulosa 21foydalanilgan adabiyotlar 22internet saytlari kirish bugungi kunda milliy axborot tizimini shakllantirish jarayonida intеrnеt va boshqa global axborot tizimlaridan foydalanish, ayniqsa, muhim ahamiyatga ega. yangi axborot – kommunikatsion texnologiyalari hozirgi vaqtda eng dolzarb mavzulardan biri bo’lib kelmoqda, sababi har bir sohani o’rganish, izlanish va tajriba orttirish uchun turli usullardan foydalanish kerak bo’ladi. shuning uchun yangi axborot – kommunikatsion texnologiyalardan foydalanish maqsadga muvofiqdir. hozirgi zamon mutaxassislari, faoliyat doiralari qanday bo’lishidan qat’iy nazar axborot texnalogiyalari bo’yicha keng ko’lamdagi bilimlarga, zamonaviy hisoblash texnikasi, informatsion aloqa va kommunikatsiya tizimlari, orgtexnika vositalari va ulardan foydalanish borasida yetarli malakalarga ega bo’lishi, hamda yangi informatsion texnika …
2 / 42
mida tuzilgan dasturlar mavjud. deykstra algoritmi – bu biror joydan turib boshqa joyga borim kerak bo’lganda va u yerga borishning uchun bir necha xil usullari bor bo’lganda ishlatiladi. bu algoritm bizga bu usullar orasidan eng qisqa yo’lli ,eng kam xarajatli , eng qisqa vaqtlisini topib beradi. bu algoritmdan ko’plab sohalarda foydalanib kelinadi. deykstra algoritmining tarixi 1.1 deykstra algoritmining kelib chiqishi “qanday sayohat qilish eng qisqa yo'ldir, rotterdam shahridan groningen shahriga umuman,: bu shahardan berilgan shaharga. bu eng qisqa yo'lning algoritmi , men uni yigirma daqiqada yaratganman. bir kuni ertalab amsterdamda xarid qilgan edim yosh kelinim bilan charchagan holda, biz bir stakan qahva ichish uchun kafe terastasiga o'tirdik va men buni qilsam bo'ladimi, deb o'ylardim va keyin eng qisqa yo'l uchun algoritmni ishlab chiqdim. aytganimdek, bu yigirma daqiqalik ixtiro edi. aslida, uch yil o'tgach, u 1959 yilda nashr etilgan. nashr hali ham o'qilishi mumkin, bu juda yaxshi. bu juda yoqimli bo'lishining …
3 / 42
il o'tgach, u institutning keyingi kompyuterida ishlaydigan apparat muhandislari tomonidan yana bir muammoga duch keldi: mashinaning orqa panelidagi pimlarni ulash uchun zarur bo'lgan sim miqdorini minimal darajada kamaytirish. yechim sifatida, u primning minimal daraxtni o'stiradigan algoritmi deb nomlangan algoritmni ( jarnik tomonidan ilgari ma'lum bo'lgan va shuningdek, prim tomonidan kashf qilingan ) qayta kashf 5 etgan.dijkstra 1959-yilda, primdan ikki yil keyin va jarnikdan 29 yil keyin algoritmni nashr etdi. dijkstraning algoritmi (yoki dijkstraning eng qisqa yo'lining birinchi algoritmi) - bu , masalan, yo'l tarmoqlarini aks ettirishi mumkin bo'lgan grafikadagi tugunlar orasidagi eng qisqa yo'llarni topish uchun algoritm . u 1956- yilda kompyuter olimi edsger v. dijkstra tomonidan ishlab chiqilgan va uch yildan so'ng nashr etilgan. algoritm ko'p variantlarda mavjud. dijkstra asl algoritm ikki berilgan tugunlari orasidagi eng qisqa yo'lni topadi. grafikdagi berilgan manba tuguni uchun algoritm ushbu tugun va boshqa har tugun orasidagi eng qisqa yo'lni topadi. bundan tashqari, kerak …
4 / 42
chik dastur sifatida ishlatiladi . dijkstra algoritmida musbat butun sonlar yoki haqiqiy sonlardan foydalaniladi. dijkstra algoritmi boshidan masofa bo'yicha saralangan qisman echimlarni saqlash va so'rash uchun ma'lumotlar tuzilmasidan foydalanadi. ushbu algoritm g'oyasi leyzorek va boshqalarda ham berilgan . 1957 yil . fredman va tarjan 1984 , ish vaqtining murakkabligini optimallashtirish uchun minimal ustunlikdagi fibonachchi sonlaridan foydalanishni taklif qiladi. bu asemptomatik ravishda , ma'lum manfiy bo'lmagan uzunliklarga ega ixtiyoriy yo'naltirilgan grafikalar uchun eng tez tanilgan bitta manbali qisqa yo'nalishli algoritm. 1.2 deykstra algoritmining tuzilishi ushbu algoritm bitta manbali eng qisqa yo'llar muammosi deb ham nomlanadi bizga n ta nuqta berilgan bo’lsin. biz bu nuqtalar ichidan bittasini boshlang’ich nuqta sifatida tanlaymiz va shu nuqtadan qolganlarigacha bo’lgan masofalarini toppish bizning maqsadimiz. bunig uchun biz dastlab bitta matritsa hosil qilamiz. bu matritsa o’zida ixtiyoriy nuqtadan boshqa bir ixtiyoriy nuqtagacha bo’lgan masofani saqlaydi. bizga ixtiyoriy ikki nuqta orasidagi masofa kerak bo’lganda shu matritsa orqali topib …
5 / 42
algoritmi n marta takrorlanadi. har bir takrorlanishda u[] massivda false qiymatga ega bo’lgan nuqtalar ichidan d[] massivda eng kichik qiymatga ega bo’lgan nuqta olinadi. va bu nuqta uchun eng qisqa masofa topilgan hisoblanadi. takrorlanishda boshlang’ich s nuqta tanlanadi. har bir takrorlanganda bittadan nuqta tanlanadi va uning u[] massivdagi qiymati true ga almashtiriladi. bu uning boshqa tanlanmasligini kafolatlaydi. biror nuqta tanlangandan keyin u nuqta keyingi takrorlanish uchun saqlab qolinadi. har bir takrorlanishda u[] massivida false qiymatga ega nuqtalarning d[] massivdagi joriy qiymati va saqlangan nuqtaning eng qisqa masofasi bilan saqlangan nuqta va joriy nuqta orasidagi masofalarniyeg’indisi solishtiriladi. va bu solishtirilayotgan masofalardan kichigi joiriy nuqtaning eng qisqa masofasi sifatida saqlanadi. bunday nuqtalarning barchasi ko'rib chiqilgandan so'ng, joriy takrorlanish tugaydi. nihoyat, keyingi takrorlanishlarda barcha nuqtalar uchun eng qisqa masofalar topiladi va algoritm tugaydi. algoritm tugaganidan so’ng, d[] massiv o’zizda boshlang’ich nuqtadan qolgan nutalargacha bo’lgan eng qisqa masofalarni saqlaydi. agar ba'zi bir nuqatlar boshlang'ich …

Хотите читать дальше?

Скачайте все 42 страниц бесплатно через Telegram.

Скачать полный файл

О "deykstr algoritmi"

o‘zbekiston respublikasi oliy ta’lim, fan va innovatsiyalar vazirligi __universiteti kurs ishi mustaqil ish referatmavzu:________________ deykstr algoritmi mundarija оглавление 3kirish 4deykstra algoritmining tarixi 41.1 deykstra algoritmining kelib chiqishi 61.2 deykstra algoritmining tuzilishi 10ii. algoritmni amaliyotda qo’llash 102.1 dijkstra algoritmini dasturlash tillaridagi ko’rinishi 142.2 dijkstra algoritmini jadvalda ifodalash. 182.3 tegishli muammolar va algoritmlar 20xulosa 21foydalanilgan adabiyotlar 22internet saytlari kirish bugungi kunda milliy axborot tizimini shakllantirish jarayonida intеrnеt va boshqa global axborot tizimlaridan foydalanish, ayniqsa, muhim ahamiyatga ega. yangi axborot – kommunikatsion texnologiyalari hozirgi vaqtda eng dolzarb mavzulardan biri bo’lib k...

Этот файл содержит 42 стр. в формате DOC (472,5 КБ). Чтобы скачать "deykstr algoritmi", нажмите кнопку Telegram слева.

Теги: deykstr algoritmi DOC 42 стр. Бесплатная загрузка Telegram