تالار گفتمان مانشت
SMA* چگونه کار می کند. - نسخه‌ی قابل چاپ

SMA* چگونه کار می کند. - pos - 26 آبان ۱۳۹۰ ۱۲:۵۵ ب.ظ

توی بقیه A*‌ها مسیری را انتخاب میکنه که f کوچکتری داره. چرا توی عکس زیر بعد از انتخاب A از بین Bو G اول Bرا انتخاب کرد در صورتی که G مسیر کوتاهتری را داره نشان میده (F کوچکتری داره). یا مثلا توی تصویر زیر با اینکه به جواب I رسید باز هم به مسیر داره ادامه میده. از کجا می فهمه I بهینه نیست؟
ممنون.

RE: SMA* چگونه کار می کند. - nfe89 - 26 آبان ۱۳۹۰ ۰۶:۵۹ ب.ظ

(۲۶ آبان ۱۳۹۰ ۱۲:۵۵ ب.ظ)pos نوشته شده توسط:  توی بقیه A*‌ها مسیری را انتخاب میکنه که f کوچکتری داره. چرا توی عکس زیر بعد از انتخاب A از بین Bو C اول Bرا انتخاب کرد در صورتی که C مسیر کوتاهتری را داره نشان میده (F کوچکتری داره). یا مثلا توی تصویر زیر با اینکه به جواب I رسید باز هم به مسیر داره ادامه میده. از کجا می فهمه I بهینه نیست؟
ممنون.

سلام.

ویژگی ها:
این روش از حافظه موجود برای جستجو استفاده می کند.
هر اندازه که حافظه در اختیارش اجازه دهد، می تواند از حالت های تکراری دوری کند.
اگر حافظه در دسترس آن، برای ذخیره سازی مسیر کم عمقترین پاسخ کافی باشد، کامل خواهد بود.
اگر حافظه در دسترس آن، برای ذخیره سازی مسیر بهترین پاسخ کافی باشد، بهینه خواهد بود.
به عبارت دیگر این روش، بهترین جوابی را که با حافظه در دسترسش می تواند دست یابد، باز می گرداند.

خلاصه روش:
در این روش هنگامی که بخواهیم فرزند را تولید کنیم و بر روی صف حافظه ای موجود نباشد، آن گاه گره هایی را از صف حذف می کنیم. به این گره‌ها‌، فراموش شده گویند.
در این کار گره هایی را که امید چندانی به آن‌ها نداریم از صف حذف خواهد شد( یعنی گره با f بیشتر)

برای اجتناب از کاوش دوباره زیر درختی که از حافظه حذف شده است، باید اطلاعات مربوط به بهترین مسیر در زیر درخت فراموش شده را در گره پدر ذخیره کرد. بدین ترتیب فقط هنگامی این زیر درخت باز تولید خواهد شد که مشخص شود تمامی سایر مسیرها، نسبت به این زیر درخت بدتر به نظر آیند.

در مثال شما فرض شده است کهفقط اطلاعات ۳ گره را می توان حفظ کرد.


سوال اولتون رو اگر منظورتون b , g هست‌، g‌، مقدار f کمتری داره.
سوال دومتون چون به یه پاسخ با هزینه ۲۴ رسیده ولی تو گره های پدری (اینجا A) جلوش نوشتیم ۱۵ یعنی یه زیر درختی رو ازش فراموش کردیم که مقدار f معادل ۱۵ داشته.
اما توی مرحل آخر‌، پدر و پدربزرگ قبول کردن که زیردرختی بهتر از این نداشتن...

تلاشم رو کردم که کامل متوجه بشید حالا چقدر موفق بودم نمیدونم

SMA* چگونه کار می کند. - pos - 26 آبان ۱۳۹۰ ۰۸:۰۴ ب.ظ

جواب قسمت دوم را متوجه شدم ولی قسمت اول را نه.
ببینین توی عکسی که گذاشتم در قسمت پایین توی ۸ مرحله مراحل کار را کشیده. در مرحله دوم از بین G و B ابتدا B را انتخاب کرده در صورتی که f(b)=15 و f(g)=13 هست. یعنی f بزرگتر را انتخاب کرده. همین طور در مرحله از بین C و D ابتدا f گره C را انتخاب کرده که f آن بزرگ‌تر هست

(۲۶ آبان ۱۳۹۰ ۰۶:۵۹ ب.ظ)nfe89 نوشته شده توسط:  سوال اولتون رو اگر منظورتون b , g هست‌، g‌، مقدار f کمتری داره.
بله منظورم همان G بود. سوال را ویرایش کردم.
ممنون

RE: SMA* چگونه کار می کند. - nfe89 - 26 آبان ۱۳۹۰ ۰۹:۴۷ ب.ظ

(۲۶ آبان ۱۳۹۰ ۰۸:۰۴ ب.ظ)pos نوشته شده توسط:  در مرحله دوم از بین G و B ابتدا B را انتخاب کرده در صورتی که f(b)=15 و f(g)=13 هست. یعنی f بزرگتر را انتخاب کرده.
ببین ما کلا توی صف جای سه حالت رو داریم اینجا .
بخاطر این محدودیت تو هر مرحله نمیاد همه فرزندا رو بسازه.

این مراحلی که کشیده خاسته بگه تو هر نوبت کدوم گره‌ها تو صف هستن.
اگه تو صف جا بود اولینی که میتونه رو میسازه. اگه نه بدترین f رو از صف حذف میکنه بعد میسازه.
ینی مرحله دوم که میگید اصلن گره Gرو ندیدیم که بخایم از بین G و B انتخاب کنیم. اومدیم اولین گرهی که میتونستیم رو ساختیم و گذاشتیم تو صف.
(۲۶ آبان ۱۳۹۰ ۰۸:۰۴ ب.ظ)pos نوشته شده توسط:  همین طور در مرحله از بین C و D ابتدا f گره C را انتخاب کرده که f آن بزرگ‌تر هست
همین طور در این مرحله D رو ندیدیم اصلن

SMA* چگونه کار می کند. - pos - 26 آبان ۱۳۹۰ ۱۰:۱۳ ب.ظ

ممنون متوجه شدم چطور هست