Orqaga qaytish - Backtracking

Uchun chiziqlarni qidirish ichida ishlatiladigan algoritm cheklanmagan optimallashtirish, qarang Orqaga qarab chiziqlarni qidirish.
Grafik va daraxt
qidirish algoritmlari
Listinglar
Tegishli mavzular

Orqaga qaytish general algoritm ba'zilariga barcha (yoki ba'zi) echimlarni topish uchun hisoblash muammolari, ayniqsa cheklov qoniqish muammolari, bu bosqichma-bosqich nomzodlarni echimlarga asoslantiradi va nomzodning haqiqiy echimini topishi mumkin emasligini aniqlagandan so'ng nomzoddan voz kechadi ("backtracks").[1][2]

Backtracking-dan foydalanishda klassik darslik namunasi sakkiz qirolicha jumboq, bu sakkiztadan barcha tartiblarni so'raydi shaxmat malikalar standart bo'yicha shaxmat taxtasi hech bir malika boshqasiga hujum qilmasligi uchun. Umumiy orqaga chekinish yondashuvida qisman nomzodlar kelishuvlardir k birinchisida malikalar k taxtaning qatorlari, barchasi har xil qator va ustunlarda joylashgan. O'zaro hujum qiladigan ikkita malikani o'z ichiga olgan har qanday qisman echimdan voz kechish mumkin.

Backtracking faqat "nomzodning qisman echimi" tushunchasini tan oladigan muammolar uchun va amaldagi echim bilan yakunlanishi mumkinligini nisbatan tezroq tekshirishda qo'llanilishi mumkin. Masalan, tartibsiz jadvalda berilgan qiymatni topish uchun foydasiz. Amalga oshirilganda, orqaga qaytish ko'pincha nisbatan tezroq bo'ladi qo'pol kuchlarni hisoblash to'liq nomzodlarning barchasi, chunki bu bitta nomzod bilan ko'plab nomzodlarni yo'q qilishi mumkin.

Backtracking bu hal qilishning muhim vositasidir cheklov qoniqish muammolari,[3] kabi krossvordlar, og'zaki arifmetik, Sudoku va boshqa ko'plab boshqotirmalar. Bu ko'pincha eng qulay (agar u samarali bo'lmasa)[iqtibos kerak ]) uchun texnika tahlil qilish,[4] uchun xalta muammosi va boshqalar kombinatorial optimallashtirish muammolar. Bu, shuningdek, deb atalmish asosidir mantiqiy dasturlash kabi tillar Belgisi, Rejalashtiruvchi va Prolog.

Backtracking foydalanuvchi berganiga bog'liq "qora quti protseduralari "bu hal qilinadigan muammoni, qisman nomzodlarning mohiyatini va ularning to'liq nomzodlarga qanday kengayishini belgilaydi. Shuning uchun metaevistik ma'lum bir algoritmdan ko'ra - garchi, ko'plab boshqa meta-evristikalardan farqli o'laroq, cheklangan vaqt ichida cheklangan muammoning barcha echimlarini topish kafolatlangan.

"Orqaga qaytish" atamasi amerikalik matematik tomonidan kiritilgan D. X. Lemmer 1950-yillarda.[5] Kashshof satrlarni qayta ishlash tili SNOBOL (1962) birinchi bo'lib orqaga qaytish uchun ichki imkoniyatni taqdim etgan bo'lishi mumkin.

Usulning tavsifi

Orqaga qaytish algoritmi bir qatorni sanab chiqadi qisman nomzodlar bu, asosan, bo'lishi mumkin yakunlandi berilgan masalaga mumkin bo'lgan barcha echimlarni berishning turli usullari bilan. Tugatish bosqichma-bosqich amalga oshiriladi nomzodni kengaytirish bosqichlari.

Kontseptual ravishda qisman nomzodlar a tugunlari sifatida ifodalanadi daraxt tuzilishi, potentsial qidirish daraxti. Har bir qisman nomzod - bu bitta uzaytirish bosqichi bilan farq qiladigan nomzodlarning ota-onasi; daraxt barglari qisman nomzodlar bo'lib, ularni endi uzaytirish mumkin emas.

