سه کشيش و سه آدم خوار در يک طرف رودخانه قرار دارند و هم چنين قايقي که قادر است يک يا دو نفر را حمل کند. راهي را بيابيد که هر نفر (همه) به سمت ديگر رودخانه برود، بدون آنکه تعداد کشيشها در يکجا کمتر از آدم خوارها شود.
حالات: يک حالت شامل يک دنبالة مرتب شده از عدد است که تعداد کشيشها، تعداد آدمخوارها و محل قايق در ساحلي از رودخانه که از آنجا مسئله شروع شده را نمايش ميدهد.
عملگرها: از هر حالت، عملگرهاي ممکن يک کشيش، يک آدمخوار، دو کشيش، دو آدمخوار، يا يکي از هر کدام را در قايق جا ميدهند.
این برنامه که بیشتر حالت الگوریتمیک دارد تا هوش مصنوعی با استفاده از جستجوی عمقی (DFS)اولین راه حل را نمایش میدهد . دوستان با کمی تغییر میتوانند آن را به سی شارپ تبدبل کنند .ابتدای کار قایق سمت چپ قرار دارد و سه کشیش و سه آدمخوار نیز سمت چپ هستند .
right >> M=2 C=2 M=1 C=1
یعنی
دو کشیش و دو آدمخوار سمت چپ رودخانه، یک کشیش و یک آدمخوار سمت راست ،قایق نیز سمت راست رودخانه ایستاده
اگه آدمخوارها رو با k و کشیشها رو با aنشون بدیم و left و right سمت چپ و راست رودخونه باشن, الگوریتم به این صورت میشه:
كد:
left(a1,a2,a3,k1,k2,k3); & right(null);
left(a1,a2,a3,k3); & right(k1,k2);(دوتا آدمخور از رودخونه رد میشن)
left(a1,a2,a3,k1,k3); & right(k2);(یکی از آدمخورها برمیگرده)
left(a1,a2,a3); & right(k1,k2,k3);(دوتا دیگه از ادمخورها از رودخونه رد میشن)
left(a1,a2,a3,k1); & right(k2,k3);(یکی از آدمخورها برمیگرده)
left(a3,k1); & right(a1,a2,k2,k3);(دوتا از کشیش ها رد میشن)
left(a1,a3,k1,k2); & right(a2,k3);(یه کشیش و یه ادمخور برمیگردن)
left(k1,k2); & right(a1,a2,a3,k3);(دو تا کشیش رد مشن)
left(k1,k2,k3); & right(a1,a2,a3);(یه ادمخور برمیگرده)
left(k3); & right(a1,a2,a3,k1,k2);(دوتا آدمخور از رودخونه رد میشن)
left(k1,k3); & right(a1,a2,a3,k2);(یکی از آدمخورها برمیگرده)
left(null); & right((a1,a2,a3,k1,k2,k3);(دو تا آدمخور باقی مونده هم رد میشن)
unit HV;
interface
const
Left=false;
Right=true;
Human=0;
Vampire=1;
Type
TPopulation=array[Human..Vampire] of byte;
TRiverCondition=Record
SidesPopulation:array[Left..Right] of TPopulation;
BoatSide:Boolean;
end;
var
n:byte;
FirstSide:boolean;
function Transport(a:TRiverCondition):Boolean;
implementation
function IsValid(a:TRiverCondition):boolean;
begin
Result:=(a.SidesPopulation[Left][Human]>0)and
(a.SidesPopulation[Left][Vampire]>0)and
(a.SidesPopulation[Right][Human]>0)and
(a.SidesPopulation[Right][Vampire]>0)and
(a.SidesPopulation[Left][Human]>=
a.SidesPopulation[Left][Vampire]) and
(a.SidesPopulation[Right][Human]>=
a.SidesPopulation[Right][Vampire]);
end;
function Goal(a:TRiverCondition):boolean;
begin
Result:=(a.SidesPopulation[FirstSide][Human]=0)and
(a.SidesPopulation[FirstSide][Vampire]=0)and
(a.SidesPopulation[not FirstSide][Human]=n)and
(a.SidesPopulation[not FirstSide][Vampire]=n);
end;
procedure WriteCondition(a:TRiverCondition);
begin
//display a in somewhere
end;
function Transport(a:TRiverCondition):Boolean;
var
vv,hh:byte;
ok:Boolean;
b:TRiverCondition;
begin
b.BoatSide:=not a.BoatSide;
ok:=Goal(a);
if IsValid(a) and not ok then
for vv:=0 to 2 do
for hh:=0 to 2 do
if ((vv+hh)>0) and (not ok) then begin
b.SidesPopulation[a.BoatSide][Human]:=a.SidesPopulation[a.BoatSide][Human]-hh;
b.SidesPopulation[not a.BoatSide][Human]:=a.SidesPopulation[a.BoatSide][Human]+hh;
b.SidesPopulation[a.BoatSide][Vampire]:=a.SidesPopulation[a.BoatSide][Vampire]-vv;
b.SidesPopulation[not a.BoatSide][Vampire]:=a.SidesPopulation[a.BoatSide][Vampire]+vv;
ok:=Transport(b);
end;
if ok then WriteCondition(a);
Result:=ok;
end;
end.
خوب حالت اوليه رو 0و0و0 بترتيب قايق، كشيش، آدمخوار در نظر ميگيريم كه حالت هدف ميشه 1و3و3
حركات مجاز:
1- يك آدمخوار به طرف مقابل ميرود
2- دو آدمخوار به طرف مقابل ميرود
3- يك كشيش به طرف مقابل ميرود
4- يك كشيش به طرف مقابل ميرود
5- يك آدمخوار و يك كشيش به طرف مقابل ميروند
اين هم نمايش
تا اينجا فرموله كردن بود حالا گام بعدي براي پياده سازي چيه؟
چه جالب. من اولین بار بازی این مسپله رو انجام دادم. بعد ها که بزرگتر شدم، فهمیدم که مربوط به هوش مصنوعی می شه. چند وقت پیش یک نوشته کوتاه در مورد این مسپله نوشتم که تو یه پست جدید به اشتراک می گذارم.