Sokoban bo'yicha takliflar

Notatsiya

Ushbu qo'llanmada quyidagi atamalar qo'llaniladi:

• Harakat: Ishchining qutini itarib yoki itarib qo'ymasligining bir qadami.
• yo'l: harakatlar ketma-ketligi.
• pozitsiya: ishchi va barcha qutilar ma'lum bir joyda bo'lishi bilan bog'liq butun muammo.
• Yechim: har bir quti nuqta ustida o'tirgan joy.
• Yechim yo'li: dastlabki holatdan yechimga o'tish ketma-ketligi.
• O'lik pozitsiya: yechimga erishib bo'lmaydigan pozitsiya.

Umumiy strategiya

Eng qisqa yechim 100, 300 yoki hatto 1000 harakatni o'z ichiga olishi mumkin (bizning eng oddiy o'yin 1 allaqachon 73 harakatga muhtoj, 8 o'yin 126 harakat kerak). Agar o'rtacha, masalan, har bir harakat uchun 2 ta imkoniyat mavjud bo'lsa va yechim 100 harakatni olsa, unda qo'pol kuch qidiruvi yechimni topish uchun 2¹⁰⁰ yo'lni qidirishni talab qiladi. Hatto kompyuterlar uchun ham bu mumkin emas. Shuning uchun biz:

1. bir pozitsiya o'lik bo'lsa, erta tan olish,
2. Umumiy maqsadni pastki vazifalarga bo'linadi. Agar 100 harakatdan iborat yechim yo'lini, masalan, 10 kichik vazifalarga bo'linishi mumkin bo'lsa, muammoning murakkabligi keskin kamayadi. Bundan tashqari, pastki vazifalarni bajarish kerak bo'lgan tartibni aniqlash mumkin va keyin butun muammoni hal qilish oson bo'ladi,
3. yechim yoʻlidagi cheklovlarni topish,
4. Boshqa evristik haqida o'ylab ko'ring.

Taxminan 1) O'lik pozitsiyalarni erta aniqlash

1.1) Ba'zan pozitsiyaning o'lik yoki yo'qligini hal qilish oson, faqat bitta qutining atrofiga qarash kerak. Buning uchun faqat "mahalliy" tekshiruv kerak. Agar quti nuqta ustida turmasa va gorizontal va vertikal ravishda ko'chirilmasa, u holda pozitsiya o'likdir. Quti devor yoki boshqa qutilar tomonidan to'sib qo'yilishi mumkin, ular ham ko'chib o'tmasligi mumkin.

1.2) Agar quti devorning yonida bo'lsa va uni itarish mumkin bo'lsa, lekin faqat bir xil tomondagi devor bo'ylab va u etib boradigan joylarning hech biri nuqta bo'lmasa, pozitsiyaning o'lik ekanligini ko'rish biroz qiyinroq.

1.3) Ushbu umumlashtirishda quti devorning yonida joylashgan va uning yonida devor bo'lmagan joyga ko'chirilishi mumkin (quyida A joyi), lekin qutini A yonidagi qutini itarib qo'ygandan keyin ishchi tomonidan erkin qo'shni A joyiga etib bo'lmaydi.

Ushbu uchta holat mahalliy ravishda va ishchini harakatlantirmasdan hal qilinishi mumkin. Shunday qilib, ularni boshlang'ich holatda tekshirish mumkin va joylarni taqiqlangan deb belgilash mumkin, masalan, ! shunday qilib, quti hech qachon bunday joyga itarilmaydi.

1.4) Keyingi umumlashtirishda A joyiga ishchi etib borishi mumkin, lekin faqat taqiqlangan joyga boshqa qutini qo'yish narxida.

Bu tushuntirish rekursiv^[1], ya'ni "o'lik pozitsiya" so'zlari yordamida o'lik pozitsiyani tavsiflaydi. Bunday o'lik pozitsiyalarni aniqlash qiyinroq, chunki ular mahalliy tekshiruv tomonidan aniqlanmaydi va sinov harakatlariga muhtoj bo'lishi mumkin.

Taxminan 2) Kichik vazifalarni shakllantirish