Orqaga qaytish algoritmi ushbu qidiruv daraxtidan o'tadi rekursiv, ildizdan pastga, ichida chuqurlik-birinchi tartib. Har bir tugunda v, algoritm yoki yo'qligini tekshiradi v haqiqiy echimga qadar to'ldirilishi mumkin. Agar buni qila olmasa, butun pastki daraxt ildiz otadi v atlanmoqda (kesilgan). Aks holda, algoritm (1) yoki yo'qligini tekshiradi v o'zi to'g'ri echim bo'lib, agar shunday bo'lsa, bu haqda foydalanuvchiga xabar beradi; va (2) rekursiv ravishda barcha pastki daraxtlarni sanab chiqadi v. Ikkala test va har bir tugunning farzandlari foydalanuvchi tomonidan berilgan protseduralar bilan belgilanadi.

Shuning uchun haqiqiy qidiruv daraxti algoritm orqali o'tadigan potentsial daraxtning faqat bir qismidir. Algoritmning umumiy qiymati bu har bir tugunni olish va qayta ishlash xarajatlaridan haqiqiy daraxt tugunlarining soni. Ushbu haqiqat potentsial qidirish daraxtini tanlashda va Azizillo testini amalga oshirishda e'tiborga olinishi kerak.

Psevdokod

Orqaga qaytishni muayyan muammolar sinfiga qo'llash uchun ma'lumotlarni taqdim etish kerak P hal qilinishi kerak bo'lgan muammoning ma'lum bir misoli uchun va oltitasi protsessual parametrlar, ildiz, rad etish, qabul qilish, birinchi, Keyingisiva chiqish. Ushbu protseduralar misol ma'lumotlarini olishlari kerak P parametr sifatida va quyidagilarni bajarishi kerak:

  1. ildiz(P): qidiruv daraxtining ildizida qisman nomzodni qaytarish.
  2. rad etish(P,v): qaytish to'g'ri faqat qisman nomzod bo'lsa v to'ldirishga arzimaydi.
  3. qabul qilish(P,v): qaytish to'g'ri agar v ning echimi Pva yolg'on aks holda.
  4. birinchi(P,v): nomzodning birinchi kengaytmasini yaratish v.
  5. Keyingisi(P,s): kengaytirilganidan keyin nomzodning navbatdagi muqobil kengaytmasini yaratish s.
  6. chiqish(P,v): echimdan foydalaning v ning P, dasturga muvofiq.

Orqaga qaytish algoritmi muammoni qo'ng'iroqqa kamaytiradi bt(ildiz(P)), qaerda bt quyidagi rekursiv protsedura:

protsedura bt (c) bu    agar rad etish (P, c) keyin qaytish agar qabul qilish (P, c) keyin chiqish (P, c) s ← birinchi (P, c) esa s ≠ NULL qil        bt (s) s ← keyingi (P, s)

Foydalanish masalalari

The rad etish protsedura a bo'lishi kerak mantiqiy funktsiya qaytib keladi to'g'ri kengaytirilishi mumkin emasligi aniq bo'lsa v uchun tegishli echimdir P. Agar protsedura aniq bir xulosaga kela olmasa, u qaytishi kerak yolg'on. Noto'g'ri to'g'ri natija sabab bo'lishi mumkin bt to'g'ri echimlarni o'tkazib yuborish tartibi. Jarayon shunday deb taxmin qilishi mumkin rad etish(P,t) qaytib keldi yolg'on har bir ajdod uchun t ning v qidiruv daraxtida.

Boshqa tomondan, orqaga qaytish algoritmining samaradorligi bog'liqdir rad etish qaytib kelish to'g'ri iloji boricha ildizga yaqin bo'lgan nomzodlar uchun. Agar rad etish har doim qaytadi yolg'on, algoritm hali ham barcha echimlarni topadi, ammo bu qo'pol kuch qidirishga teng bo'ladi.

The qabul qilish protsedura qaytishi kerak to'g'ri agar v muammo misoli uchun to'liq va to'g'ri echimdir Pva yolg'on aks holda. Bu qisman nomzod deb taxmin qilishi mumkin v va daraxtdagi barcha ota-bobolari o'tgan rad etish sinov.

