آبجی
10th May 2010, 09:52 PM
http://www.hamedhabibi.com/images/contents/programs/puzzle.jpg
در یک مربع 3 در 3 که شامل 9 خانه کوچک است ، هشت مربع شماره گذاری شده قرار داده ایم . یکی از خانه ها نیز خالی است . مسئله با یک حالت اولیه شروع می شود . هدف چیدن مربع های شماره گذاری شده به ترتیب روبرو است ( حالت هدف ) :
http://www.hamedhabibi.com/images/contents/programs/puzzle1.jpg
نکته مسئله مربع هشت اینسنت که فقط مربع های اطراف خانه خالی را می توانیم با خانه خالی تعویض کنیم . یعنی با حرکت دادن مکرر خانه خالی به چپ ، راست ، بالا و پایین باید به حالت هدف برسیم . برای حل این مساله می توان از روش جستجوی A* استفاده کرد . برای این مسئله چند هیوریستیک مختلف وجود دارد . دو هیوریستیک معمول به صوزت زیر هستند :
1) هیوریستیک اول سعی می کند خانه خالی را طوری جابجا کند که تعداد مربع هایی را در خانه خود قرار نگرفته اند ، صفر شود . یعنی این هیوریستیک بر اساس تعداد مربع هایی که در خانه خود قرار نگرفته اند ، جستجو انجام می دهد.
2) هیوریستیک دوم مجموع فاصله های بلوک شهری هر مربع از خانه خود را محاسبه کرده و سعی می کند خانه حالی را طوری حرکت دهد که این مقدار را به صفر برسد .
در یک مربع 3 در 3 که شامل 9 خانه کوچک است ، هشت مربع شماره گذاری شده قرار داده ایم . یکی از خانه ها نیز خالی است . مسئله با یک حالت اولیه شروع می شود . هدف چیدن مربع های شماره گذاری شده به ترتیب روبرو است ( حالت هدف ) :
http://www.hamedhabibi.com/images/contents/programs/puzzle1.jpg
نکته مسئله مربع هشت اینسنت که فقط مربع های اطراف خانه خالی را می توانیم با خانه خالی تعویض کنیم . یعنی با حرکت دادن مکرر خانه خالی به چپ ، راست ، بالا و پایین باید به حالت هدف برسیم . برای حل این مساله می توان از روش جستجوی A* استفاده کرد . برای این مسئله چند هیوریستیک مختلف وجود دارد . دو هیوریستیک معمول به صوزت زیر هستند :
1) هیوریستیک اول سعی می کند خانه خالی را طوری جابجا کند که تعداد مربع هایی را در خانه خود قرار نگرفته اند ، صفر شود . یعنی این هیوریستیک بر اساس تعداد مربع هایی که در خانه خود قرار نگرفته اند ، جستجو انجام می دهد.
2) هیوریستیک دوم مجموع فاصله های بلوک شهری هر مربع از خانه خود را محاسبه کرده و سعی می کند خانه حالی را طوری حرکت دهد که این مقدار را به صفر برسد .