سلام
در الگوریتم جست جو *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 هست.
تایپیک سوالات درخواستی در زیر انجمن همون درس قرار داره مثل اینجا:
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
