Maslaning qo’yilishi



Download 109,5 Kb.
bet1/3
Sana31.12.2021
Hajmi109,5 Kb.
#232033
  1   2   3
Bog'liq
4-misol


912-19 guruh talabasi

Karimov Doston
9-Laboratoriya ishi

Mavzu: Bir uchdan boshqa uchlarga boradigan eng qisqa yo’llar.

Maslaning qo’yilishi


n ta uchli va m ta qirraga ega bo’lgan orietrlangan yoki orintrlanmagan graf berilgan. Qandaydir boshlang’ich uch ko’rsatilgan. uchdan boshqalarigacha bo’lgan eng qisqa masofalarni toppish kerak va yo’lning o’zinin ham chiqarish talab etiladi.

Bu masala “yagona manbaali eng qisqa yo’llarni izlash masalasi” (single-source shortest paths problem) deyiladi.


Algoritm


Bu yerda Daniyalik tadqiqodchi Deykstra (Dijkstra) tamonidan 1959 yilda ishlab chiqilgan algoritm ko’rib tavsifnalgan.

Harbir uch uchun ungacha bo’lgan eng qisqa masofani belgilovchi massiv kiritamiz. Dastlab , boshqalari uchun esa uni qandaydir bir kata son bilan to’ldirib qo’yamiz. (Masalada bu uzunlik mavjud eng kata yo’l uzunligidan ham kata bo’ladigan shartni qanoatlantirishi kerak):



Undan tashqari harbir uch uchun uning ko’rilgani yoki ko’rilmaganini bildiruvhci matkiqiy(boolean) massiv kiritamiz.Dastlab barcha uchlar hali ko’rilmagan ya’ni:



Deyksta algoritmi ta iteratsiyadan iborat. Navbatdagi iteratsiyada kattalik eng kichik bo’lgan hali ko’rilmagan uch tanlanadi ya’ni:



(Birinchi iteratsiyada boshlang’ich uch ko’riladi).



Yo’lni tiklash. Bizdan faqat eng qisqa yo’lning uzunligi so’ralmasdan, balki bu yo’lnig o’zi ham ya’ni unga borishdagi qaysi uchlardan o’tish ketma-ketligi so’ralishi mumkin. uchdan boshqa uchlargacha yo’lni ketma-ket qanday tiklash mumkinligini ko’rsatamiz. Buning uchun predka massiv deb nomlanadigan massiv kiritamiz. Bu massiv harbir uch uchun kattalik uchga undan oldin qaysi uch orqali kelganligini bildiruvchi ma’lumot saqlasymiz. Bunda biz quyidagicha faktdan foydalanamiz. Agar biz qandaydir uchgacha bo’lgan eng qisqa yo’lni olib undan ohirgi uchni o’chirsak u holda bu uchdan oldingi uchda yakunlanadigan qandaydir yo’l hosil bo’ladi va bu yo’l uchun eng qisqa bo’ladi. Shunday qilib, agar biz predka massiv bo’yicha yurib borsak ohir oqibatda boshlang’ich uchga yetib boramiz. Bu esa butun bosib o’tilgan yo’lni tiklab olish imkoniyatini beradi. Lekin bu ketma-ketlikni teskari tartibda olishimiz kerak.Shunday qilib uchgacha bo’lga eng qisqa masofa quyidagiga teng: Bu predka massivni qanday qilib hosil qilishni tushinish qoldi. Lekin bu juda oddiy amalga oshiriladi: harbir relaksatsiyada uchdan uchgacha bo’lgan masofa yaxshilansa u holda u holda uchga uch orqali kelgan bo’ladi. Demak uchning predkasini uch qilib belgilab qo’yish mumkin.: Isbotlash

Asosiy tasdiq, Deykstra algoritmining to’g’riligi quyidagi tasdiq orqali tushintiriladi. Agar qandaydir uch ko’rilgan uchlar qatoriga kiritilsa u holda ungacha bo’lgan eng qisqa masofa allaqachon hisoblangan bo’ladi va u boshqa o’zgarmaydi.




Download 109,5 Kb.

Do'stlaringiz bilan baham:
  1   2   3




Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©hozir.org 2024
ma'muriyatiga murojaat qiling

kiriting | ro'yxatdan o'tish
    Bosh sahifa
юртда тантана
Боғда битган
Бугун юртда
Эшитганлар жилманглар
Эшитмадим деманглар
битган бодомлар
Yangiariq tumani
qitish marakazi
Raqamli texnologiyalar
ilishida muhokamadan
tasdiqqa tavsiya
tavsiya etilgan
iqtisodiyot kafedrasi
steiermarkischen landesregierung
asarlaringizni yuboring
o'zingizning asarlaringizni
Iltimos faqat
faqat o'zingizning
steierm rkischen
landesregierung fachabteilung
rkischen landesregierung
hamshira loyihasi
loyihasi mavsum
faolyatining oqibatlari
asosiy adabiyotlar
fakulteti ahborot
ahborot havfsizligi
havfsizligi kafedrasi
fanidan bo’yicha
fakulteti iqtisodiyot
boshqaruv fakulteti
chiqarishda boshqaruv
ishlab chiqarishda
iqtisodiyot fakultet
multiservis tarmoqlari
fanidan asosiy
Uzbek fanidan
mavzulari potok
asosidagi multiservis
'aliyyil a'ziym
billahil 'aliyyil
illaa billahil
quvvata illaa
falah' deganida
Kompyuter savodxonligi
bo’yicha mustaqil
'alal falah'
Hayya 'alal
'alas soloh
Hayya 'alas
mavsum boyicha


yuklab olish