تابع هیورستیک برای معمای8

[fandogh]

میتونید برای مسئله معمای8 چند تابع هیورستیک به جز توابع زیر معرفی کنید:
h1:misplaced tiles (تعداد خانه هایی که در مکان مناسب خود باتوجه به حالت هدف قرار ندارند)
h2:manhattan distance (مجموع فاصله بلوکی تمام خانه ها با مکان مناسب خود باتوجه به حالت هدف)

[Cancer]

سلام
از اين دو تا چه استفاده مي توني بكني؟
اون يكي اولي به چه درد مي خوره؟
اون يكي دومي به چه درد مي خوره؟
مي خواي با اين دوتا حالت هاي اضافي رو حذف كني؟
چطوري؟
اون اولي يعني اين كه هر چي تعداد خانه هايي كه در مكان مناسب خود قرار نداشته باشن رو كمتر كني يعني داري به جواب نزديك مي شي؟
اون دومي هم همين طور اگر حالي رو انتخاب كني كه مجموع فواصل بلوكي تمام خانه ها با مكان مناسب خود (هدف) كمتر باشه يعني اون حالت درسته؟
منو روشن كن.

[fandogh]

سلام
از اين دو تا چه استفاده مي توني بكني؟
اون يكي اولي به چه درد مي خوره؟
اون يكي دومي به چه درد مي خوره؟
مي خواي با اين دوتا حالت هاي اضافي رو حذف كني؟
چطوري؟
اون اولي يعني اين كه هر چي تعداد خانه هايي كه در مكان مناسب خود قرار نداشته باشن رو كمتر كني يعني داري به جواب نزديك مي شي؟
اون دومي هم همين طور اگر حالي رو انتخاب كني كه مجموع فواصل بلوكي تمام خانه ها با مكان مناسب خود (هدف) كمتر باشه يعني اون حالت درسته؟
منو روشن كن.


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

h<=h*(n) (قابل قبولh)
— h*(n): مقدار واقعی کم هزینه ترین مسیر رسیدن به هدف از گره n
— اگر برای مسئله ای دو تابع اکتشاف قابل قبول مانند h1(n) و h2(n) وجود داشته باشند و برای تمام گره های n رابطه ی h2 بزرگتریا مساوی h1 برقرار باشد آنگاه میگوییم که h2 بر h1 برتری دارد و یا به عبارتی گوییم روش جستجوی A2 که از تابع h2 استفاده می کند از روش جستجوی A1 که از تابع h1 استفاده می کند آگاه تر است.