Pastki vazifalarga misollar:

1. Ishchini A dan B ga ko'chiring,
2. Muayyan qutini A'dan B ga koʻchirish

bu vazifalarning har biri o'lik pozitsiyani yaratmasdan amalga oshirilishi kerak.

Misol (a): Ishchi A ga borish uchun qutini qanday o'tkazishi mumkin:

Ishchi quti atrofida yurishi kerakligi sababli barcha bo'sh joy kerak. Agar kamroq bo'sh joy bo'lsa, ishchi o'lik pozitsiyani yaratmasdan qutidan o'ta olmaydi.

Agar koridorning shakllari bilan ko'plab bunday kichik vazifalarni bilsa, bu haqda o'ylashga hojat qolmasdan ko'p vaqtni tejaydi, bu erda bu 9-harakat-yo'l. Eng muhimi, bu sub vazifa imkonsiz deb o'ylagani uchun taslim bo'lmaydi.

Pastki vazifalar bilan bog'liq savol - ularni qanday topish mumkin. Masalan, muammoni teskari hal qilishda pastki vazifalar paydo bo'ladi. Aytaylik, ma'lum bir nuqtaga faqat bir tomondan va faqat bitta quti orqali erishish mumkin. Natijada ushbu qutini ma'lum bir yo'nalishda itarish kerak. Buning uchun ishchi uning boshqa tomoniga o'tishi kerak. Vazifa qutini va ishchini to'g'ri holatga keltirish bo'lishi mumkin.

Pastki vazifani ishlab chiqishning yana bir tipik misoli quyidagilardir. Yechim uchun barcha ichki makonni zarur deb taxmin qilish xavfsizdir. Ya'ni, agar asl holat yuqoridagi misoldagi 2 marta 3 bo'sh maydon kabi katta hajmli ichki bo'shliqlarga ega bo'lsa, unda bu makonning maqsadi nima ekanligini so'rash mumkin. Ishchiga qutini o'tkazish kerak bo'lishi mumkin yoki vaqtincha boshqa joyda bo'sh joy bo'shatish uchun qutini vaqtincha to'xtatish uchun ishlatilishi mumkin. Shunday qilib, agar katta hajmli bo'sh joy vaqtincha qutini saqlashga qodir bo'lsa, unda bu qaysi quti bo'lishi mumkin? Ushbu qutini ushbu oraliq avtoturargohga qanday olib borish mumkin?

Taxminan 3) Yechim yoʻlidagi cheklovlarni shakllantirish

Harakatlarni sinab ko'rmasdan pozitsiyaga qarash orqali echim yo'lida ko'plab cheklovlar mavjud. Misollar:

3.1) Qutiga kirish mumkin bo'lgan yo'lak mavjud, ammo quti hech qachon butun koridor bo'ylab harakatlana olmaydi va shuning uchun yo'lak oxiridagi bo'shliqqa hech qachon yo'lak tugaydigan tomondan etib bo'lmaydi.

3.2) Turli tomonlarda bo'sh joy bo'lsa ham, ma'lum bir nuqtaga faqat bir tomondan erishish mumkin.

3.3) Muayyan quti hech qachon ma'lum bir yo'nalishda harakatlanmaydi va shuning uchun faqat bitta aniq nuqtaga erishishi mumkin.

3.4) Nuqtalarga qutilar orqali faqat biron bir tomondan erishish mumkinligi sababli, u nuqtalarning qaysi tartibda bo'lishi kerakligini belgilaydi.

3.5) Qaysi nuqtani oxirgi marta qoplash kerakligi aniq bo'lishi mumkin, chunki ishchiga qutini ma'lum bir yo'nalishda itarish uchun bo'sh joy kerak.

Taxminan 4) Boshqa evristik usullar

4.1) Teskari bo'lishi mumkin bo'lgan har qanday surish ketma-ketligi sinab ko'rish mumkin va kerak, hatto bu ishchi bu surishlarni teskari qilish uchun boshqa tomondan itarish uchun uzoq yo'lni bosib o'tishi kerak bo'lsa ham. Agar bunday mashqlar ma'nosiz ko'rinsa ham, yangi pozitsiya qanday davom etish kerakligining yangi imkoniyatlarini ochishi mumkin.

