نمايش پست تنها
قديمي ۰۹-۱۶-۱۳۸۹, ۱۲:۵۱ قبل از ظهر   #11 (لینک دائم)
bijibuji Male
عضو فوق فعال
 
آواتار bijibuji
 
تاريخ عضويت: مهر ۱۳۸۸
پست ها: 16
تشكرها: 27
38 تشكر در 14 پست
پيش فرض حل پازل 8

حالت اولیه (شروع):



حالت هدف:


فرض کنید که حالت فعلی به این شکله:


حالا می ریم سر محاسبه f در این حالت فعلی (برای هر حالت یک f محاسبه می شه که جمع g و h هست)

با چند حرکت از حالت اولیه به حالت جاری رسیدیم؟ (این رو نمی شه یهو واسه یه حالت حساب کرد. بلکه باید به تدریج که مراحل رو جلو میاید، یکی یکی حساب کنید و در حافظه نگهداری کنید. اما در این مثال چون ساده است، می شه فهمید که با چند حرکت از حالت اولیه به اینجا رسیدیم.)

g=4
بعد از اون می ریم سراغ محاسبه h که هیورستیک یا تابع اکتشافی است.
تخمیی که به کار می خوایم ببریم فاصله منهتنه. یعنی هر خانه، نسبت به جایی که باید باشه چند خونه اختلاف داره. به عبارت بهتر با چند حرکت می تونیم ببریم بذاریم اش سر جاش، اگر هیچ عدد دیگه ای در بازی نباشه و راه کاملا هموار باشه. برای تک تک خانه ها (هر 8 تا) باید حساب کنیم و آخرش با هم جمع بزنیم.

h= فاصله منهتن خانه شماره 1 + فاصله منهتن خانه شماره 2 + فاصله منهتن خانه شماره 3 + فاصله منهتن خانه شماره 4 + ...

پس خواهیم داشت:

h=2+2+0+0+0+1+1+1=7
خوب حالا مقدار تابع ارزیابی f برای حالت جاری محاسبه شد:

f=g+h=4+7=11
اگر مقدار f رو برای حالت های دیگه حساب کردیم و کمترین شون این مقدار (یعنی 11) بود، باید حالت های دیگه رو بی خیال شیم و حالت جاری رو بسط بدیم.

امیدوارم متوجه شده باشید.
عكس ضميمه
نوع فايل: png 8_puzzle_start_state_a.png (8.5 كيلو بايت, 294 نمايش)
نوع فايل: png 8_puzzle.png (10.5 كيلو بايت, 271 نمايش)
نوع فايل: png 8_puzzle_goal_state_a.png (8.5 كيلو بايت, 265 نمايش)
bijibuji آفلاين است   پاسخ با نقل قول
از bijibuji تشكر كرده اند:
jafar.spectator (۰۳-۲۳-۱۳۹۱), khodesh (۰۹-۱۷-۱۳۸۹), mahdi68 (۰۹-۱۶-۱۳۸۹)

  #ADS
نشان دهنده تبلیغات
تبليغگر
 
 
 
تاريخ عضويت: -
محل سكونت: -
سن: 2010
پست ها: -
 

نشان دهنده تبلیغات is online