الگوریتم *SMA - نسخهی قابل چاپ |
الگوریتم *SMA - amir_ghanati - 31 مرداد ۱۳۹۶ ۱۲:۱۱ ق.ظ
[attachment=22077] با سلام مانشتی های بزرگوار لطفا این الگوریتم *SMA روی مثال زیر برای من توضیح بدید ممنون میشم گراف فضای حالت و مقادیر h گره های آن را نشان میدهد.مراحل اجرا با فرض این که حافظه ظرفیت ۳ گره دارد |
RE: الگوریتم *SMA - M3t30r - 31 مرداد ۱۳۹۶ ۰۳:۳۲ ق.ظ
سلام در الگوریتم جست جو *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 هست. تایپیک سوالات درخواستی در زیر انجمن همون درس قرار داره مثل اینجا: مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمیباشید. جهت مشاهده پیوندها ثبت نام کنید. |