Ma'lumotlar tuzilmalarida orqaga qaytish algoritmi

Ma'lumotlar tuzilmalarida orqaga qaytish algoritmi

Orqaga qaytish - bu shafqatsiz kuchlar yondashuvini takomillashtirish. U barcha mavjud variantlar orasida muammoning echimini izlashga harakat qiladi. U yechimni bosqichma-bosqich ishlab chiqish, vaqt o'tishi bilan darajalarni oshirish, rekursiv chaqiruvdan foydalanish orqali yechim to'plamini topadi.

Olib ketishlar

Backtracking - bu ba'zi hisoblash muammolariga, xususan, cheklovni qondirish muammolariga yechim topish uchun umumiy algoritm bo'lib, bu yechimga nomzodlarni bosqichma-bosqich quradi.

Backtracking algoritmiga kirish

• 
  Orqaga qaytishda biz har doim mavjud bo'lgan ko'plab variantlardan bitta mumkin bo'lgan tanlovdan boshlaymiz va muammoning yechimini topishga harakat qilamiz, agar tanlangan harakat bilan yechimni topa olsak, keyin yechimni chop etamiz, aks holda biz orqaga qaytamiz va ba'zilarini tanlaymiz. boshqa variantni tanlang va muammoni hal qilishga harakat qiling.
  
• 
  Bu bizga shafqatsiz kuch yondashuvi ko'rib chiqilishi mumkin bo'lmagan sonli tanlovlarga olib keladigan vaziyatlarni hal qilishga imkon beradi. Shunday qilib, har bir tugundagi orqaga qaytish algoritmida biz mumkin bo'lmagan variantlarni yo'q qilishga harakat qilamiz va faqat yechimga hissa qo'shishi mumkin bo'lgan tanlovlarni rekursiv tekshirish uchun davom etamiz.
  

Backtracking algoritmlari qanday ishlaydi?

Backtracking - bu dasturlarni rekursiv hal qilish usuli. Muammolarni orqaga qaytarishda siz bir nechta variantlarga ega bo'lasiz va siz ushbu variantlardan birini tanlashingiz kerak. Tanlovni amalga oshirganingizdan so'ng, siz yangi variantlar to'plamini o'rganasiz, agar siz ushbu tanlovlar orqali mumkin bo'lgan yechimga erishsangiz, echimni chop etasiz, aks holda siz orqaga qaytib, yechimga olib kelishi mumkin bo'lgan boshqa yo'llar va tanlovlarni o'rganish uchun qaytasiz.
Masalan: Quyidagi fazo holati daraxtini ko'rib chiqing. Quyidagi kosmik holat daraxti yordamida orqaga qaytish algoritmi aslida qanday ishlashini tushunamiz.

Biz muammomizning boshlang'ich nuqtasi bo'lgan S dan boshlaymiz. Biz X1 oraliq nuqtasidan Y1 ga yechim topishga boramiz va keyin Y1 muammomizning mumkin bo'lgan yechimi emasligini aniqlaymiz, shuning uchun biz orqaga qaytamiz va Y1 orqali X1 ga qaytamiz, so'ngra S ga qaytamiz va yana amalga oshirilishi mumkinligini aniqlashga harakat qilamiz. S->X2->Y2 boshqa yo'lni bo'ylab hal qilish va yana biz Y2 amalga oshirish mumkin emasligini topamiz, shuning uchun biz Y2->X2->S yo'li bo'ylab yana S ga qaytamiz va oxir-oqibat amalga oshirish mumkin bo'lgan yo'lga erishamiz. Y3 yechim S->X3->Y3 yo'li bo'ylab . Shunday qilib, biz orqaga qaytish algoritmini quyidagicha umumlashtirishimiz mumkin:

1. 
   Biz bitta mumkin bo'lgan yo'lni tanlaymiz va mumkin bo'lgan yechimni topish sari olg'a intilamiz.
   
2. 
   Agar biz yechim tomon harakat qila olmaydigan nuqtaga erishsak, biz orqaga qaytamiz.
   
3. 
   Yana boshqa mumkin bo'lgan yo'llarni kuzatib, mumkin bo'lgan yechimni topishga harakat qilamiz.