Muhammad al xorazmiy nomidagi toshkent axborot texnologiyalari universiteti qarshi filiali

MUHAMMAD AL XORAZMIY NOMIDAGI TOSHKENT AXBOROT TEXNOLOGIYALARI UNIVERSITETI
QARSHI FILIALI

“TT VA KT” fakulteti “AKT” yo’nalishi

2-bosqich 11-20 guruh talabasining


5-MUSTAQIL ISHI

BAJARDI: Nomozova.D

QABUL QILDI: A.RAVSHANOV

Mavzu: Prima-Deykstraalgoritmi. Univaqtbo`yichabaholash.
Reja:
1.Prima-Deykstra algoritmi. Univaqtbo`yichabaholash.
2. Ajratvahukumronlikqiltipidagialgortimlar.
3.P va NP sinflar , NP –to`liqmasalalartushunchasi.
Prim algoritmi og'irlikdagi bog'langan yo'naltirilmagan grafikning minimal oraliqli daraxtini qurish algoritmidir. Algoritm birinchi marta 1930 yilda chex matematigi Voytsex Jarnik tomonidan kashf etilgan, keyinchalik Robert Prim tomonidan 1957 yilda va mustaqil ravishda 1959 yilda E. Diykstra tomonidan kashf etilgan.Algoritmning kiritilishi bog'langan yo'naltirilmagan grafikdir. Har bir chekka uchun uning narxi belgilanadi.Birinchidan, ixtiyoriy cho'qqi olinadi va bu cho'qqiga tushadigan va eng kam xarajatga ega bo'lgan chekka topiladi. Topilgan chekka va u bilan bog'langan ikkita cho'qqi daraxtni hosil qiladi. Keyin, grafikning qirralari ko'rib chiqiladi, ularning bir uchi allaqachon daraxtga tegishli cho'qqi, ikkinchisi esa yo'q; bu qirralardan eng kam xarajat chekkasi tanlanadi. Har bir qadamda tanlangan chekka daraxtga qo'shiladi. Daraxt dastlabki grafikning barcha uchlari tugamaguncha o'sadi. Algoritmning natijasi minimal xarajatlarni qamrab oluvchi daraxtdir.
Daraxtni yoyish uchun Prim algoritmi
Onlayn o'yinlarni ishlab chiquvchilar va Internet-radio provayderlari tez-tez duch keladigan muammoni ko'rib chiqish uchun grafiklar bo'yicha oxirgi algoritmimizni taklif qilamiz. Muammo shundaki, ular ma'lumot paketlarini har kimga va uni eshitadigan har bir kishiga samarali yetkazib berishlari kerak. Bu o'yinlarda muhim, chunki barcha o'yinchilar ularning har birining oxirgi harakatini bilishlari kerak. Bu internet radiosi uchun juda muhim, chunki unga sozlangan tinglovchilar tinglayotgan qoʻshiqni qayta yaratish uchun zarur boʻlgan barcha maʼlumotlarga ega boʻlishi kerak.

Algoritm ko'p variantlarda mavjud. Dijkstraning asl algoritmi ikkita berilgan tugun oʻrtasidagi eng qisqa yoʻlni topdi, lekin keng tarqalgan variant bitta tugunni “manba” tugun sifatida oʻrnatadi va manbadan grafikdagi barcha boshqa tugunlarga eng qisqa yoʻllarni topib, eng qisqa yoʻlni hosil qiladi.Grafikdagi ma'lum bir manba tugun uchun algoritm ushbu tugun va boshqa tugunlar orasidagi eng qisqa yo'lni topadi. Bundan tashqari, to'xtash orqali bitta tugundan bitta maqsad tugungacha bo'lgan eng qisqa yo'llarni topish uchun ham foydalanish mumkin. maqsad tugunga eng qisqa yo'l aniqlangandan keyin algoritm. Misol uchun, agar grafikning tugunlari shaharlarni va chekka yo'l xarajatlari to'g'ridan-to'g'ri yo'l bilan bog'langan juft shaharlar orasidagi harakat masofalarini ifodalasa (oddiylik uchun qizil chiroqlar, to'xtash belgilari, pullik yo'llar va boshqa to'siqlarga e'tibor bermang), Dijkstra algoritmidan foydalanish mumkin. bir shahar va boshqa barcha shaharlar orasidagi eng qisqa yo'lni topish. Eng qisqa yo'l algoritmlarining keng qo'llaniladigan qo'llanilishi tarmoq marshrutlash protokollari, ayniqsa IS-IS (Oraliq tizimdan oraliq tizimga) va OSPF (Ochiq eng qisqa yo'l birinchi) hisoblanadi. Shuningdek, u Jonson algoritmi kabi boshqa algoritmlarda subprogramma sifatida ishlatiladi.
Biz boshlayotgan tugunni boshlang‘ich tugun deb ataymiz. Y tugunning masofasi boshlang'ich tugundan Y.gacha bo'lgan masofa bo'lsin. Deykstra algoritmi dastlab cheksiz masofalardan boshlanadi va ularni bosqichma-bosqich yaxshilashga harakat qiladi.

1. 
   Barcha tugunlarni ko'rilmagan deb belgilang. Ko'rilmagan to'plam deb ataladigan barcha ko'rilmagan tugunlar to'plamini yarating.
   
2. 
   Har bir tugunga taxminiy masofa qiymatini belgilang: uni boshlang'ich tugunimiz uchun nolga va boshqa barcha tugunlar uchun cheksizga qo'ying. V tugunining taxminiy masofasi v tugun va boshlang'ich tugun o'rtasida aniqlangan eng qisqa yo'lning uzunligidir. Dastlab manbaning o'zidan boshqa cho'qqilarga hech qanday yo'l ma'lum bo'lmagani uchun (bu nol uzunlikdagi yo'l), boshqa barcha taxminiy masofalar dastlab cheksizlikka o'rnatiladi. Dastlabki tugunni joriy sifatida o'rnating.[15]
   
3. 
   Joriy tugun uchun uning barcha ko'rilmagan qo'shnilarini ko'rib chiqing va joriy tugun orqali ularning taxminiy masofalarini hisoblang. Yangi hisoblangan taxminiy masofani hozirda qo'shniga tayinlangan masofa bilan solishtiring va uni kichikroq qilib belgilang. Misol uchun, agar joriy tugun A 6 masofa bilan belgilangan bo'lsa va uni qo'shni B bilan bog'laydigan chekka 2 uzunlikka ega bo'lsa, u holda A dan B gacha bo'lgan masofa 6 + 2 = 8 bo'ladi. Agar B ilgari bilan belgilangan bo'lsa. masofa 8 dan katta bo'lsa, uni 8 ga o'zgartiring. Aks holda, joriy qiymat saqlanadi.
   
4. 
   Joriy tugunning barcha ko'rilmagan qo'shnilarini ko'rib chiqishni tugatgandan so'ng, joriy tugunni tashrif buyurilgan deb belgilang va uni tashrif buyurilmagan to'plamdan olib tashlang. Tashrif buyurilgan tugun boshqa hech qachon tekshirilmaydi (bu 6-bosqichdagi xatti-harakatlar bilan bog'liq holda to'g'ri va maqbuldir: keyingi tashrif buyuriladigan tugunlar har doim "birinchi tugundan eng kichik masofa" tartibida bo'ladi, shuning uchun keyingi tashriflar kattaroq masofaga ega).
   
5. 
   Agar maqsad tugun tashrif buyurilgan bo'lsa (ikkita aniq tugunlar orasidagi marshrutni rejalashtirishda) yoki ko'rilmagan to'plamdagi tugunlar orasidagi eng kichik taxminiy masofa cheksizlik bo'lsa (to'liq o'tishni rejalashtirganda; boshlang'ich tugun o'rtasida aloqa bo'lmaganda sodir bo'ladi) va qolgan ko'rilmagan tugunlar), keyin to'xtating. Algoritm tugadi.
   
6. 
   Aks holda, eng kichik taxminiy masofa bilan belgilangan tashrif buyurilmagan tugunni tanlang, uni yangi joriy tugun sifatida o'rnating va 3-bosqichga qayting.