این ترم برای هوش مصنوعی ، استادمون چندتا مسئله داده بود که یکیشون مسئله‌ی اینشتین (Einstein) بود. اینشتین ادعا کرده که ۹۸ درصد مردم جهان نمی‌تونن این مسئله رو حل کنن! حالا صرف‌نظر از روش‌های حل مسئله در هوش مصنوعی اگه می‌خواید هوش خودتون رو آزمایش کنید ، بفرمایید. البته من تا حالا افراد زیادی رو دیدم که این مسئله رو حل کردن و تا جایی که علمم قد بده ، بیشتر از ۲ درصد میشن (!!). به هر حال اگر کامپیوتر رو با انسان مقایسه کنیم و اون رو یک عامل هوشمند در نظر بگیریم ، پس باید بتونه اون رو حل بکنه ( چون به قدر کافی سریع و با دقت هست و هوش رو هم ما که هوشمند‌ترین عامل‌ها هستیم ، بهش داده‌ایم )

به هر حال شروع می‌کنیم: ۵ عدد خانه‌ی منحصربفرد داریم که دارای رنگ‌های مختلف و غیریکسان هستند، در هر کدام از این خانه‌ها ، ۵ نفر با پنج ملیت جداگانه زندگی می‌کنند. این ۵ نفر هرکدام نوشیدنی متفاوت می‌نوشند ، حیوان متفاوت نگهداری می‌کنند و سیگار متفاوت می‌کشند. ماهی در کدام خانه زندگی می‌کند ؟

راهنمایی‌ها :

۱- مرد بریتانیایی در خانه قرمز زندگی می‌کند.

۲- مرد سوئدی سگ نگه می‌دارد.

۳- دانمارکی چای می‌نوشد.

۴- خانه سبز در سمت چپ خانه سفید قرار دارد.

۵- صاحب خانه سبز قهوه می‌نوشد.

۶- مردی که سیگار PallMall می‌کشد ، پرنده نگه می‌دارد.

۷- صاحب خانه زرد رنگ سیگار DunHill می‌کشد.

۸- مردی که در خانه وسطی زندگی می‌کند ، شیر می‌نوشد.

۹- مرد نروژی در خانه اول زندگی می‌کند.

۱۰- مردی که سیگار Blends می‌کشد در کنار مردی که گربه نگه می‌دارد زندگی می‌کند.

۱۱- مردی که اسب نگه می‌دارد ، در کنار مردی که سیگار DunHill می‌کشد زندگی می‌کند.

۱۲- صاحب خانه‌ای که سیگار BlueMaster می‌کشد ، آبجو می‌نوشد.

۱۳- مرد آلمانی سیگار Prince می‌کشد.

۱۴- مرد نروژی در کنار خانه‌ی آبی زندگی می‌کند.

۱۵- مردی که سیگار ‌Blends می‌کشد ، همسایه‌ای دارد که آب می‌نوشد.

قبل از نگاه کردن به حل مسئله ، ابتدا سعی کنید با هر روشی که می‌تونید دستی اون رو حل کنید. ( بهتره که یک ماتریس از خانه‌ها و ملیت‌ها یا عناصر دیگه بکشید و بوسیله‌ی اون ، مسئله رو حل کنید )

( حل مسئله و توضیحات در ادامه‌ی نوشته )

خوب به حل مسئله می‌پردازیم. ابتدا بایستی تشخصی بدهید که تعدادی از جملات فقط وابسته به یک عنصر هستند. برای مثال جمله‌ی ۴ را در نظر بگیرید. در این جمله ما فقط با رنگ‌ها سر و کار داریم. اگر این کار را نکنید ( یعنی جدا کردن جملات و اعمال شرط‌ها به صورت مرحله به مرحله) ، بایستی ۵*۵*۵*۵*۵ حالت رو بررسی کنید که زمان خیلی زیادی – در حدود روزها – خواهد برد.

قبل از شروع به مسئله در صورتی که ساختمان داده‌ها رو پاس کرده باشید ( امیدوارم ! :D ) بایستی با تابع Perm آشنا باشید. این تابع در واقع جایگشت یک لیست کاراکتری رو برامون حساب می‌کنه. این تابع به صورت زیر هست :

