“Floyd algoritmi” mavzusidagi

To'lqin algoritmi.

Kenglik qidiruviga asoslangan bu ortiqcha algoritm ikki bosqichdan iborat:

1. 
   to'lqin tarqalishi;
   
2. 
   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.