Missionerlar va odamxo'rlar muammosi - Missionaries and cannibals problem
The missionerlar va odamxo'rlar muammosiva chambarchas bog'liq rashkchi erlar muammosi, klassik daryodan o'tish mantiqiy jumboqlar.[1] Missionerlar va odamxo'rlar muammosi taniqli o'yinchoq muammosi yilda sun'iy intellekt, qaerda ishlatilgan Shoul Amarel muammolarni namoyish etish misoli.[2][3]
Muammo
Missionerlar va odamxo'rlar muammosida uchta missioner va uchta odamxo'rlar, agar ikkala bank uchun ham, agar bankda mavjud bo'lgan missionerlar bo'lsa, ular sonini oshirib bo'lmaydi degan cheklov bilan, ko'pi bilan ikki kishini olib ketishi mumkin bo'lgan qayiq yordamida daryodan o'tishlari kerak. odamxo'rlar (agar ular bo'lsa, odamxo'rlar missionerlarni yeyishgan). Bortda odamlar bo'lmagan holda qayiq o'z-o'zidan daryodan o'tolmaydi. Va ba'zi bir o'zgarishlarda, odamxo'rlardan bittasi faqat bitta qo'li bor va u qatlana olmaydi.[1]
Rashkchi erlar muammosida, missionerlar va yirtqichlar uchta turmush qurgan juftlikka aylanishadi, chunki eri ham bo'lmasa boshqa ayolning huzurida hech bir ayol bo'lishi mumkin emas. Ushbu cheklov ostida, ayollarda ham, erkaklar ham bankda hozir bo'lishi mumkin emas, chunki ularning soni erkaklarnikidan oshib ketadi, chunki agar ular bo'lsa, bu ayollar erisiz qoladilar. Shuning uchun, erkaklarni missionerlarga, ayollarni esa odamxo'rlarga almashtirgandan so'ng, hasadgo'y erlar muammosining har qanday echimi ham missionerlar va odamxo'rlar muammosining echimiga aylanadi.[1]
Yechish
Missionerlar va odamxo'rlar muammosini hal qilish uchun tizim, bunda hozirgi holat ⟨m, c, b⟩ oddiy vektor bilan ifodalanadi. Vektor elementlari missionerlar, odamxo'rlar sonini va qayiq noto'g'ri tomonda bo'lganligini bildiradi. Qayiq va barcha missionerlar va odamxo'rlar noto'g'ri tomondan boshlanganligi sababli, vektor -3,3,1⟩ ga o'rnatildi. Harakatlar holat vektorini boshqarish uchun vektorlarni olib tashlash / qo'shish yordamida namoyish etiladi. Masalan, agar yolg'iz odamxo'r odam daryodan o'tgan bo'lsa, ⟨0,1,1⟩ vektor holatdan chiqarilib, -3,2,0⟩ hosil bo'ladi. Shtat noto'g'ri tomonda hali ham uchta missioner va ikkita yirtqichlar borligini va qayiq endi qarama-qarshi sohilda ekanligini aks ettiradi. Muammoni to'liq hal qilish uchun ildiz sifatida dastlabki holat bilan oddiy daraxt hosil bo'ladi. Mumkin bo'lgan beshta harakatlar (-1,0,1⟩, -2,0,1⟩, -0,1,1⟩, -0,2,1⟩ va -1,1,1⟩) olib tashlandi boshlang'ich holatidan, natijada bolalarning ildiz tugunlarini hosil qiladi. Ikkala bankdagi missionerlardan ko'ra ko'proq odamxo'rlarga ega bo'lgan har qanday tugun yaroqsiz holatda bo'ladi va shuning uchun qo'shimcha ko'rib chiqilishdan olib tashlanadi. Yaratilgan bolalar tugunlari -3,2,0⟩, -3,1,0⟩ va -2,2,0⟩ bo'ladi. Ushbu qolgan tugunlarning har biri uchun bolalar tugunlari tomonidan yaratilgan qo'shish mumkin bo'lgan harakat vektorlarining har biri. Algoritm daraxtning har bir darajasi uchun o'zgaruvchan ayirboshlashni va qo'shishni davom ettiradi, uning qiymati ⟨0,0,0⟩ vektor bilan tugun hosil bo'lguncha. Bu maqsad holati va daraxt ildizidan ushbu tugunga qadar bo'lgan yo'l bu muammoni hal qiladigan harakatlar ketma-ketligini anglatadi.
Qaror
Rashkchi erlarga ma'lum bo'lgan dastlabki echim, 11 ta bir martalik sayohatlardan foydalanib, quyidagicha. Turmush qurgan juftliklar sifatida namoyish etiladi a (erkak) va a (ayol), β va bva γ va v.[4], p. 291.
| Sayohat raqami | Boshlang'ich bank | Sayohat | Bank tugaydi |
|---|---|---|---|
| (boshlash) | aa bb γc | ||
| 1 | βb γc | aa → | |
| 2 | βb γc | ← a | a |
| 3 | a β γ | miloddan avvalgi → | a |
| 4 | a β γ | ← a | b v |
| 5 | aa | βγ → | b v |
| 6 | aa | ← βb | γc |
| 7 | a b | aβ → | γc |
| 8 | a b | ← c | a β γ |
| 9 | b | a c → | a β γ |
| 10 | b | ← β | aa γc |
| 11 | βb → | aa γc | |
| (tugatish) | aa bb γc |
Bu muammoning eng qisqa echimi, ammo bu eng qisqa echim emas.[4], p. 291.
Ammo, agar bir vaqtning o'zida qayiqdan faqat bitta erkak chiqib ketishi mumkin bo'lsa va erlar faqat qirg'oqda qayiqda bo'lishdan farqli o'laroq, uning xotini bilan hisoblash uchun qirg'oqda bo'lishlari kerak: 5 dan 6 gacha harakat qilish mumkin emas, chunki tez orada kabi γ chiqib ketdi b qirg'oqda eri faqat qayiqda bo'lishiga qaramay, u bilan bo'lmaydi.
Ilgari aytib o'tganimizdek, rashkchi erlar muammosini hal qilish, missionerlar va odamxo'rlar muammosiga erkaklarni missionerlar, ayollarni esa odamxo'rlar almashtirishi mumkin. Bunday holatda biz missionerlar va odamxo'rlarning individual xususiyatlarini e'tiborsiz qoldirishimiz mumkin. Hozir berilgan echim hali ham eng qisqa va to'rtta eng qisqa echimlardan biri.[5]
Agar qirg'oqda qayiqda bo'lgan ayol bo'lsa (lekin emas) kuni qirg'oq) o'zi deb hisoblaydi (ya'ni qirg'oqdagi biron bir erkakning huzurida emas), unda bu jumboqni 9 ta bir martalik sayohatda hal qilish mumkin:
| Sayohat raqami | Boshlang'ich bank | Sayohat | Bank tugaydi |
|---|---|---|---|
| (boshlash) | aa bb γc | ||
| 1 | βb γc | aa → | |
| 2 | βb γc | ← a | a |
| 3 | β γc | ab → | a |
| 4 | β γc | ← b | aa |
| 5 | γc | βb → | aa |
| 6 | γc | ← b | aa b |
| 7 | γ | miloddan avvalgi → | aa b |
| 8 | γ | ← c | aa bb |
| 9 | γc → | aa bb | |
| (tugatish) | aa bb γc |
O'zgarishlar
Aniq umumlashma rashkchi juftliklar (yoki missionerlar va odamxo'rlar) sonini, qayiqning imkoniyatlarini yoki ikkalasini ham o'zgartirishdir. Agar qayiqda 2 kishi bo'lsa, unda 2 juftlik 5 ta sayohatni talab qiladi; 4 yoki undan ortiq juftlik bilan muammo hal etilmaydi.[6] Agar qayiqda 3 kishi bo'lishi mumkin bo'lsa, unda 5 ta juftlik o'tishi mumkin; agar qayiqda 4 kishi bo'lishi mumkin bo'lsa, istalgan juftlik o'tishi mumkin.[4], p. 300. Ushbu umumlashmalarni tahlil qilish va hal qilishda oddiy grafik-nazariy yondashuv 1966 yilda Fraley, Kuk va Detrik tomonidan berilgan.[7]
Agar daryo o'rtasiga orol qo'shilsa, u holda ikki kishilik qayiq yordamida istalgan juftlik o'tishi mumkin. Agar bankdan bankka o'tishga ruxsat berilmagan bo'lsa, u holda 8nFeribotga o'tish uchun bir tomonlama sayohat qilish kerak n daryoning narigi tomonidagi juftliklar;[1], p. 76 agar ularga ruxsat berilsa, u holda 4nAgar kerak bo'lsa +1 sayohat kerak n 4 dan oshadi, garchi minimal echim faqat 16 ta sayohatni talab qiladi n 4 ga teng.[1], p. 79. Agar rashkchi juftliklar o'rnini missionerlar va odamxo'rlar egallashsa, bankdan bankka o'tishga yo'l qo'yilmasa, zarur bo'lgan sayohat soni o'zgarmaydi; agar ular bo'lsa, sayohat soni 4 ga kamayadin$ -1 $ deb taxmin qilsangiz n kamida 3 ga teng.[1], p. 81.
Tarix
Rashkchi erlar muammosining birinchi ma'lum ko'rinishi o'rta asr matnida Acuendos Juvenes kompaniyasining takliflari, odatda tegishli Alcuin (804 yilda vafot etgan). Alkuyinning formulasida er-xotinlar birodarlar va opa-singillardir, ammo cheklovlar hanuzgacha bir xil - biron bir ayol, agar uning ukasi ishtirok etmasa, boshqa erkakning yonida bo'lolmaydi.[1], p. 74. XIII asrdan XV asrgacha bu muammo butun Shimoliy Evropada ma'lum bo'lib, er-xotinlar endi er va xotin bo'lishgan.[4], 291–293 betlar. Keyinchalik bu masala ustalar va vale shaklida qo'yilgan; missionerlar va odamxo'rlar bilan tuzilish 19-asrning oxiriga qadar paydo bo'lmadi.[1], p. 81 Xotinlarning sonini va qayiqning o'lchamlarini o'zgartirish XVI asrning boshlarida ko'rib chiqilgan.[4], p. 296. Kadet de Fontenay orolni daryoning o'rtasiga joylashtirishni 1879 yilda o'ylagan; muammoning ushbu varianti, ikki kishilik qayiq bilan, Yan Pressman tomonidan to'liq hal qilindi va Devid Singmaster 1989 yilda.[1]
2020 yilda ushbu muammo haqidagi multfilmdagi irqchi mavzulardagi tortishuvlar sabab bo'ldi AQA muammoni o'z ichiga olgan matnli kitobni olib tashlash uchun imtihon kengashi.[8]
Shuningdek qarang
Adabiyotlar
- ^ a b v d e f g h men Pressman, Yan; Singmaster, Devid (1989 yil iyun). "'Rashkchi erlar va 'missionerlar va odamxo'rlar'". Matematik gazeta. 73 (464): 73–81. doi:10.2307/3619658. JSTOR 3619658.
- ^ Amarel, Shoul (1968). Michie, Donald (tahrir). "Amallar to'g'risida mulohaza yuritish muammolari to'g'risida". Mashina intellekti. Amsterdam, London, Nyu-York: Elsevier / Shimoliy-Gollandiya. 3: 131–171. Arxivlandi asl nusxasi 2008 yil 8 martda.
- ^ Kordeski, Roberto (2006). "Labirintda qidirish, bilim izlash: dastlabki sun'iy aql masalalari". Stokda, Oliviero; Sherf, Marko (tahr.). AI nazariyalari va tizimlarida mulohaza, harakat va o'zaro ta'sir: Luigia Carlucci Aiello-ga bag'ishlangan insholar. Kompyuter fanidan ma'ruza matnlari. 4155. Berlin / Heidelberg: Springer. 1-23 betlar. doi:10.1007/11829263_1. ISBN 978-3-540-37901-0.
- ^ a b v d e Franci, Raffaella (2002). "Daryodan o'tayotgan rashkchi erlar: Alkuyindan tortib Tartaliyaga qadar bo'lgan muammo". Dold-Samploniusda, Yvonne; Dauben, Jozef V.; Folkerts, Menso; van Dalen, Benno (tahrir). Xitoydan Parijgacha: matematik g'oyalarning 2000 yilligi. Shtutgart: Frants Shtayner Verla. 289-306 betlar. ISBN 3-515-08223-9.
- ^ Lim, Ruby (1992). Shou, Leyn S.; va boshq. (tahr.). Yirtqichlar va missionerlar. APL '92, APL bo'yicha Xalqaro konferentsiya (Sankt-Peterburg, 6-10 iyul 1992). Nyu-York: Hisoblash texnikasi assotsiatsiyasi. 135–142 betlar. doi:10.1145/144045.144106. ISBN 0-89791-477-5.
- ^ Peterson, Ivars (2003 yil 13-dekabr). "Ayyor chorrahalar". Fan yangiliklari. 164 (24). Olingan 12 mart, 2011.
- ^ Frali, Robert; Kuk, Kennet L.; Detrik, Piter (1966 yil may). "Qiyin o'tish jumboqlarining grafik echimi". Matematika jurnali. 39 (3): 151–157. doi:10.1080 / 0025570X.1966.11975705. JSTOR 2689307.
- ^ Muxbir, Nikola Vulkok, Ta'lim. "AQA imtihon kengashi tomonidan GCSE kitobi tasdiqlangan, u oq missionerni pishiradigan odamxo'rlar tasvirlangan". ISSN 0140-0460. Olingan 2020-07-19 - www.thetimes.co.uk orqali.