قوانین بازی هم این هست که شما باید همه کشیش ها و آدم خوار ها را به آن طرف رودخانه ببرید تنها یک قایق برای عبور دارید که دو نفر می توانید سوار آن شود و اگر تعداد آدم خوار ها بیشتر از کشیش ها باشد آدم خوار کشیش را می خورد!
برای دیدن حل این مسئله به ادامه مطلب مراجعه نمایید…
توضیح ویکیپدیا:
معمای کشیشها و آدمخوارها (Missionaries and cannibals problem) یک مسئله کلاسیک در هوش مصنوعی است. این مسئله نمونهای از مسائل ارضای محدودیت میباشد. سه کشیش و سه آدمخوار در یک طرف رودخانه قرار دارند و هم چنین قایقی که قادر است یک یا دو نفر را حمل کند. راهی را بیابید که همه را به سمت دیگر رودخانه ببرد، بدون آنکه تعداد کشیشها در یکجا کمتر از آدمخوارها شود.
این سه مسئله یعنی معمای زن و شوهرهای حسود، ‘معمای کشیشها و آدمخوارها’ و معمای گرگ و گوسفند و کلم به مسائل رد شدن از رودخانه معروف هستند.
حل معما به روش اول:
1- دو آدم خوار را با قایق به سمت چپ آورده و یکی را پیاده می کنیم و با یکی دیگر قایق را به سمت راست می آوریم.
2- یک آدم خوار دیگر را هم می بریم و در طرف راست آدم خواری دیگر نمی ماند! باز هم با یکی از آدم خوار ها با قایق به راست برمی گردیم.
3- آدم خوار را گذاشته و دو کشیک را سوار می کنیم به طرف چپ می بریم و یکی را پیاده کرده و با یک آدم خوار و یک کشیک به سمت راست راه می افتیم.
4- آدم خوار سواره را پیاده می کنیم و کشیش آخری را سوار می کنیم و به سمت چپ می رویم. حال همه کشیش ها را آورده ایم و در سمت چپ سه کشیش داریم و با خیال راحت آدم خوارها را به سمت چپ می بریم. یعنی وقتی سه کشیش در سمت چپ مستفر شدند با یک آدم خوار مانده کشتی را به سمت راست می بریم و دوبار این عمل را انجام داده و همه آدم خوار ها را هم از رودخانه عبور می دهیم.
.
روش دوم:
۱- ابتدا یک آدمخوار با یک کشیش به طرف دیگر میروند.
۲- سپس آدمخوار پیاده شده و کشیش برمی گردد.
۳- دو آدمخوار به سمت دیگر میروند.
۴- یک آدمخوار پیاده شده و یکی بر میگردد.
۵- دو کشیش به سمت دیگر میروند
۶- یک کشیش پیاده شده و یک آدمخوار و یک کشیش بر میگردند
۷- دو کشیش به سمت دیگر میروند
۸- هر دو کشیش پیاده شده و یک آدمخوار بر میگردد
۹- دو آدمخوار به سمت دیگر میروند.
۱۰- یک آدمخوار پیاده شده و یکی بر میگردد.
۱۱- دو آدمخوار به سمت دیگر میروند.
.
تصویر نهایی:
معمای زن و شوهرهای حسود
معمای زن و شوهرهای حسود(jealous husbands problem) به شکل زیر تعریف میشود: سه شوهر حسود و همسران آنها مجبور بودند برای عبور از رودخانه از قایق استفاده کنند. اما قایق آنها آنقدر کوچک بود که بیشتر از ۲ نفر در آن جای نمیگرفت. محدودیت مسئله این است که هیچ زنی نباید با مردی غیر از شوهر خود تنها بماند.
حل مسئله کشیش ها و آدمخوارها در هوش مصنوعی
نمونه کدها (Sample Codes)
برای حل حل مسئله کشیش ها و آدمخوارها در هوش مصنوعی نمونه کدهایی در اینترنت وجود دارد که برای Java میتوانید این لینک و برای Python این لینک و C++ این لینک را مشاهده نمایید.