|
Mustaqil ish
30-Variant
Mavzu: Floyd-Uorshell algoritmi
Bajardi:020-guruh talabasi
Khoshimov Elyor
Floyd-Varshl algoritmi
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:
p 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:
Do'stlaringiz bilan baham: | 
