معمای کشیش‌ها و آدمخوارها

معمای کشیش ها و آدمخوارها (Missionaries and cannibals problem) یک مسئله کلاسیک در هوش مصنوعی است. این مسئله نمونه‌ای از مسائل ارضای محدودیت می‌باشد. سه کشیش و سه آدم‌خواری در یک طرف رودخانه قرار دارند و هم چنین قایقی که قادر است یک یا دو نفر را حمل کند. راهی را بیابید که همه را به سمت دیگر رودخانه ببرد، بدون آنکه تعداد کشیش ها در یکجا کمتر از آدم‌خوارها شود.

این سه مسئله یعنی معمای زن و شوهرهای حسود، 'معمای کتاب خوان ها و آدمخوارها' و معمای گرگ و گوسفند و کلم به مسائل ردشدن از رودخانه معروف هستند.

راه حل

1. ابتدا یک آدم‌خوار با یک کتاب خوان به طرف دیگر می‌روند.
2. سپس آدم‌خوار پیاده شده و کتاب خوان برمی گردد.
3. دو آدم‌خوار به سمت دیگر می‌روند.
4. یک آدم‌خوار پیاده شده و یکی بر می‌گردد.
5. دو کتاب خوان به سمت دیگر می‌روند
6. یک کتاب خوان پیاده شده و یک آدم‌خوار و یک کتاب خوان بر می‌گردند
7. دو کتاب خوان به سمت دیگر می‌روند
8. هر دو کتب خوان پیاده شده و یک آدم‌خوار بر می‌گردد
9. دو آدم‌خوار به سمت دیگر می‌روند.
10. یک آدم‌خوار پیاده شده و یکی بر می‌گردد.
11. دو آدم‌خوار به سمت دیگر می‌روند.

منابع

• http://www.sid.ir/fa/VEWSSID/J_pdf/52313840202.pdf