Yuqoridagi umumiy psevdo-kod haqiqiy echimlar har doim potentsial qidirish daraxtining barglari deb o'ylamaydi. Boshqacha qilib aytadigan bo'lsak, u hal qilish mumkin bo'lgan echimni tan oladi P boshqa tegishli echimlarni olish uchun yana kengaytirilishi mumkin.

The birinchi va Keyingisi protseduralar tugmachaning bolalarini ro'yxatga olish uchun orqaga qaytish algoritmi tomonidan qo'llaniladi v daraxtning, ya'ni farq qiladigan nomzodlarning v bitta kengaytma qadam bilan. Qo'ng'iroq birinchi(P,v) ning birinchi bolasini berishi kerak v, qandaydir tartibda; va qo'ng'iroq Keyingisi(P,s) tugunning keyingi birodarini qaytarishi kerak s, shu tartibda. Agar so'ralgan bola bo'lmasa, ikkala funktsiya ham o'ziga xos "NULL" nomzodini qaytarishi kerak.

Birgalikda ildiz, birinchiva Keyingisi funktsiyalar qisman nomzodlar to'plamini va potentsial qidirish daraxtini belgilaydi. Ular shunday tanlanishi kerakki, ularning har bir echimi P daraxtning biron bir joyida sodir bo'ladi va qisman nomzod bir necha marta sodir bo'lmaydi. Bundan tashqari, ular samarali va samarali tan olishlari kerak rad etish predikat.

Variantlarni erta to'xtatish

Yuqoridagi psevdo-kod qo'ng'iroq qiladi chiqish ushbu misol uchun echim bo'lgan barcha nomzodlar uchun P. Algoritmni birinchi echim topilgandan so'ng to'xtatish uchun o'zgartirish mumkin yoki ma'lum miqdordagi echimlar; yoki ma'lum bir miqdordagi nomzodlarni sinovdan o'tkazgandan so'ng yoki ma'lum miqdorni sarflaganidan keyin Markaziy protsessor vaqt.

Misollar

A Sudoku orqaga chekinish orqali hal qilindi.

Backtracking yordamida jumboq yoki muammolarni hal qilishda foydalanish mumkin bo'lgan misollarga quyidagilar kiradi:

Quyidagi uchun backtracking qo'llaniladigan misol keltirilgan cheklovni qondirish muammosi:

Cheklovdan qoniqish

Umumiy cheklovni qondirish muammosi butun sonlar ro'yxatini topishdan iborat x = (x[1], x[2], …, x[n]), ularning har biri ba'zi oraliqlarda {1, 2, …, m}, bu ba'zi bir o'zboshimchalik cheklovlarini qondiradi (mantiqiy funktsiya) F.

Ushbu sinf muammolari uchun misol ma'lumotlari P butun sonlar bo'ladi m va nva predikat F. Ushbu muammoning odatdagi orqaga qaytish echimida qisman nomzodni butun sonlar ro'yxati sifatida aniqlash mumkin v = (v[1], v[2], …, v[k]), har qanday kishi uchun k 0 va n, bu birinchisiga tayinlanishi kerak k o'zgaruvchilar x[1], x[2], …, x[k]. Keyin asosiy nomzod bo'sh ro'yxat () bo'ladi. The birinchi va Keyingisi protseduralar shunday bo'ladi

funktsiya birinchi (P, c) bu    k ← uzunlik (c) agar k = n keyin        qaytish NULL boshqa        qaytish (c [1], c [2],…, c [k], 1)
funktsiya keyingi (P, lar) bu    k ← uzunlik (lar) agar s [k] = m keyin        qaytish NULL boshqa        qaytish (s [1], s [2],…, s [k - 1], 1 + s [k])

Bu yerda uzunlik(v) - bu ro'yxatdagi elementlarning soni v.

Qo'ng'iroq rad etish(P, v) qaytishi kerak to'g'ri agar cheklov bo'lsa F ning har qanday ro'yxati bilan qondirish mumkin emas n bilan boshlanadigan butun sonlar k elementlari v. Orqaga qaytish samarali bo'lishi uchun, hech bo'lmaganda ba'zi nomzodlar uchun ushbu holatni aniqlashning bir usuli bo'lishi kerak v, barchasini sanab o'tmasdan mn − k n- juftliklar.

