سلام به همه ی مانشتی های عزیز
میشه یه نفر لطف کنه الگوریتم *SMA رو با ذکر مثال به زبان ساده توضیح بده، من هرچی میخونم و مثال حل میکنم باز یه جاهایی رو اشتباه می کنم، فک کنم کلا درست متوجهش نشدم، ممنون میشم اگه کسی از دوستان میتونه راهنمایی کنه و یه توضیح ساده بده.
با تشکر
(۰۵ آذر ۱۳۹۴ ۱۰:۱۴ ب.ظ)safoora s نوشته شده توسط: سلام به همه ی مانشتی های عزیز
میشه یه نفر لطف کنه الگوریتم *SMA رو با ذکر مثال به زبان ساده توضیح بده، من هرچی میخونم و مثال حل میکنم باز یه جاهایی رو اشتباه می کنم، فک کنم کلا درست متوجهش نشدم، ممنون میشم اگه کسی از دوستان میتونه راهنمایی کنه و یه توضیح ساده بده.
با تشکر
طبق شکل زیر
ظرفیت حافظه ۳ گره:
گره A رو بسط می دیم ، مثلا بر حسب حروف الفبا (طبق تست ۸۸ IT) برگ ها تولید می شوند، اول B بعد G . حالا دیگه حافظه جا نداره و طبق الگوریتم مورد بحث، گره B حذف میشه و مقدارش کناره باباش یعنی گره A می شینه. خوب گره A کامل بسط داده شده ، پس مقدار f بهترین فرزندش رو جایگزین مقدار خودش میکنه حالا باید بریم سراغ یکی از برگ هاش که در حال حاضر فقط G مونده.
G رو که بسط می دیم برگ H تولید میشه ، حالا حافظه پر شده و مسلما دیگه از طریق این برگ نمیشه به هدف رسید، از طرفی H هم گره هدف نیست اگر هم بود الگوریتم خاتمه پیدا نمی کرد چون هزینه H بیشتر از هزینه شاخه دیگری است . طبق توضیحات الگوریتم مربوطه باید بیخیال این مسیر شد پس گره H حذف میشه ، تگ مقدار بی نهایت بهش زده میشه و تحویل باباش یعنی گره G میشه( بی نهایت یعنی دیگه هیچ وقت سراغش نمیریم)
حالا اون یکی فرزند G یعنی i تولید میشه که از قضا گره هدف هست ، ولی چون ما دنبال مسیر بهینه ایم و هزینه گره i بیشتر از گره دیگری است الگوریتم تموم نمیشه.
دوباره گره مذکور از حافظه خارج میشه و این داستان ادامه داره تا میرسیم به گره D و چون مقدارش از گره های دیگه (مثل مسیر حاوی مقدار f=24) کمتره به جواب رسیدیم.