الف صحیح و یا غلط بودن جملات زیر را مشخص کرده و پاسخ را توضیح دهید. -
-۱ در فضای جستجوی محلی ممکن است بیش از یک ماکزیمم محلی وجود داشته باشد.
-۲ جستجوی تپه نوردی با شروع مجدد تصادفی تضمین می کند که جواب بهینه را بیابد.
-۳ اگر h(n) و g(n) دو تابع هیوریستیک قابل قبول باشند، آنگاه ½ h(n)+ ½ g(n) نیز یک هیوریستیک قابل قبول است.
-۴ در روش جستجوی هزینه یکنواخت اگر به همه هزینه مقدار ثابت c اضافه شود، مسیر بهینه تغییر نمی کند.
-۵ روش جستجوی RBFS نسبت به روش A* به حافظه کمتری نیاز دارد.
۱- صحیح - چون در فضای حالتِ مسئله ممکن است شرایط یا حالات یا اهدافی وجود داشته باشند که کاملترین و بهترین جواب نیستند اما نزدیک به هدف هستند. مثلا در مسئله ۸-وزیر ممکن است در هر بار اجرای برنامه نتوانیم حالت هدف برنامه را بچینیم(حالتی که وزیرها هیچکدام همدیگر را تهدید نمیکنند) اما حالتهایی وجود دارد که در آن حداقل تهدید وجود دارد
به طور کلی فضای حالت یا فضای جستجو ممکن است چند ماکزیمم محلی داشته باشد(که همان حالاتی هستند که اگر چه هدف اصلی نیستند ولی نزدیک به هدف هستند)
۲- صحیح (طبق کتاب راسل) - چون در اینجا مسئله احتمال هم مطرح هست ، پس و قتی مکررا شروع های مجدد داریم ، و هربار از نقطه ای شانسی ، این احتمال وجود دارد که این مسیر و شروع مجدد مارا به قله ماکزیمم برساند. و وقتی تعداد شروعهای محدد تصادفی بیشتر شود ، شانس رسیدن به ماکزیمم سراسری هم بیشتر میشود و نزدیک به ۱ خواهد شد
(۰۶ آذر ۱۳۹۱ ۱۲:۵۸ ب.ظ)f kermani نوشته شده توسط: الف صحیح و یا غلط بودن جملات زیر را مشخص کرده و پاسخ را توضیح دهید. -
-۱ در فضای جستجوی محلی ممکن است بیش از یک ماکزیمم محلی وجود داشته باشد.
-۲ جستجوی تپه نوردی با شروع مجدد تصادفی تضمین می کند که جواب بهینه را بیابد.
-۳ اگر h(n) و g(n) دو تابع هیوریستیک قابل قبول باشند، آنگاه ½ h(n)+ ½ g(n) نیز یک هیوریستیک قابل قبول است.
-۴ در روش جستجوی هزینه یکنواخت اگر به همه هزینه مقدار ثابت c اضافه شود، مسیر بهینه تغییر نمی کند.
-۵ روش جستجوی RBFS نسبت به روش A* به حافظه کمتری نیاز دارد.
در مورد گزینه های ۳و۴و۵ ...
۳ - مطمئن نیستم ولی یه نکته اینکه اگر h , g قابل قبول باشند ، max(g,h) هم قابل قبوله ! فکر می کنم درسته...
۴- درسته - چون فقط وقتی مشکل ایجاد می شه که هزینه ی گامها منفی باشه
۵- درسته - چون با استفاده از حدی که ذخیره میشه ، بهترین گره بعد از گره ی که انتخاب شده رو داریم پس نیازی به نگهداری کل گره ها نیست.
منم
فکر کنم همه درست باشن
همشهری عزیز هر ۵ گزینه درسته!
در مورد گزینه ۳ هم که دوستان ابهام داشتن کافیه به تست کامپیوتر ۸۳ مراجعه کنی عین همینه!البته اونجا سه تا H داریم که میانگین اونها هم قابل قبوله!
کلا اینو بدون اگه چندتا h قابل قبول داشته باشیم آنگاه میانگین اونها هم حتما قابل قبوله!
موفق باشی
(۱۹ دى ۱۳۹۱ ۱۲:۲۱ ب.ظ)۸Operation نوشته شده توسط: در مورد گزینه ۳ هم که دوستان ابهام داشتن کافیه به تست کامپیوتر ۸۳ مراجعه کنی عین همینه!البته اونجا سه تا H داریم که میانگین اونها هم قابل قبوله!بانظر شما موافقم.میانگین توابع هیوریستیک هم یک هیوریستیک قابل قبوله
(۰۶ آذر ۱۳۹۱ ۱۲:۵۸ ب.ظ)f kermani نوشته شده توسط: -۴ در روش جستجوی هزینه یکنواخت اگر به همه هزینه مقدار ثابت c اضافه شود، مسیر بهینه تغییر نمی کند.در این مورد فکر نمیکنم تغییری کنه(یعنی باید این گزینه درست باشه) چون هزینه یکنواخت فقط وقتی هزینه یک گره منفی میشه نمیتونه جواب بهینه رو پیدا کنه.ودر مواقعی که هزینه ها با افزایش عمق جستجو زیاد بشن(به طور ثابتی اضافه بشن ) باز هم میتونه جواب رو پیدا کنه و بهینه است
(۰۶ آذر ۱۳۹۱ ۱۲:۵۸ ب.ظ)f kermani نوشته شده توسط: -۵ روش جستجوی RBFS نسبت به روش A* به حافظه کمتری نیاز دارد.درسته چون a* همه گرهها رو توی حافظه نگه میداره
rbfs پیچیدگی خطی داره.
(۰۶ آذر ۱۳۹۱ ۱۲:۵۸ ب.ظ)f kermani نوشته شده توسط: -۳ اگر h(n) و g(n) دو تابع هیوریستیک قابل قبول باشند، آنگاه ½ h(n)+ ½ g(n) نیز یک هیوریستیک قابل قبول است.
این الان میانگینشونه؟ میانگین باشه درسته.اما من دارم این طوری می خونم:
Hn+
۱/۲
*
Gn be tavane 1/2
اینطوری فکر نکنم درست باشه. فرض کنین Hn همون حداقل فاصله بین دو نود باشه و بزرگتر از یک و Gn ما هم برابر یک باشه اونوقت بیشتر تخمین میزنه پس نادرسته