Masalan, agar F bo'ladi birikma mantiqiy predikatlardan, F = F[1] ∧ F[2] ∧ … ∧ F[p]va har biri F[men] faqat o'zgaruvchilarning kichik qismiga bog'liq x[1], …, x[n], keyin rad etish protsedura shunchaki shartlarni tekshirishi mumkin F[men] faqat o'zgaruvchilarga bog'liq x[1], …, x[k]va qaytish to'g'ri agar ushbu shartlarning birortasi qaytarilsa yolg'on. Aslini olib qaraganda, rad etish ehtiyojlari faqat bog'liq bo'lgan shartlarni tekshiring x[k], chunki faqat bog'liq bo'lgan atamalar x[1], …, x[k − 1] qidiruv daraxtida yanada ko'proq sinovdan o'tkaziladi.

Buni taxmin qilaylik rad etish yuqoridagi kabi amalga oshiriladi, keyin qabul qilish(P, v) faqat tekshirishni talab qiladi v to'liq, ya'ni bor yoki yo'qligini n elementlar.

Odatda o'zgaruvchilar ro'yxatini buyurtma qilish yaxshiroqdir, shunda u eng muhim bo'lganlardan boshlanadi (ya'ni eng kam variant variantlari bo'lgan yoki keyingi tanlovlarga katta ta'sir ko'rsatadigan).

Bunga ham ruxsat berish mumkin Keyingisi qisman nomzodni kengaytirganda, u tomonidan tayinlangan o'zgaruvchilarning qiymatlari asosida, qaysi o'zgaruvchini tayinlash kerakligini tanlash funktsiyasi. Keyinchalik takomillashtirishni texnikasi bilan olish mumkin cheklovlarni ko'paytirish.

Zaxiralashda ishlatiladigan minimal tiklash qiymatlarini saqlab qolishdan tashqari, orqaga qaytish dasturlari odatda o'zgaruvchan izni saqlaydi va qiymat o'zgarishi tarixini qayd etadi. Samarali dastur tanlov nuqtasi bo'lmaganda ketma-ket ikkita o'zgarish o'rtasida o'zgaruvchan iz yozuvini yaratishni oldini oladi, chunki orqaga qaytish barcha o'zgarishlarni bitta operatsiya sifatida o'chirib tashlaydi.

O'zgaruvchan izga alternativa - saqlash vaqt tamg'asi o'zgaruvchiga oxirgi o'zgartirish qachon kiritilganligi. Vaqt tamg'asi tanlov nuqtasi vaqt tamg'asi bilan taqqoslanadi. Agar tanlov nuqtasi o'zgaruvchiga nisbatan kechroq vaqtga ega bo'lsa, tanlov nuqtasi orqaga qaytarilganda o'zgaruvchini qaytarish kerak emas, chunki u tanlov nuqtasi paydo bo'lishidan oldin o'zgartirilgan.

Shuningdek qarang

Izohlar

  1. ^ Qarang Sudoku echish algoritmlari.

Adabiyotlar

  1. ^ Donald E. Knut (1968). Kompyuter dasturlash san'ati. Addison-Uesli.
  2. ^ Gurari, Eitan (1999). "CIS 680: MA'LUMOT TUZILMALARI: 19-bob: Algoritmlarni orqaga qaytarish". Arxivlandi asl nusxasi 2007 yil 17 martda.
  3. ^ A. Bere; M. Xule; H. van Maaren (2009 yil 29 yanvar). Satisfeability haqida qo'llanma. IOS Press. ISBN  978-1-60750-376-7.
  4. ^ Des Uotson (2017 yil 22 mart). Kompilyator qurilishiga amaliy yondashuv. Springer. ISBN  978-3-319-52789-5.
  5. ^ Rossi, Francheska; Beek, Piter Van; Uolsh, Tobi (2006 yil avgust). "Cheklovdan qoniqish: paydo bo'layotgan paradigma". Cheklovlarni dasturlash bo'yicha qo'llanma. Sun'iy aqlning asoslari. Amsterdam: Elsevier. p. 14. ISBN  978-0-444-52726-4. Olingan 2008-12-30. Bitner va Reingold Lehmerga birinchi marta "orqaga qaytish" atamasini 1950-yillarda ishlatishgan.

Qo'shimcha o'qish

Tashqi havolalar