|
Haddan tashqari algoritmlar
|
| bet | 2/4 | | Sana | 25.11.2022 | | Hajmi | 128.09 Kb. | | #31757 |
Bog'liq Mamasoiyev Farxod Diskret tuzilmalari maruza[1]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.
|
| |
