“Floyd algoritmi” mavzusidagi

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.