• MAVZU: Graflarni eniga va boyiga aylanish
  • Deykstra algoritmi
  • Mustaqil ish 1 s Bajardi: Rabbonayev Javoxir mavzu: Graflarni eniga va boyiga aylanish




    Download 239.93 Kb.
    bet1/4
    Sana25.06.2022
    Hajmi239.93 Kb.
    #24431
      1   2   3   4
    Bog'liq
    AL.mustaqilish
    anotomiya, Nazariy №13 Mavzu Taqdimot muharrirlari va ularda ishlash. Reja, Metall kesuychl stanoklatlya ularning tasnifi Bobning qisqacha m, Договор №891082 электронный магазин (2), my-favourite-website, “Baliqning ichki tuzulishi”, 5-6-7-8-9 sinf rasmli test, Ikki to’g’ri chiziq orasidagi burchak.

    O’zbekiston Respublikasi Axborot Texnologiyalari va
    Kommunikatsiyalarini rivojlantirish Vazirligi
    Muhammad Al-Xorazmiy nomidagi
    Toshkent Axborot Texnologiyalari Universiteti.
    Algoritmlarni loyihalash fani boyicha

    Mustaqil ish 1
    s

    Bajardi:Rabbonayev Javoxir




    MAVZU: Graflarni eniga va boyiga aylanish

    Graflar bilan ishlash algoritmlari. Yo’llar va bog’liqliklar.


    Graflar bilan ishlash algoritmlarini loyihalash.
    Reja:
    1. Graflar haqida tushuncha.
    2. Deykstra algoritmi
    3. Bellman-Ford algoritmi.
    4. Floyd-Yolshel algoritmi.
    Graflar
    Graf – bu tugunlar va qirralar (tugunlar juftligini birlashtiruvchi) to’plamidan iborat bo’lgan abstrakt matematik ob’ektdir.

    Grafning elementlari tarkibi va munosabatlar tuzilishi beriladi. Grafning tarkibiy qismlari bu uning tugunlari va qirralaridir.

    Tarmoq
    Bir nechta juft tugunlararo qirralardan iborat bo’lgan turlicha yo’llar to’plami mavjud bo’lishi mumkin. Yopiq yo’llar – sikllarning mavjud bo’lishi tarmoqlarga xos xususiyatdir.


    Yonaltirilmagan graf yoki simmetrik bog’liqlik

    Yonaltirilmagan graf yoki nosimmetrik bog’liqlik



    qirra yoylar
    Ilmoq – aynan bitta tugundan chiqib, yana shu tugunga kiruvchi qirra.

    Deykstra algoritmi
    Gollandiyalik olim Edsger Deykstra algoritmi grafning boshlang’ich berilgan tugunidan boshlab qolgan barcha tugunlargacha bo'lgan barcha eng qisqa yo'llarni topadi. Uning yordamida, agar barcha zarur ma'lumotlar berilgan bo'lsa, masalan, neft va shu kabi mahsulotlarni eksport qilish uchun bitta shahardan boshqa shaharlarning har biriga borish uchun qaysi yo'llar ketma-ketligini tanlash afzalroq ekanligini bilib olish mumkin. Ushbu usulning salbiy tomoni shundaki, manfiy vaznga ega bo’lgan qirralari mavjud bo'lgan graflarni qayta ishlash imkonining mavjud emasligi, ya'ni, masalan, ba'zi tizim birorta kompaniya uchun foydasiz bo'lgan marshrutlarni taqdim qilsa, u holda u bilan ishlash uchun Dijkstraning algoritmidan foydalanib bo’lmaydi.
    Algoritmni dasturiy ta'minotini amalga oshirish uchun ikkita massiv kerak bo'ladi: mantiqiy toifadagi visited - tashrif buyurilgan tugunlar haqidagi ma'lumotlarni saqlash uchun va topilgan eng qisqa yo'llar kiritiladigan butun toifadagi - distance. G={V,E} graf berilgan bo’lsin. V to’plamga tegishli barcha tugunlar dastlab tashrif buyurilmagan deb belgilanadi, ya’ni visited massivining elementlariga false qiymat berib chiqiladi. Eng afzal yo’lni topish masalasi qaralyapti. Distance massivining har bir elementiga shunday qiymat beriladiki, ixtiyoriy potensial yo’ldan katta bo’lsin (odatda, bu qiymatni cheksiz katta qiymat deb qaraladi, ammo dasturda berilgan toifaning qiymatlar diapazonidagi eng katta qiymat sifatida olinadi). Boshlang'ich nuqta sifatida s tugun tanlanadi va unga nol yo'l belgilanadi: distance [s] = 0, chunki s-dan s-gacha hech qanday qirra yo'q (bu usulda ilmoqlar qaralmaydi).
    Shundan keyin, barcha qo'shni tugunlar topiladi (s dan chiquvchi qirralar orqali) [ularni t va u deb belgilaylik] va ular birma-bir tekshirib ko'riladi, ya'ni s tugundan har bir tugungacha birma-bir marshrut bahosi hisoblanadi:
    - distance[t]=distance[s]+ s va t orasidagi qirraning vazni;
    - Distance[u]=distance[s]+ s va u orasidagi qirraning vazni.
    Ehtimoldan xoli emaski, u yoki bu tugunga s dan bir qancha yo’llar bo’lishi mumkin. Shu sababli, distance massivida bu tugunga bo’lgan yo’lning vaznini qayta ko’rib chiqish kerak bo’ladi. Shunda kattaroq (nooptimal) qiymat yo’qotiladi va tugunga mos yo’lning vazniga kichikroq qiymat beriladi. s tugun bilan qo’shni bo’lgan va qarab chiqilgan tugunlar tashrif buyurilgan sifatida belgilab chiqiladi, yani visited[s]=true va natijada, s dan chiquvchi, minimal vaznga ega bo’lgan yo’l eltuvchi tugun faol element sifatida belgilab olinadi. Faraz qilamiz, s dan u gacha masofa t ga qaraganda qisqa bo’lsin. Kelib chiqadiki, u tugun faollashadi va yuqoridagi kabi uning qo’shnilari ( s dan tashqari) o’rganilib chiqiladi. u tugun tashrif buyurilgan deb belgilanadi: visited[u]=true, endi t tugun faollashadi va yuqoridagi prosedura uning uchun takrorlanadi. Deykstra algoritmi s tugundan borish mumkin bo’lgan barcha tugunlar tadqiq qilinmaguncha davom ettiriladi.

    Download 239.93 Kb.
      1   2   3   4




    Download 239.93 Kb.

    Bosh sahifa
    Aloqalar

        Bosh sahifa



    Mustaqil ish 1 s Bajardi: Rabbonayev Javoxir mavzu: Graflarni eniga va boyiga aylanish

    Download 239.93 Kb.