Fanidan mavzusida

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.