۰
subtitle
ارسال: #۱
  
SMA* چگونه کار می کند.
توی بقیه A*ها مسیری را انتخاب میکنه که f کوچکتری داره. چرا توی عکس زیر بعد از انتخاب A از بین Bو G اول Bرا انتخاب کرد در صورتی که G مسیر کوتاهتری را داره نشان میده (F کوچکتری داره). یا مثلا توی تصویر زیر با اینکه به جواب I رسید باز هم به مسیر داره ادامه میده. از کجا می فهمه I بهینه نیست؟
ممنون.
ممنون.
۰
ارسال: #۲
  
RE: SMA* چگونه کار می کند.
(۲۶ آبان ۱۳۹۰ ۱۲:۵۵ ب.ظ)pos نوشته شده توسط: توی بقیه A*ها مسیری را انتخاب میکنه که f کوچکتری داره. چرا توی عکس زیر بعد از انتخاب A از بین Bو C اول Bرا انتخاب کرد در صورتی که C مسیر کوتاهتری را داره نشان میده (F کوچکتری داره). یا مثلا توی تصویر زیر با اینکه به جواب I رسید باز هم به مسیر داره ادامه میده. از کجا می فهمه I بهینه نیست؟
ممنون.
سلام.
ویژگی ها:
این روش از حافظه موجود برای جستجو استفاده می کند.
هر اندازه که حافظه در اختیارش اجازه دهد، می تواند از حالت های تکراری دوری کند.
اگر حافظه در دسترس آن، برای ذخیره سازی مسیر کم عمقترین پاسخ کافی باشد، کامل خواهد بود.
اگر حافظه در دسترس آن، برای ذخیره سازی مسیر بهترین پاسخ کافی باشد، بهینه خواهد بود.
به عبارت دیگر این روش، بهترین جوابی را که با حافظه در دسترسش می تواند دست یابد، باز می گرداند.
خلاصه روش:
در این روش هنگامی که بخواهیم فرزند را تولید کنیم و بر روی صف حافظه ای موجود نباشد، آن گاه گره هایی را از صف حذف می کنیم. به این گرهها، فراموش شده گویند.
در این کار گره هایی را که امید چندانی به آنها نداریم از صف حذف خواهد شد( یعنی گره با f بیشتر)
برای اجتناب از کاوش دوباره زیر درختی که از حافظه حذف شده است، باید اطلاعات مربوط به بهترین مسیر در زیر درخت فراموش شده را در گره پدر ذخیره کرد. بدین ترتیب فقط هنگامی این زیر درخت باز تولید خواهد شد که مشخص شود تمامی سایر مسیرها، نسبت به این زیر درخت بدتر به نظر آیند.
در مثال شما فرض شده است کهفقط اطلاعات ۳ گره را می توان حفظ کرد.
سوال اولتون رو اگر منظورتون b , g هست، g، مقدار f کمتری داره.
سوال دومتون چون به یه پاسخ با هزینه ۲۴ رسیده ولی تو گره های پدری (اینجا A) جلوش نوشتیم ۱۵ یعنی یه زیر درختی رو ازش فراموش کردیم که مقدار f معادل ۱۵ داشته.
اما توی مرحل آخر، پدر و پدربزرگ قبول کردن که زیردرختی بهتر از این نداشتن...
تلاشم رو کردم که کامل متوجه بشید حالا چقدر موفق بودم نمیدونم
۰
ارسال: #۳
  
SMA* چگونه کار می کند.
جواب قسمت دوم را متوجه شدم ولی قسمت اول را نه.
ببینین توی عکسی که گذاشتم در قسمت پایین توی ۸ مرحله مراحل کار را کشیده. در مرحله دوم از بین G و B ابتدا B را انتخاب کرده در صورتی که f(b)=15 و f(g)=13 هست. یعنی f بزرگتر را انتخاب کرده. همین طور در مرحله از بین C و D ابتدا f گره C را انتخاب کرده که f آن بزرگتر هست
ممنون
ببینین توی عکسی که گذاشتم در قسمت پایین توی ۸ مرحله مراحل کار را کشیده. در مرحله دوم از بین G و B ابتدا B را انتخاب کرده در صورتی که f(b)=15 و f(g)=13 هست. یعنی f بزرگتر را انتخاب کرده. همین طور در مرحله از بین C و D ابتدا f گره C را انتخاب کرده که f آن بزرگتر هست
(۲۶ آبان ۱۳۹۰ ۰۶:۵۹ ب.ظ)nfe89 نوشته شده توسط: سوال اولتون رو اگر منظورتون b , g هست، g، مقدار f کمتری داره.بله منظورم همان G بود. سوال را ویرایش کردم.
ممنون
ارسال: #۴
  
RE: SMA* چگونه کار می کند.
(۲۶ آبان ۱۳۹۰ ۰۸:۰۴ ب.ظ)pos نوشته شده توسط: در مرحله دوم از بین G و B ابتدا B را انتخاب کرده در صورتی که f(b)=15 و f(g)=13 هست. یعنی f بزرگتر را انتخاب کرده.ببین ما کلا توی صف جای سه حالت رو داریم اینجا .
بخاطر این محدودیت تو هر مرحله نمیاد همه فرزندا رو بسازه.
این مراحلی که کشیده خاسته بگه تو هر نوبت کدوم گرهها تو صف هستن.
اگه تو صف جا بود اولینی که میتونه رو میسازه. اگه نه بدترین f رو از صف حذف میکنه بعد میسازه.
ینی مرحله دوم که میگید اصلن گره Gرو ندیدیم که بخایم از بین G و B انتخاب کنیم. اومدیم اولین گرهی که میتونستیم رو ساختیم و گذاشتیم تو صف.
(۲۶ آبان ۱۳۹۰ ۰۸:۰۴ ب.ظ)pos نوشته شده توسط: همین طور در مرحله از بین C و D ابتدا f گره C را انتخاب کرده که f آن بزرگتر هستهمین طور در این مرحله D رو ندیدیم اصلن
۰
Can I see some ID?
Feeling left out?
نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close