Mustaqil ishi Mavzu

Muhammad Al-Xorazmiy nomidagi Toshkent axborot texnologiyalari universiteti

Fan nomi: Algoritmlarni loyihalash



Mustaqil ishi

Mavzu: Eng qisqa yo'llarini topish algoritmlari.

CAL020 guruh talabasi

Bajardi:XakimovXojiakbar

Tekshirdi:Ishmuhamedov A.

Reja:

1. 
   Floyd Algoritmi eng qisqa yo'llarini topish algoritmlari haqida tushuncha .
   
2. 
   Eng qisqa yo'llarini topish algoritmlari misollar.
   
3. 
   Xulosa
   
4. 
   Foydalanilgan adabiyotlar ro’yhati.
   

Floyd Algoritmi

Ushbu algoritm ba'zan Floyd-Warshell algoritmi deb ataladi. Floyd-Warshell algoritmi 1962da Robert Floyd va Stiven Uorchell tomonidan ishlab chiqilgan graflarda algoritmdir. Grafning barcha juftlari orasidagi eng qisqa yo'llarni topishga xizmat qiladi. Floyd usuli to'g'ridan-to'g'ri qovurg'alarning ijobiy og'irliklari bo'lgan ustunda, har qanday elementar bo'lmagan (1 qovurg'asidan ko'prog'ini o'z ichiga olgan), eng qisqa yo'l boshqa eng qisqa yo'llardan iborat. Ushbu algoritm Dijkstra algoritmiga nisbatan ancha keng tarqalgan, chunki u har qanday ikki ustun o'rtasida eng qisqa yo'llarni topadi.

Floyd algoritmida eng qisqa yo'llarning uzunligi hisoblangan NxN matritsasi ishlatiladi. A[i,j] elementi, agar u erda chekka (i, j) bo'lsa,yakuniy qiymatga ega bo'lgan va aks holda abadiylikka teng bo'lgan j ning yuqori qismidan masofaga teng.

Floyd Algoritmi

Algoritmning asosiy g'oyasi. I, j, k ning uchta tepasi bor va ular orasidagi masofa belgilanadi. Agar tengsizlik a[i,k]+a[k,j]j yo'lini i->k->j bilan almashtirish tavsiya etiladi. Qadam 0. A0 masofasining dastlabki matritsasini va S0 vertexlarining ketma-ketligini aniqlang. Har ikkala matritsaning har bir diagonali elementi 0ga teng, shuning uchun bu elementlarning hisob-kitoblarda ishtirok etmasligini ko'rsatmoqda. K = 1 ga ishonamiz.

Asosiy qadam k. k satrini va k ustunini etakchi satr va etakchi ustun sifatida belgilang. Yuqorida tavsiflangan AK-1 matritsasining barcha elementlariga[i, j] almashtirishni ko'rib chiqamiz. Agar tengsizlik a[i,k]+a[k,j]

A[i,k]+a[k,j] miqdori uchun A[i,j] elementining Ak-1 matritsasini almashtirish orqali Ak matritsasini yarating] ;

k ga SK-1 element s[i,j] matritsasini almashtirish orqali Sk matritsasini yarating.

Shunday qilib, Floyd algoritmi n yinelemelerini qiladi, a matritsasining i-yinelemesinden keyin, bu yo'llar birinchi dan i-chigacha bo'lgan tepaliklardan o'tishi sharti bilan, har qanday ikki juftlik orasidagi eng qisqa yo'llarning uzunligini o'z ichiga oladi. Har bir iteratsiya bo'ylab barcha juftlar ko'chib o'tadi va ularning orasidagi yo'l i-tepa yordamida kamayadi ( misol 45.2).

Misol 45.2. Floyd algoritmini namoyish qilish

// Floyd algoritm funktsiyasi tavsifi

void Floyd(int n, int **Graph, int **ShortestPath){

int i, j, k;

int Max_Sum = 0;

for ( i = 0 ; i < n ; i++ )

for ( j = 0 ; j < n ; j++ )

Max_Sum += ShortestPath[i][j];

for ( i = 0 ; i < n ; i++ )

for ( j = 0 ; j < n ; j++ )

if ( ShortestPath[i][j] == 0 && i != j )

ShortestPath[i][j] = Max_Sum;

for ( k = 0 ; k < n; k++ )

for ( i = 0 ; i < n; i++ )

for ( j = 0 ; j < n ; j++ )

if ((ShortestPath[i][k] + ShortestPath[k][j]) <

ShortestPath[i][j])

ShortestPath[i][j] = ShortestPath[i][k] +

ShortestPath[k][j];

}

