Hozirgi kunda biror bir sohada ishni boshlash va uni boshqarishni kompyutersiz tasavvur qilish qiyin. XXI asr savodxon kishisi bo’lishi uchun kompyuter savodxon bo’lish, axborot texnologiyalarini puxta egallamoq lozim


- MAVZU: ENG QISQA YO’LLAR. DEYKSTRA ALGORITMI



Download 1,84 Mb.
bet14/76
Sana30.06.2022
Hajmi1,84 Mb.
#719156
1   ...   10   11   12   13   14   15   16   17   ...   76
Bog'liq
O’zbekiston oliy va o’rta

12 - MAVZU: ENG QISQA YO’LLAR. DEYKSTRA ALGORITMI.


Reja
1. Eng qisqa yo’llar masalalarining turlari.
1. Sozli algoritmni tuzish.
3. Algoritmni psevdokodda ishlab chiqish
4. Algoritmni baholash.
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.
Deykstra algoritmning so’zli tavsifi
Shunday masalalarni yechish uchun Deykstra algoritmi ancha qulay va yahshi deb topilgan.
Algoritm quyidagi qadamlardan iborat:

  1. Dastlab, berilgan (Lex) uchidan qolgan barcha uchlargacha bir qirra uzunligidagi masofalar aniqlanadi.

  2. Ulardan eng qisqasi “doimiy eng qisqa masofa” sifatida belgilanadi (Lex va BVa uchlari qirrasi).

  3. Aniqlangan masofa BVa dan boshqa bor uchlargacha masofalarga qo’shiladi.

  4. Hosil bo’lgan yig’indilar dastlab aniqlangan Lex dan qolgan uchlargacha bo’lgan masofalar bilan taqqoslanadi. Natijada masofasi qisqaroq bo’lgan uchning qirrasi tanlanadi.

  5. 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.
Rasm bo’yicha ikkinchi iteratsiyada Nbr uchi aniqlanadi va Roa gacha masofa 41 deb qabul qilinadi. Uchinchi iteratsiyada Gla uchigacha masofa eng qisqa va 27 deb qabul qilinadi. Quyidagi rasmda eng qisqa yo’llar daraxti ko’rinishida ularning natijaviy to’plami keltirilgan.
Aylanalar ichidagi sonlar algoritm bo’yicha qirralar tanlanish tartibini ko’rsatadilar. Bu daraxt bo’yicha biz Lex uchidan ixtiyoriy bizni qiziqtirayotgan uchgacha eng qisqa yo’lni topishimiz mumkin.
Ko’rilgan misolda Bed uchi Lex dan boshlab eng oxirgi bo’lib chiqdi, ya’ni Lex dan Bed gacha eng qisqa masofani topish uchun biz Lex dan barcha qolgan uchlargacha eng qisqa yo’llarni topishga majbur bo’ldik.
Demak, eng yomon holatda 2 ta berilgan uchlar orasidagi eng qisqa yo’lni topish, bir berilgan nuqtadan qolgan barcha nuqtalargacha eng qisqa yo’l topish masalasi bilan murakkabligi bir xil bo’ladi.
Algoritmni psevdokodda ishlab chiqish

  1. Masala qo’yilishi.


Download 1,84 Mb.

Do'stlaringiz bilan baham:
1   ...   10   11   12   13   14   15   16   17   ...   76




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