۳ آدم خوب و ۳ آدم خوار داریم که از یه طرف رودخونه میخوان برن اون ور. یه قایق هم داریم که فقط میتونه یک یا دو نفر رو حمل کنه. در هیچ وضعیتی نباید تعداد آدم خوارها از آدم های خوب بیشتر بشه. کدوم هیوریستیک برای این مسئله مناسب تره؟
۱/ تعداد افرادی که هنوز به طرف دوم رودخونه نرسیدن
۲/ ۱/۲ تعداد افرادی که هنوز به طرف دوم رودخونه نرسیدن
۳/ ۲/۳ تعداد افرادی که هنوز به طرف دوم رودخونه نرسیدن
۴/ دو برابر تعداد افرادی که هنوز به طرف دوم رودخونه نرسیدن
کتاب پوران جوابو زده گزینه ۲ ولی توضیح نداده. یکی لطف کنه توضیح بده
هزینه مسیر در مسئله کشیش و آدمخوار، تعداد طی کردن عرض رودخانه ست . می خواهیم این تعداد مینیمم باشه . وقتی گفته می شه هیوریستیک بهتر کدومه یعنی باید تخمین دقیق‌تر و یا نزدیک تری به هزینه واقعی بزنه . مثلا اگه ۴ تا هیوریستیک [tex]h_{4}[/tex] , [tex]h_{3}[/tex] , [tex]h_{2}[/tex] , [tex]h_{1}[/tex] برای حل یک مساله خاص داشته باشیم، [tex]h_{2}[/tex] به شرطی بهترین هیوریستیکه که مقدارش برای کلیه هزینه‌ها، از اون سه تا هیوریستیک بیشتر باشه . یعنی مثلا اگه حالت زیر رو داشته باشیم می تونیم بگیم [tex]h_{2}[/tex] بهتره:
که [tex]h^{*}[/tex] هزینه واقعی تا هدفه . خوب توی چهار تا گزینه ای که داده گزینه ۴ حذف میشه، چون که اصلا یک هیوریستیک نباید هزینه رو بیشتر از هزینه واقعی تخمین بزنه . اگه دقت کنی میبینی که هزینه گره اول تا گره هدف ۱۱ می شه ولی این تابع هزینه رو ۱۲ میده که غلطه!( [tex]h_{4} \geq h^{*}[/tex] ). این شکل فضای حالت راه حلی از مساله است که عملگرهای توش به اختصار نوشته شده و تعریفش رو پایین عکس می بینید.
![[تصویر: attachment.php?aid=2505]](https://manesht.ir/forum/attachment.php?aid=2505)
می مونه گزینه های ۱ و ۲ و ۳ . شما حالت یکی مونده به آخر تا هدف رو درنظر بگیر. مقدار هیوریستیک واقعی اینجا ۱ هستش ولی گزینه ۱ و ۳ مقداری که برمیگردونه بزرگتر از ۱ میشه ([tex]h_{2} \geq h^{*} , h_{3} \geq h^{*}[/tex] ). پس اصلا گزینه های ۱ و ۳ و ۴ اصلا هیوریستیک مجاز نیستند . می مونه گزینه ۲ که بهترین هیوریستیکه که شرط کمتربودن از هزینه مسیر واقعی رو داره ([tex]h_{2} \leq h^{*}[/tex] ).
[tex]h_{1} \leq h_{3} \leq h_{4} \leq h_{2} \leq h^{*}[/tex]
که [tex]h^{*}[/tex] هزینه واقعی تا هدفه . خوب توی چهار تا گزینه ای که داده گزینه ۴ حذف میشه، چون که اصلا یک هیوریستیک نباید هزینه رو بیشتر از هزینه واقعی تخمین بزنه . اگه دقت کنی میبینی که هزینه گره اول تا گره هدف ۱۱ می شه ولی این تابع هزینه رو ۱۲ میده که غلطه!( [tex]h_{4} \geq h^{*}[/tex] ). این شکل فضای حالت راه حلی از مساله است که عملگرهای توش به اختصار نوشته شده و تعریفش رو پایین عکس می بینید.
MM -> Two Missionaries cross the river
MC -> One Missionary and one Cannibal
CC -> Two Cannibals
M -> One Missionary
C -> One Cannibal
MC -> One Missionary and one Cannibal
CC -> Two Cannibals
M -> One Missionary
C -> One Cannibal
می مونه گزینه های ۱ و ۲ و ۳ . شما حالت یکی مونده به آخر تا هدف رو درنظر بگیر. مقدار هیوریستیک واقعی اینجا ۱ هستش ولی گزینه ۱ و ۳ مقداری که برمیگردونه بزرگتر از ۱ میشه ([tex]h_{2} \geq h^{*} , h_{3} \geq h^{*}[/tex] ). پس اصلا گزینه های ۱ و ۳ و ۴ اصلا هیوریستیک مجاز نیستند . می مونه گزینه ۲ که بهترین هیوریستیکه که شرط کمتربودن از هزینه مسیر واقعی رو داره ([tex]h_{2} \leq h^{*}[/tex] ).