Ma'lumotlar tuzilmalarida orqaga qaytish algoritmi

Orqaga qaytish muammolarining turlari

Muammoni hal qilishni boshlashdan oldin, biz uni orqaga qaytish algoritmi yordamida hal qilish mumkinligini bilib olishimiz kerak. Backtracking yordamida hal qilinishi mumkin bo'lgan muammolarning quyidagi turlari mavjud:

1. 
   Qaror muammosi: Ushbu turdagi muammoda biz doimo mumkin bo'lgan yechimni qidiramiz.
   
2. 
   Optimallashtirish muammosi: Ushbu turdagi muammolarda biz har doim eng yaxshi echimni qidiramiz.
   
3. 
   Ro'yxatga olish muammosi: Ushbu turdagi muammolarda biz barcha mumkin bo'lgan echimlarni topishga harakat qilamiz.
   

Orqaga qaytish algoritmiga misol

Biz N Queen misolini muhokama qilamiz, bu juda mashhur muammo bo'lib, uni Backtracking yordamida hal qilish mumkin. N qirolicha muammosida biz N × N shaxmat taxtasiga N qirolichani joylashtirishimiz kerak, shunda ikkita malika bir-biriga hujum qilolmaydi. Hujumni oldini olish uchun biz ikkita malikani bir qatorga yoki bir ustunga yoki bir xil diagnolga joylashtira olmaymiz. Misol uchun, quyida N*N shaxmat taxtasiga N qirolichalarni joylashtirish konfiguratsiyasi berilgan, bu erda N=4 .



Chiqishda biz malika joylashtirilishi mumkin bo'lgan 1 larni o'z ichiga olgan ikkilik matritsani chop etamiz, qolgan barcha hujayralar esa 0 ni o'z ichiga oladi .

Yechim: Ushbu muammoni hal qilishda qo'pol kuch usuli bortda malikalarning barcha mumkin bo'lgan konfiguratsiyasini yaratish va keyin cheklovni qondiradigan konfiguratsiyani chop etishdir. Ammo bu yondashuvning vaqt murakkabligi eksponent bo'ladi, chunki biz barcha mumkin bo'lgan konfiguratsiyalarni yaratishimiz kerak. Ammo biz orqaga qaytish algoritmidan foydalanib, vaqt murakkabligini yaxshilashimiz mumkin.
Orqaga qaytish algoritmida biz eng chap ustundan boshlaymiz va birma-bir qirolichalarni turli ustunlarga joylashtirishga harakat qilamiz. Qirolichani ustunga qo'yganimizda, biz hozirda qo'ygan malika boshqa joylashtirilgan malika bilan to'qnashyaptimi yoki yo'qligini tekshiramiz. Joriy ustunda, agar biz malika joylashtirish xavfsiz bo'lgan qatorni topa olsak, biz ushbu qator va ustunni yechimning bir qismi sifatida belgilaymiz. Agar biz to'qnashuvlar tufayli bunday qatorni topmasak, biz orqaga qaytib, yolg'onni qaytaramiz. Keling, muammoni hal qilishning bosqichma-bosqich yondashuvini ko'rib chiqaylik.
1-qadam: Biz 1 -ustun va 1 -qatordan boshlaymiz va birinchi malikani C1R1 katakka joylashtiramiz . Bu malika boshqa qirolichalar bilan to'qnash kelmasligi sababli, biz malika 2 ni joylashtirish uchun keyingi bosqichga o'tamiz .
2-qadam: Endi biz 2 -ustunga o'tamiz va qator bir xil bo'ladi va biz malika 2 ni joriy katakchaga joylashtirishimiz mumkinligini tekshiring R1C2 . Bu qatorda allaqachon malika 1 bor, shuning uchun cheklovlar tufayli biz malikani bu qatorga joylashtira olmaymiz. Shunday qilib, biz keyingi qatorga o'tamiz va har bir ustunni sinab ko'ramiz. Biz qirolichani joylashtirish uchun keyingi xavfsiz hujayrani ko'ramiz 2 hujayra R2C3 .