Mavzu: Floyd-Uorshell algoritmi



Download 86.9 Kb.
bet1/5
Sana10.04.2021
Hajmi86.9 Kb.
  1   2   3   4   5

Mustaqil ish

30-Variant

Mavzu: Floyd-Uorshell algoritmi

Bajardi:020-guruh talabasi

Khoshimov Elyor

Floyd-Varshl algoritmi



  • Algoritmlar

Floyd-Warshall algoritmi dinamik dasturlash usulidan foydalanib, salbiy og'irliklari bo'lgan tsikllarsiz o'lchangan grafikning barcha uchlari orasidagi eng qisqa masofani topish uchun algoritmdir . Bu asosiy algoritm, shuning uchun uni bilganlar bundan keyin o'qimasliklari kerak.

Bu algoritm bir vaqtning o'zida (Robert Floyd tomonidan maqolada chop etildi Robert Floyd tomonidan ) va Stiven Uorshella ( Stiven Warshall 1959 yilda bo'lsa-da, 1962 yilda), (Bernard Roy Rua Bernard ) deyarli bir xil algoritm e'lon qildi, lekin u ko'rinmagan ketdi.




Eslatma

Agar grafikda salbiy og'irlikdagi qirralar bo'lmasa, unda ushbu muammoni hal qilish uchun siz Dijkstra algoritmidan foydalanib , har bir verteksda ishlaydigan bitta vertexdan boshqasiga eng qisqa yo'lni topishingiz mumkin. Bunday algoritmning ishlash vaqti biz Dijkstra algoritmi uchun foydalanadigan ma'lumot turiga bog'liq, u oddiy ustuvor navbat yoki ikkilik yoki Fibonachchi uyasi bo'lishi mumkin , mos ravishda, ish vaqti O (V 3 ) dan O (V * E) gacha o'zgaradi. * log (V)), bu erda V - vertikallarning soni, E - qirralarning. ( "Oh" juda yaxshi ).

Salbiy og'irlikdagi qirralar bo'lsa , Bellman-Ford algoritmidan foydalanishingiz mumkin. Ammo grafikning barcha uchlarida ishlaydigan bu algoritm sekinroq, uning ishlash vaqti O (V 2 * E) va juda "qalin" grafiklarda esa O (V 4 ).


Dinamik dasturlash


Dinamik algoritm nimani anglatadi? Dinamik dasturlash muammolarni peshona usuli bilan, ya'ni qo'pol fork yoki ochko'z algoritmlar yordamida hal qilish uchun alternativa hisoblanadi . Dastlabki muammoni hal qilish uchun kichikroq hajmdagi eng maqbul echim ishlatilishi mumkin bo'lgan joyda qo'llaniladi. Umuman olganda, usul quyidagicha ko'rinadi:

1. Vazifani kichikroq pastki qismlarga bo'lish.
2. Subkastlar uchun eng maqbul echimni topish rekursivdir.
3. Olingan quyi chiziqlardan asl masalaga yechim qurish uchun foydalanish.

Grafikning barcha uchlari orasidagi eng qisqa yo'llarni topish uchun, bu barcha imkoniyatlarni sanab o'tmaydi, bu uzoqroq vaqtni talab qiladi va ko'proq xotirani talab qiladi, ammo yuqoriga qarab dinamik dasturlash, ya'ni dastlabki muammoni hal qilish uchun kerak bo'ladigan barcha pastki satrlar oldindan hisoblab chiqiladi va keyin ishlatiladi.


Qisqa yo'lning tuzilishi

Algoritm grafikning eng qisqa yo'lining ikkita xususiyatiga asoslanadi. Birinchi:

1k = (v 1 , v 2 , ..., v k ) eng qisqa yo'li v 1 verteksidan v k uchiga, shuningdek uning pastki pathi p '(v i , v i + 1 , ..., v j ), bu holda, 1 <= i <= j <= k.

P V qisqa yo'l bo'lsa 1 v uchun K , keyin R "uch V qisqa yo'l ham i v uchun j


Buni osonlikcha isbotlash mumkin, chunki p yo'lining qiymati p 'yo'lining qiymati va qolgan qismlarning qiymati yig'indisidir. Shunday qilib, p 'yo'li qisqa bo'lishini tasavvur qilsak, biz bu miqdorni kamaytiramiz, bu esa bu miqdor minimal bo'lgan degan gap bilan qarama-qarshilikka olib keladi.

Ikkinchi xususiyat algoritm asosidir. 1 dan n gacha bo'lgan {v 1 , v 2 , ..., v n } vertikallari bilan G grafini va k indeks bilan chegaralangan ma'lum ruxsat etilgan uchlardan o'tadigan p i v dan v j gacha bo'lgan yo'lni ko'rib chiqamiz .

Agar k = 0 bo'lsa, u holda vertikallarning bir-biriga to'g'ridan-to'g'ri bog'lanishini ko'rib chiqamiz, chunki ruxsat etilgan oraliq vertikallarning to'plami erta nolga teng. Agar k = 1 bo'lsa - v 1 uchidan o'tadigan yo'llarni , k = 2 - {v 1 , v 2 } uchlari orqali, k = 3 - {v 1 , v 3 , v 3 } va boshqalarni ko'rib chiqamiz .

Masalan, bizda shunday grafik bor (chapda) va k = 1, ya'ni oraliq tugun sifatida faqat "1" tuguniga ruxsat beriladi. Ushbu grafikda k = 1 uchun p 43 yo'l yo'q , lekin k = 2 uchun siz "4" dan "3" ga "2" yoki "1" va "2" orqali o'tishingiz mumkin.

Eng qisqa yo'lni ko'rib chiqing p ij ruxsat etilgan oraliq vertikal {1..k-1} qiymatga ega d ij. Endi biz to'plamni kth elementga uzaytiramiz, shunda ruxsat etilgan uchlari {1..k} bo'ladi. Bunday bir kengaytmasi bilan, 2 natijalar mumkin:




Download 86.9 Kb.

Do'stlaringiz bilan baham:
  1   2   3   4   5




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

    Bosh sahifa
davlat universiteti
ta’lim vazirligi
maxsus ta’lim
O’zbekiston respublikasi
axborot texnologiyalari
zbekiston respublikasi
o’rta maxsus
nomidagi toshkent
guruh talabasi
davlat pedagogika
texnologiyalari universiteti
xorazmiy nomidagi
toshkent axborot
pedagogika instituti
rivojlantirish vazirligi
haqida tushuncha
toshkent davlat
Toshkent davlat
vazirligi toshkent
samarqand davlat
tashkil etish
kommunikatsiyalarini rivojlantirish
ta’limi vazirligi
matematika fakulteti
navoiy nomidagi
vazirligi muhammad
bilan ishlash
fanining predmeti
nomidagi samarqand
Darsning maqsadi
maxsus ta'lim
pedagogika universiteti
ta'lim vazirligi
Toshkent axborot
o’rta ta’lim
Ўзбекистон республикаси
sinflar uchun
haqida umumiy
fanlar fakulteti
fizika matematika
Alisher navoiy
Ishdan maqsad
universiteti fizika
Nizomiy nomidagi
moliya instituti
таълим вазирлиги
nazorat savollari
umumiy o’rta
respublikasi axborot
Referat mavzu
махсус таълим