Kampyuter injinering

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.