Agar grafik yo'naltirilmagan bo'lsa, unda transformatsiyalar natijasida olingan barcha matritsalar nosimmetrik bo'lib, shuning uchun faqat asosiy diagonaldan yuqorida joylashgan elementlarni hisoblash kifoya.

Agar grafik qo'shni matritsasi bilan ifodalangan bo'lsa, unda bu algoritmning ishlash vaqti o(n3) buyrug'iga ega, chunki u bir-biriga biriktirilgan uchta tsiklni o'z ichiga oladi.

Haddan tashqari algoritmlar

Bulkhead algoritmlari, odatda, optimal yechim topish uchun qidiruv algoritmlari. Shu bilan birga, yechim asta-sekin ishlab chiqilgan. Bunday holda, odatda, daraxt variantlarining ustunlarini qidirish haqida gap boradi. Bunday ustunning tepalari oraliq yoki yakuniy variantlar bo'ladi va qovurg'alar variantlarni loyihalash yo'llarini ko'rsatadi.Labirintdagi eng qisqa yo'lni topish vazifasi misolida ustundagi qidiruv usullariga asoslangan juda ko'p algoritmlarni ko'rib chiqing.

Muammo bayonoti.

O'tish va o'tkazilmaydigan hujayralardan tashkil topgan labirint mxn o'lchamli a matritsasi bilan berilgan. Agar hujayra (i,j) o'tkazilsa, matritsaning elementi a[i,j]=0. Aks holda, a [i,j]=\infty.Hujayradagi (1, 1) hujayradagi (m, n) eng qisqa yo'lning uzunligini topish kerak.Aslida, qo'shni matritsa berilgan (faqat nollar abadiylik bilan almashtiriladi va birliklar nolga teng). Labirint-bu grafik.Ushbu vazifadagi variantlar daraxtining tepalari qafada boshlangan yo'llardir (1, 1). Qovurg'alar-bu yo'llarning dizayni yo'lini ko'rsatadi va k va k+1 uzunliklarining ikki yo'lini birlashtiradi, bu erda ikkinchi yo'l yana bir harakatning yo'lini birinchi marta qo'shib olinadi.

Qaytish bilan qidirish.

Ushbu usul chuqur qidirish uslubiga asoslangan. Qaytish bilan qidirish sinov va xato usuli hisoblanadi ("keling, bu yo'nalishda borishga harakat qilaylik – bu ishlamaydi - qaytib keling va boshqasiga harakat qilaylik"). Variantlarni qidirish chuqur qidirish usuli bilan amalga oshirilganligi sababli, algoritm ish paytida daraxtdagi joriy yo'lni saqlash tavsiya etiladi. Bu yo'l bir yo'l suyakka hisoblanadi.Bundan tashqari, bir qator Distga ehtiyoj bor, uning o'lchami grafikaning vertikalari soniga mos keladi, bu har bir Vertex uchun dastlabki tepadan masofani saqlaydi.

Hozirgi hujayra (algoritm boshida – hujayra (1, 1) ). Agar hozirgi hujayra uchun qo'shni qo'shni qo'shni bo'lsa, u yo'lda hali bormagan yo'lda yo'q bo'lsa, unda biz yo'lda qo'shni qo'shamiz va hozirgi hujayradan qo'shni tayinlaymiz, aks holda yo'lni olib tashlaymiz.

Yuqoridagi tavsif, bu usulning nima uchun qaytib kelishi bilan busting deb atalishini aniq ko'rsatib beradi. Qaytish bu erda "Way out Way" operatsiyasi bilan mos keladi, bu esa yo'l uzunligini 1ga kamaytiradi.

Bulkhead bo'sh va orqaga qaytish uchun harakat qilganda tugaydi. Bunday holatda qaytib kelish uchun hech qanday joy yo'q.

Way joriy yo'l, lekin ish jarayonida optimal yo'lni saqlash kerak. Algoritmni takomillashtirish quyidagicha amalga oshirilishi mumkin: yo'lning uzunligi OptimalWay uzunligidan kattaroq yoki teng bo'lishiga yo'l qo'ymang. Bunday holda, agar biror variant topilsa, u albatta maqbul bo'lmaydi. Umuman olganda, bunday takomillashtirish, hozirgi yo'l aniq bo'lmagan optimal holga kelganda, biz orqaga qaytishimiz kerak degan ma'noni anglatadi. Algoritmning bu yaxshilanishi ko'p hollarda bustni sezilarli darajada kamaytirishga imkon beradi.

To'lqin algoritmi.

Kenglik qidiruviga asoslangan bu ortiqcha algoritm ikki bosqichdan iborat:

to'lqin tarqalishi;

teskari harakat.