4.2) Agar barcha nuqtalarni kamida bitta qutidan ajratib turadigan to'g'ri chiziq mavjud bo'lsa, bu quti ushbu chiziqni kesib o'tishi kerak. Agar bu mumkin bo'lmasa, unda pozitsiya o'lik. Agar qutining bu chiziqni kesib o'tishining faqat bitta yo'li mavjud bo'lsa, bu yechim yo'li uchun kuchli cheklovdir.

To'liq echim misoli (8-o'yin)

Biz belgilash nuqtalariga koordinatalarni kiritamiz. Masalan, ishchi dastlab G1 nuqtasida.

Dastlab ishchida faqat 2 variant mavjud: a) G3 teshikdan o'tish yoki b) E3 teshikdan o'tish. G3 orqali o'tish faqat ishchiga qutini B3 dan B1 gacha o'limdan → itarishga imkon beradi. Shunday qilib, ishchi E3 dan B2 gacha bo'lgan teshikdan o'tadi:

Biz qila oladigan yagona itarish a) B3 qutisi B4 gacha (B5 emas, bu o'lim degan ma'noni anglatadi) yoki C2 qutisi o'ngda.

Biz qutilarni G3 orqali yo'nalishda nuqtalarga ko'chirish mumkin emasligini tushunamiz, chunki ular keyinchalik hech qachon chapga ko'chirilmaydi (1.2-ga qarang).

Ammo ularni B3, C3 teshikdan ko'chirish uchun bu sohada bo'sh joy kerak, shuning uchun biz o'ng tomonda bir yoki ikkita qutini to'xtatishimiz kerak va keyin ularni qaytarib olishimiz kerak.

Biz shuningdek, B3 qutisini faqat B chizig'ida ko'chirish mumkinligini tushunamiz va shuning uchun nihoyat B4 nuqtasida tugashi kerak.

Keyinchalik C4-da qutilarni ko'chirish va keyin ularni o'ng tomonga itarish uchun ishchi A4-ga o'tishi kerak, ammo pastdan u erga borish uchun B3 qutisi B2-da bo'lishi kerak va B3, C3, C2 bo'shliqlari bo'sh bo'lishi kerak, shuning uchun ikkita quti yo'ldan chiqib ketishi va pastki o'ng tomonga to'xtab qo'yilishi kerak.

lekin A3 yoki B3 qutilarini pastga itarish ishlamaydi. (2) pozitsiyasida bo'lgan yagona boshqa variant - B3 qutisini avval B4 ga itarib, keyin (3) pozitsiyasiga olib boradigan harakatlarni bajarish. Biz olish

Endi biz C3 qutisini C2 ga itarib, ishchi bilan F2 qutisini G2 va G3-ga itarish uchun harakat qilishimiz mumkin:

Yuqorida muhokama qilinganidek, bizga B3, C3, C2 bo'shliqlari kerak va B4 qutisini B2-ga tushirishimiz kerak, shuning uchun C2 qutisini vaqtincha G2-ga to'xtatishimiz kerak. Biz:

Endi biz oldingi rejamizga amal qilishimiz va G2 qutisini C4-ga itarishimiz mumkin:

Savol shundaki, biz C4 qutisini qanchalik o'ng tomonga surishimiz kerak. Biz hali ham G3 qutisini xuddi shu yo'l orqali itarib yuborishimiz kerak, chunki biz ishchini G4-ga olishimiz kerak va buning uchun C4 qutisini F4-ga qadar itarib, G4-ni G3-ga surish uchun ishchini G3-ga ko'chirishimiz kerak:

G2 qutisini chapga ko'chirish uchun ishchi H2 ga soat yo'nalishiga qarshi qaytib borishi kerak.

Qolganlari oddiy: quti G2 C2, C4, D4 ga itariladi

keyin B2 qutisi B4 ga itariladi va keyin ishchi G4 qutisini E4 nuqtasida itarish uchun G4-ga o'tadi.

BAJARILDI.