void perm(char *list, int i, int n)
{
int j;

if(i == n)
{
for ( j=0; j <= n; j++)
cout << list[j];
cout << “[" << ++count << "] “;
}

else
{
for ( j = i; j <= n; j++)
{
SWAP(&list[i], &list[j]);
perm(list, i+1, n);
SWAP(&list[i], &list[j]);
}
}
}

این تابع به اندازه‌ی کافی ساده هست. کافیه که به پارامتر list یک آرایه‌ی کاراکتری ( مثلا {‘a’, ‘b’, ‘c’} ) رو بدید تا تمامی جایگشت‌های اون رو براتون حساب کنه. البته تابع SWAP هم رو خودتون بنویسید که خیلی راحته و جای دو متغیر رو با هم عوض می‌کنه ( به صورت Macro هم می‌تونید بنویسید ) خوب حالا کاری که بنده کرده‌ام اینه که پنج‌تا تابع تو در توی شبیه Perm نوشتم که حالات رو با بررسی شرط‌ها در هر مرحله تست می‌کنند.
قبل از همه برای هریک از عناصر مسئله Enumeration تعریف کردم :

enum COLOR { RED, GREEN, WHITE, YELLOW, BLUE, NONE_COLOR };

enum NATION { SWEDEN, DENMARK, NORWEJ, GERMAN, BRITAN, NONE_NATION};

enum DRINK { TEA, COFFEE, MILK, BEER, WATER, NONE_DRINK };

enum SIGAR { PALLMALL, DUNHILL, BLENDS, BLUEMASTER, PRINCE, NONE_SIGAR };

enum ANIMAL { BIRD, CAT, HORSE, DOG, FISH, NONE_ANIMAL };

بعد یک کلاس House تعریف کردم که پنج خانه رو به راحتی بتونیم از روی اون درست کنیم. کلاس House به صورت زیر هست :

class House

{

COLOR h_color;

NATION p_nation;

DRINK p_drink;

SIGAR p_sigar;

ANIMAL p_animal;

public:

House();

void SetVar(COLOR );

void SetVar(NATION );

void SetVar(DRINK );

void SetVar(SIGAR );

void SetVar(ANIMAL );

COLOR GetVar(COLOR);

NATION GetVar(NATION);

DRINK GetVar(DRINK);

SIGAR GetVar(SIGAR);

ANIMAL GetVar(ANIMAL);

void PrintColor();

void PrintNation();

void PrintDrink();

void PrintSigar();

void PrintAnimal();

};

همون طور که می‌بینید . برای هر خانه ، رنگ اون ، ملیت شخصی که زندگی می‌کنه ، حیوانی که نگه می‌داره ، سیگاری که می‌کشه و نوشیدنی که می‌نوشه رو به عنوان اعضای کلاس House تعریف کردیم. تعدادی تابع سربار گذاری شده هم داریم که کارمون رو راحت می‌کنه برای گرفتن و ست کردن عناصر مختلف هر خانه ( به پیاده‌سازی اون‌ها در برنامه‌ی اصلی دقت کنید. )

کلاس اصلی که کار اصلی را در برنامه انجام می‌دهد ، کلاس Einstein هست به صورت زیر :

class Einstein

{

int house_numbers;

int HouseList[5];

House Houses[5];

public:

Einstein();

void Initialize();

bool PromisingHouse(int );

void HouseSeq(int );

bool PromisingNation(int );

void NationSeq(int );

bool PromisingDrink(int );

void DrinkSeq(int );

bool PromisingSigar(int );

void SigarSeq(int );

bool PromisingAnimal(int );

void AnimalSeq(int );

void SWAPHouse(int *, int *);

void SWAPNation(int , int );

void SWAPDrink(int , int );

void SWAPSigar(int , int );

void SWAPAnimal(int , int );

};

