اولین باری که به این مساله بر خوردم در کتاب Russel و Norvig بود. شاید بشه گفتش که این مساله یکی از ابتدایی ترین و در عین حال تاثیرگذارترین مسائل در هوش مصنوعی باشه. اجازه بدید تا صورت مساله رو براتون توضیح بدم.
رودخانه ای رو در نظر بگیرد که در یک طرفش ۳ آدم و ۳ عدم آدم خوار وجود دارند. آدم ها و آدم خوارها همشون قصد دارن تا به طرف دیگر طرف رودخونه برن. برای این کار یه قایق در اختیار دارن که در قایق حداکثر ۲ نفر میتونن سوار بشن. نکتهٔ جالب این مساله اینجاست که هر وقت در یک طرف رودخونه تعداد آدم خوارها از تعداد آدم ها بیشتر بشه، آدم خوارها، آدم هارو میخورن!! یعنی باید تمام سعیتون بر این باشه که آدم ها خرده نشن!
یک لحظه خودتون رو تو این موقعیت تصور کنین! فکر می‌کنین آدم ها و آدم خورها به چه ترتیبی باید از رودخونه رد بشن تا هیچ آدمی خورده نشه؟!
اگر فکر می‌کنین که هنوز مساله رو درست متوجه نشدید یک سری به سایت زیر بزنید.
Missionaries&Cannibals Problem Puzzle Game,Online Logic Games
در این سایت بازی Missionaries and Cannibals توسط Flash برنامه نویسی شده و شما میتونید امتحانش کنید.
و اما رابطه این مساله به هوش مصنوعی چیه؟! بسیأی از مسائلی که در هوش مصنوعی وجود دارن معروفن به مسائل جستجو (Search Problems). یعنی چی؟ یعنی اینکه باید بین گزینه هایی که موجودن بگردیم و بهترین رو انتخاب کنیم. مثلا در مورد همین مسالهٔ خودمون چه گزینه هایی ممکنه داشته باشیم؟ میتونیم اول ۲ تا از آدم خورها رو با قایق ببریم اون ور رودخونه. یا اینکه میتونیم اول ۲ تا از آدم هارو با قایق ببریم اون ور رودخونه. یا اینکه نه! اصلا بیایم یک آدم خور و یک آدم رو اول ببریم اون ور رودخونه. و گزینه های دیگه که همشون رو نمی‌شه اسم برد!
و اما ببینیم توی انفورماتیک با اینجور مسائل چگونه برخورد می‌کنن. دانشمندانه انفورماتیک یه علاقهٔ خاصی به درخت دارن! همه چی رو به چشم یه درخت میبینن. ولی از اونجایی که کسایی که توی زمینهٔ کامپیوتر فعالیت می‌کنن همهٔ کارشون با بقیه فرق داره، درختشونم با بقیه فرق می‌کنه! درخت دانشمند انفورماتیک برعکسه! یعنی اینکه ریشهٔ درخت بالاست و برگ ها و شاخه هاش به سمت پایین!
برگردیم سر مسالهٔ اصلی خودمون. برای حل این مساله با استفاده از درختا، یه سری اومدن گفتن که بیایم یه درخت بسازیم که به جای اینکه میوش گیلاس باشه، میوش (x,y,z) باشه! (اینم یه فرق دانشمندانه انفورماتیک با آدم های معمولی. به جای اینکه درختشون گیلاس و خرمالو و این جور چیزا بده، (x,y,z) میده!!) و اما معنی (x,y,z) چیه؟ فرض کنین که رودخونه، یه سمتش اسمش هست A و سمت دیگش اسمش هست B. و فرض کنیم که همهٔ آدم ها و همهٔ آدم خورها، الان سمت A قرار دارند و میخوان برن سمت B.
x تعداد آدم ها رو در سمت A نمایش میده
y تعداد آدم خورها رو در سمت A نمایش میده
و z هم میتونه دو مقدار به خودش بگیره. یکی صفر که نشون میده قایق سمت B هستش و دیگری یک که نشون میده قایق سمت A هستش.
توجه کنید x و y همیشه بین صفر و سه هستن.
بازی همیشه در وضعیت (3,3,1) شروع میشه.یعنی آدم ها و آدم خور ها و قایق هر سه در سمت A قرار دارن. و هدف ما از انجام بازی رسیدن به وضعیت (0,0,0) هستش. یعنی آدم خورها و آدم ها و قایق هر سه در طرف B قرار بگیرن. از اینجا به بعد ساختن درخت برعکس! شروع میشه.
اجازه بدید از اینجا به بعد رو با یه شکل توضیح بدم.
همینطور که می‌بینید بالای بالا ریشهٔ درخت قرار داره. یعنی وضعیت (3,3,1) که معنیش اینه که آدم خورها و آدم ها و قایق همشون سمت A قرار دارن. قدم بعدی شاخ و برگ دادن به درخته.اگر یکی از آدم ها سوار قایق بشه و بره اون طرف، وارد وضعیت (2,3,0) میشیم. اما این وضعیت قابل قبول نیست. چون تعداد آدم خورها در سمت A برابر ۳ میشه و تعداد آدم ها، برار ۲. پس آدم ها خورده می شن. از اونجایی که این وضعیت قابل قبول نیست، اون رو به رنگ قرمز در می آریم. و اما یک وضعیت قابل قبول می تونه وضعیت (3,2,0) باشه. یعنی یکی از آدم خورها سوار قایق شده و به سمت B رفته.خلاصه این کار رو ادامه می دیم تا تمامی وضعیت هایی که در بالا مشاهده می کنید، تولید بشن. این کار رو باز هم ادامه میدیم، و باز هم ادامه می دیم و انقدر ادامه میدیم تا به وضعیت (0,0,0) برسیم.
توی شکل زیر می تونین نتیجه کار رو ببینید! روی عکس کلیک کنید تا عکس رو با کیفیت بهتر ببینید!
مسیری که به صورت خطوط پررنگ مشخص شده یک راه حل ممکن برای این مسئله می توه باشه.