Mustaqil ishi Mavzu

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.