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

الگوریتم *SMA

ارسال:
۳۱ مرداد ۱۳۹۶, ۱۲:۱۱ ق.ظ
الگوریتم *SMA



با سلام
مانشتی های بزرگوار لطفا این الگوریتم *SMA روی مثال زیر برای من توضیح بدید ممنون میشم

گراف فضای حالت و مقادیر h گره های آن را نشان میدهد.مراحل اجرا با فرض این که حافظه ظرفیت ۳ گره دارد
یافتن تمامی ارسال‌های این کاربر
نقل قول این ارسال در یک پاسخ
ارسال:
۳۱ مرداد ۱۳۹۶, ۰۳:۳۲ ق.ظ (آخرین ویرایش در این ارسال: ۳۱ مرداد ۱۳۹۶ ۰۳:۳۸ ق.ظ، توسط M3t30r.)
RE: الگوریتم *SMA
سلام
در الگوریتم جست جو *SMA عمق جست جوها محدود به یه ظرفیت مکانی میشه که در اینجا ظرفیت ۳ هست،یعنی بالا بریم پایین بیایم حداکثر فقط میتونیم ۳ تا گره اونم به شرط اینکه حتما مبدا یکی از اون ۳ تا باشه داشته باشیم.یا به تعریف دیگه حداکثر میتونیم تا ۳ سطح از مبدا به جهت های دیگه حرکت کنیم و گره ها رو ملاقات کنیم.پس مثلا اگه یه هدف با کمترین فاصله تو عمق ۴ ام باشه ما نمیتونیم اصن بررسیش کنیم.
جست جو هایی که از تابع هیروستیک استفاده میکنن به این شکل هستن: [tex]F(x)=G(x)+H(x)[/tex]
G همون فاصله ای هست که روی یال ها نوشته شده و H هم فاصله تخمینی هر راس تا هدف رو بیان میکنه.
خب حالا مثال رو شروع میکنیم:گره A که مبدا هست و برای دیدنش هیچ یالی رو لازم نبود طی کنیم پس G صفر , H هم تخمینش نوشته ۱۲
حالا گره های همسایه A رو ملاقات میکنیم و F هاشونو محاسبه میکنیم.خب فاصله گره Gاز Bکمتر شد پس اول میریم سمت G گره H رو ملاقات میکنیم و مقدار فاصلش همون F رو حساب میکنیم.چون گره Hهدف نبود و ظرفیت ما هم پر شده باید عقبگرد میکنیم و در این مواقع که یک گره از خونه ها حذف میشه مقدار فاصله ش رو کنار پدرش مینویسیم چون ممکنه مسیر های دیگه بدتر ازین باشن و دوباره مجبور بشیم برگردیم همون جایی که قبلا بودیم.
گره H هدف نبود و چون ازون به پایین تر هم دیگه امکان بسط وجود نداره(چون ظرفیت اجازه نمیده عمق پایینتری بریم) برامون ارزشی نداره و مقدار بینهایت رو براش میذاریم که دیگه سراغش نریم اصن.
حالا گره بعدی یعنی iرو ملاقات میکنیم و هدف با فاصله ۲۴ رو پیدا میکنیم : ۸+۱۶+۰= ۲۴
خب ظرفیت خونه ها پر شده و دیگه نمیتونیم این سمت رو ادامه بدیم حالا به امید اینکه در سمت دیگه گره A بتوینم هدف نزدیک تری رو پیدا کنیم عقب گرد میکنیم و مقدار هدف قبلی رو منتقل میکنیم به اجدادش.
سمت چپ هم به همین صورت طی میشه و در نهایت هدف D با فاصله ۲۰ پیدا میشه که بهتر از هدف در زیر شاخه سمت راست A هست.
تایپیک سوالات درخواستی در زیر انجمن همون درس قرار داره مثل اینجا:

مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.

You Only Live Once
یافتن تمامی ارسال‌های این کاربر
نقل قول این ارسال در یک پاسخ
 سپاس‌گزاری شده توسط: sajjadnajafi


موضوع‌های مرتبط با این موضوع...
موضوع: نویسنده پاسخ: بازدید: آخرین ارسال
  مشکل در حل یک مثال با الگوریتم *SMA pooyaa ۱۲ ۱۰,۴۷۴ ۰۷ شهریور ۱۳۹۶ ۰۱:۳۶ ق.ظ
آخرین ارسال: amir_ghanati
  الگوریتم *sma safoora s ۱ ۱۱,۲۵۷ ۲۰ شهریور ۱۳۹۵ ۰۶:۰۱ ب.ظ
آخرین ارسال: M a h d i
  ۱۷۱ نرم افزار و ۱۹۸ الگوریتم - شبانه الگوریتم دانشگاه تهران axarsu ۱ ۲,۴۵۶ ۰۸ شهریور ۱۳۹۵ ۰۸:۳۶ ب.ظ
آخرین ارسال: majidgeek
  ۲۴۲ الگوریتم ،۳۷۱ نرم. الگوریتم برم یا نرم افزار؟ azamcheraghi ۱۱ ۷,۲۱۷ ۰۳ تیر ۱۳۹۵ ۱۱:۳۸ ق.ظ
آخرین ارسال: azamcheraghi
  ترجمه کتاب فصل ۸ Software Development for Small Teams A RUP-Centric Approa k1.technology ۰ ۱,۵۲۲ ۱۱ آذر ۱۳۹۴ ۱۱:۵۴ ب.ظ
آخرین ارسال: k1.technology
  مشکل در الگوریتم جایگزینی (الگوریتم ساعت ) araz22 ۶ ۴,۷۲۱ ۱۹ مهر ۱۳۹۴ ۱۰:۲۴ ب.ظ
آخرین ارسال: so@
  ۸ الگوریتم ۱۲ نرم افزار ۱۵ علوم -- نرم افزار شریف گرایش الگوریتم ahrmb ۲ ۱,۸۴۱ ۰۸ مهر ۱۳۹۴ ۰۶:۴۳ ب.ظ
آخرین ارسال: ahrmb
  ۱۴۷ نرم افزار و ۱۱۶ الگوریتم - الگوریتم روزانه تهران slaf83 ۱۴ ۹,۵۵۰ ۲۴ شهریور ۱۳۹۴ ۱۱:۴۵ ق.ظ
آخرین ارسال: slaf83
  ۱۸۰ نرم ۱۷۰ الگوریتم الگوریتم تهران-شبانه t.mehr ۶ ۳,۵۴۶ ۲۰ شهریور ۱۳۹۴ ۰۴:۰۴ ب.ظ
آخرین ارسال: tondar.sal
  ۱۲۱ نرم افزار ۱۴۵ الگوریتم - الگوریتم تهران روزانه ali blhj ۲۳ ۱۰,۳۷۰ ۱۵ شهریور ۱۳۹۴ ۱۰:۵۹ ق.ظ
آخرین ارسال: ali blhj

پرش به انجمن:

Can I see some ID?

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

Feeling left out?


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

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

Feeling left out?


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