مسئله کشیش و آدمخوار

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

حالات: یک حالت شامل یک دنبالة مرتب شده از عدد است که تعداد کشیش‌ها، تعداد آدمخوارها و محل قایق در ساحلی از رودخانه که از آنجا مسئله شروع شده را نمایش می‌دهد.

عملگرها: از هر حالت، عملگرهای ممکن یک کشیش، یک آدمخوار، دو کشیش، دو آدمخوار، یا یکی از هر کدام را در قایق جا می‌دهند.

آزمون هدف: رسیدن به حالت (0و 0 و 0)

هزینه مسیر: تعداد دفعات عبور از رودخانه.