زمان کنونی: ۲۰ آذر ۱۳۹۷, ۰۸:۰۸ ق.ظ مهمان گرامی به انجمن مانشت خوش آمدید. برای استفاده از تمامی امکانات انجمن می‌توانید عضو شوید.
گزینه‌های شما (ورودثبت نام)

هیوریستیک مناسب برای مسئله آدم خوارها

ارسال:
  

bn3232 پرسیده:

هیوریستیک مناسب برای مسئله آدم خوارها

۳ آدم خوب و ۳ آدم خوار داریم که از یه طرف رودخونه میخوان برن اون ور. یه قایق هم داریم که فقط میتونه یک یا دو نفر رو حمل کنه. در هیچ وضعیتی نباید تعداد آدم خوار‌ها از آدم های خوب بیشتر بشه. کدوم هیوریستیک برای این مسئله مناسب تره؟
۱/ تعداد افرادی که هنوز به طرف دوم رودخونه نرسیدن
۲/ ۱/۲ تعداد افرادی که هنوز به طرف دوم رودخونه نرسیدن
۳/ ۲/۳ تعداد افرادی که هنوز به طرف دوم رودخونه نرسیدن
۴/ دو برابر تعداد افرادی که هنوز به طرف دوم رودخونه نرسیدن
کتاب پوران جوابو زده گزینه ۲ ولی توضیح نداده. یکی لطف کنه توضیح بده Huh

۰
ارسال:
  

parsaNA پاسخ داده:

RE: هیوریستیک مناسب برای مسئله آدم خوارها

هزینه مسیر در مسئله کشیش و آدمخوار‌، تعداد طی کردن عرض رودخانه ست . می خواهیم این تعداد مینیمم باشه . وقتی گفته می شه هیوریستیک بهتر کدومه یعنی باید تخمین دقیق‌تر و یا نزدیک تری به هزینه واقعی بزنه . مثلا اگه ۴ تا هیوریستیک [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_{1} \leq h_{3} \leq h_{4} \leq h_{2} \leq h^{*}[/tex]

که [tex]h^{*}[/tex] هزینه واقعی تا هدفه . خوب توی چهار تا گزینه ای که داده گزینه ۴ حذف میشه‌، چون که اصلا یک هیوریستیک نباید هزینه رو بیشتر از هزینه واقعی تخمین بزنه . اگه دقت کنی میبینی که هزینه گره اول تا گره هدف ۱۱ می شه ولی این تابع هزینه رو ۱۲ میده که غلطه‌!( [tex]h_{4} \geq h^{*}[/tex] ). این شکل فضای حالت راه حلی از مساله است که عملگرهای توش به اختصار نوشته شده و تعریفش رو پایین عکس می بینید.

[تصویر:  attachment.php?aid=2505]

MM -> Two Missionaries cross the river
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] ).


فایل‌(های) پیوست شده



موضوع‌های مرتبط با این موضوع...
موضوع: نویسنده پاسخ: بازدید: آخرین ارسال
  حل چند مسئله یکسان سازی sal_dovomi ۵ ۳,۸۲۴ ۰۷ بهمن ۱۳۹۱ ۰۴:۰۵ ب.ظ
آخرین ارسال: ati67
  مسئله از مین ماکس lonelyforever ۲ ۲,۰۸۶ ۲۸ بهمن ۱۳۹۰ ۰۵:۰۹ ب.ظ
آخرین ارسال: lonelyforever
  سوال ۱۷ از فصل دوم پوران(مساله معمای ۸ و تخمین مناسب برای تعداد حرکت ها) mosaferkuchulu ۳ ۱,۴۸۹ ۲۷ مهر ۱۳۹۰ ۰۹:۳۴ ق.ظ
آخرین ارسال: homa
  فرض استقلال اهداف فرعی در هیوریستیک برای جستجو در فضای حالت homa ۱ ۱,۵۳۶ ۱۸ بهمن ۱۳۸۹ ۰۲:۵۸ ب.ظ
آخرین ارسال: امیدوار

پرش به انجمن:

Can I see some ID?

به خاطر سپاری رمز Cancel

Feeling left out?


نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close

رمزت رو فراموش کردی؟

Feeling left out?


نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. close