Maslaning qo’yilishi



Download 118,59 Kb.
bet1/6
Sana07.07.2022
Hajmi118,59 Kb.
#753915
  1   2   3   4   5   6
Bog'liq
14 tajriba Bog’langan graflarda marshrutlar Xasis algoritmlar Eng (2)


14-Laboratoriya ishi
Mavzu: Bog’langan graflarda marshrutlar. Xasis algoritmlar. Eng qiska marshrutni aniqlash algoritmi. Uni variantlar soni bo’yicha xajmini baxolash.

Maslaning qo’yilishi


n ta uchli va m ta qirraga ega bo’lgan orietrlangan yoki orintrlanmagan graf berilgan. Qandaydir boshlang’ich uch s ko’rsatilgan. s 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).
Shunday usul bilan tanlangan uch ko’rilgan uchlar qaotiga kiritiladi. Undan so’n esa joriy iteratsiyada uchdan relaksatsiya tekshiriladi. Ya’ni barcha qirralar qarab chiqiladi va uch uchun qiymat yaxshilashtirishga uriniladi. Ko’rilayotgan qirraning uzunligi ga teng bo’lsin, u holda relaksatsiyani tekshirish quyidagicha bo’ladi:

Joriy iteratsiya yakunlangacha algoritm keying iteratsiyaga o’tadi(yana masofa eng kichik hali ko’rilmagan uch tanlanadi va undan relaksatsiya tekshiriladi va h.). Bunda iteratsiyadan keyin ohir-oqibatda grafning barcha uchi ko’rilgan bo’lib qoladi va algoritm o’z ishini yakunlaydi. qiymat uchdan uchgacha bo’lgan eng qisqa masofa bo’ladi.
Yana shuni eslatib o’tish kerakki uchdan mavjud yo’llar orqali borib bo’lmaydigan uchlar uchun qiymat cheksiz kattaligicha qoladi. Ma’lumki algoritmning ohirgi birnechta iteratsiyasida bu uchlar tanlanadi lekin hech qanday yaxshilanish sodir bo’lmaydi. Chinki cheksiz kata masofaga qirra uzunligini qo’shganda cheksiz kata sobdan kichik bo’lmaydi. Shuning uchun bu holda algoritmni darhol to’xtatish mumkin.

Download 118,59 Kb.

Do'stlaringiz bilan baham:
  1   2   3   4   5   6




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