To'lqinning tarqalishi va hujayralar tashrif buyuradigan usulning qadam raqami bilan belgilanadigan kenglikdagi qidiruv mavjud. Qaytish jarayonida, oxirgi tepadan boshlab, minimal belgilar bilan hujayralarni kiritish yo'li bilan unga kiritilgan yo'lni tiklash (misol 45.4). Muhim xususiyat shundaki, tiklanish oxiridan boshlanadi (boshidan bu ko'pincha mumkin emas).

Misol 45.4. To'lqin algoritmini namoyish qilish

Qidiruv usuli bilan kenglikda qidirish, odatda, ma'lumotni saqlash uchun zarur bo'lgan qo'shimcha xotirani talab qiladi, bu esa teskari yo'nalishda yo'lni qurish va tashrif buyurilgan tepaliklarni belgilash uchun zarurdir. Biroq, u tezroq ishlaydi, chunki u bir xil hujayradan bir martadan ko'proq tashrif buyurishdan butunlay chiqarib tashlanadi.

Asosiy shartlar

Dijkstra algoritmi grafning tepalaridan biriga eng qisqa yo'lni topish uchun algoritm bo'lib, u faqat salbiy og'irlikdagi qovurg'alarsiz grafikalar uchun ishlaydi.

Floyd algoritmi grafning har qanday ikki uchi orasidagi eng qisqa yo'lni topish uchun algoritmdir.

To'lqin algoritmi-kenglikdagi qidiruvga asoslangan va ikki bosqichdan iborat: to'lqinning tarqalishi va teskari harakat.Eng qisqa yo'l-bu ustundagi yo'l, ya'ni ikki qo'shni tepalikda va uning uzunligi bilan bog'liq bo'lgan tepaliklar va qovurg'alar ketma-ketligi.

Bulkhead algoritmi-grafikani chetlab o'tish algoritmi, bu mumkin bo'lgan yo'llarning ketma-ket izlanishiga asoslangan.

Qisqa natijalar:

Bugungi kunda eng qisqa yo'lni topish dolzarb vazifadir.

Graflarda eng qisqa yo'lni topishning eng samarali algoritmlari Dijkstra algoritmi, Floyd algoritmi va Bulkhead algoritmlarini o'z ichiga oladi. Ushbu algoritmlar juda oz sonli vertikalar uchun samarali.

Dijkstra algoritmini amalga oshirishda dastlabki tepadan eng qisqa yo'llar allaqachon ma'lum bo'lgan ko'plab vertikalar qurilgan. Quyidagi qadamlar optimal yo'llarning uzunligini saqlab, mavjud bo'lgan to'siqlarga bir tepalikka qo'shilishga asoslangan.

Dijkstra algoritmining murakkabligi vertikani topish usuliga, shuningdek, ko'plab turg'un cho'qqilarni saqlash usuli va uzunliklarni yangilash usuliga bog'liq.

Floyd usuli, qovurg'alarning ijobiy og'irliklari bo'lgan ustunda, har qanday elementar bo'lmagan eng qisqa yo'l boshqa eng qisqa yo'llardan iboratligiga asoslanadi.

Agar grafik qo'shni matritsasi bilan ifodalangan bo'lsa, Floyd algoritmining ishlash vaqti o(n3) tartibiga ega.

Bulkhead algoritmlar optimal yechim topish uchun algoritmlar bor.

To'lqin algoritmi kenglikdagi qidiruvga asoslangan va ikki bosqichdan iborat: to'lqin tarqalishi va teskari harakat.

Keng qidirish usuli bilan qidirish, qaytib kelish bilan solishtirganda, ma'lumotni saqlash uchun ko'proq yordamchi xotira talab qiladi, biroq u tezroq ishlaydi, chunki bir xil tepalikka bir martadan ko'proq tashrif buyurilmaydi.

Xulosa:

Men ushbu Mustaqil ishini bajarish mobaynida eng qisqa yo'llarini topish algoritmlarini bu yo’llar kimlar tomonida oylab topilganini bu yo’llarni nima sababdan oylab topilganini bu yo’llarni turlarini o’rgandim.

Foydalanilgan adabiyotlar:

1. 
   Абрамов С.А. Лекции о сложности алгоритмов.- М.: МЦНМО, 2009.- 256 с.
   
2. 
   Дональд Кнут Искусство программирования, том 1. Основные алгоритмы— 3-е изд. — М.: «Вильямс», 2006. — С. 720.
   
3. 
   Кнут В. Искусство программирования. Т.3. Сортировка и поиск. – 2-е изд. - Издательский дом “Вильямс”, 2000.
   
4. 
   Вирт Н. Алгоритмы и структуры данных. Пер. с англ. – М.: Мир, 1989. – 360.
   
5. 
   Носов В.А. Основы теории алгоритмов и анализа их сложности. – М., 1992.