Artificial Intelligence - هوش مصنوعی - حل مسئله کشيش‌ها و آدمخوارها به روش هاي مختلف

Artificial Intelligence - هوش مصنوعی (http://artificial.ir/intelligence/)

- حل مسائل معروف هوش مصنوعي (http://artificial.ir/intelligence/forum102.html)

حل مسئله کشيش‌ها و آدمخوارها به روش هاي مختلف

مسئله کشيش‌ها و آدمخوارها:

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

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

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

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

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

این برنامه که بیشتر حالت الگوریتمیک دارد تا هوش مصنوعی با استفاده از جستجوی عمقی (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.

بازی شبیه کشیش و آدمخوار:d

پیاده سازی کامل مسئله کشیش ها و آدمخواران
;)

خوب حالت اوليه رو 0و0و0 بترتيب قايق، كشيش، آدم‌خوار در نظر ميگيريم كه حالت هدف ميشه 1و3و3

حركات مجاز:
1- يك آدم‌خوار به طرف مقابل مي‌رود
2- دو آدم‌خوار به طرف مقابل مي‌رود
3- يك كشيش به طرف مقابل مي‌رود
4- يك كشيش به طرف مقابل مي‌رود
5- يك آدم‌خوار و يك كشيش به طرف مقابل مي‌روند

اين هم نمايش

تا اينجا فرموله كردن بود حالا گام بعدي براي پياده سازي چيه؟

چه جالب. من اولین بار بازی این مسپله رو انجام دادم. بعد ها که بزرگتر شدم، فهمیدم که مربوط به هوش مصنوعی می شه. چند وقت پیش یک نوشته کوتاه در مورد این مسپله نوشتم که تو یه پست جدید به اشتراک می گذارم.

حل مسئله کشیشها و آدمخوار | ::وبلاگی برای تمام فصول::

این هم حل مسئله کشیشها که در زمان دانشجویی انجام دادم.
امیدوارم مورد استفاده دوستان قرار بگیره.