همان طور که احتمالا حدس زده‌اید ، بنده پنج‌تا متد Perm به نام‌های HouseSeq برای جایگشت رنگ‌ها ، NationSeq برای جایگشت ملیت‌ها ، DrinkSeq برای جایگشت نوشیدنی‌ها ، SigarSeq برای جایگشت سیگارها ! نوشتم که هرکدام از این‌ها تابع امیدبخش (Promising) خودشون رو دارن که برای هر سطح از گره بررسی می‌کنن ببین آیا امیدبخش هست یا نه. لازم به ذکر هست که این توابع در بخش if دوم تابع perm ها کاربرد داره به این خاطر که اکثر شرط‌ها طوری هستند که نیاز دارند هر ۵ خانه اول قرار بگیرن و بعد شرط بررسی بشه.

برای مثال به متد بررسی امیدبخش بودن قسمت رنگ خانه‌ها بپردازیم ، به صورت زیر است :

bool Einstein::PromisingNation(int i)

{

bool promise = true;

for(int j=0; j < i; j++)

{

if( j > 0 && (Houses[HouseList[0]].GetVar(NONE_NATION) != NORWEJ) )

promise = false;

else if(Houses[HouseList[1]].GetVar(NONE_COLOR) != BLUE)

promise = false;

else

if(Houses[HouseList[j]].GetVar(NONE_NATION) == BRITAN && Houses[HouseList[j]].GetVar(NONE_COLOR) != RED)

promise = false;

}

return promise;

}

قبل از بررسی این متد این رو بگم که آرایه‌ی HouseList رو در کلاس Einstein برای این تعریف کردم که هر بار به جای عوض کردن جای واقعی خانه‌ها فقط شماره‌ی اونها رو در این آرایه عوض کنیم.

در این متد بررسی شده است که آیا مرد نروژی در خانه اول زندگی می‌کند یا نه ؟! (بوسیله‌ی Houses[HouseList[0]].GetVar(NONE_NATION) != NORWEJ) اگر این طور نبود ، پس این سطح از درخت امیدبخش نیست. یا اینکه مرد بغلی‌اش در خانه آبی زندگی می‌کند یا خیر ؟! (Houses[HouseList[1]].GetVar(NONE_COLOR) != BLUE) یادآوری می‌کنم که برای متدهای سربارگذاری شده‌ی GetVar و SetVar باید یک enum از نوع چیزی که می‌خوایم بگیریم می‌فرستیم. مثلا برای گرفتن ملیت NONE_NATION رو می‌فرستم.

ترتیب بررسی شرط‌ها در کل کلاس Einstein به این صورت است :

۱- آیا ترتیب رنگ‌ خانه‌ها در شرط‌ها صدق می‌کند ؟! اگر بله بعد برو به مرحله ۲ در غیر اینصورت یک ترتیب دیگر را تولید کن

۲- آیا ترتیب ملیت مردها در شرط‌ها صدق می‌کند ؟! به همین صورت مانند مرحله ۱

۳- ترتیب نوشیدنی‌ها و به همین ترتیب

۴- ترتیب حیوان‌ها و در صورتی که همه‌ی شرط‌ها صدق کرد ، پس جواب پیدا شده و جواب چاپ می‌شود.

به نظر من توضیح بیشتر از این فقط باعث گیج شدن بیشتر میشه. پس کد رو بخونید و در صورتی که بازهم متوجه نشدید ، درخدمت هستم برای رفع ابهامات.

پ.ن۱ : بسته‌ای که دانلود می‌کنید ، شامل سورس کد ، فایل کامپایل‌شده برای ویندوز و گنو/لینوکس ۳۲ بیتی هست. اگه می‌خواید اون رو خودتون کامپایل کنید ، از GCC نسخه‌ی ۴ به بالا استفاده کنید ( البته ۳ هم باید کار کنه ! :D )

پ.ن۲: این مسئله یکی از سخت‌ترین مسئله‌ها و برنامه‌هایی بود که نوشتم و حدود ۲ روزکاری (!) رو براش صرف کردم. پس لطفا خدا رو از یاد نبرید !! :D

دانلود پکیج حل مسئله اینشتین

————————————–

آرزوی موفقیت.

هیچ پست مشابهی وجود ندارد !