ببینید مطمئناً SMA محدودیت حافظه‌ای داره. به نظر من این بستگی به مسئله٬ گراف٬ تعداد محدودیت‌های SMA - مقادیر تخمینی گره‌ها و... بستگی داره.

باز هم بسته به نوع مسئله حتا ممکنه SMA پاسخی برای یه مسئله‌ی خاص نداشته باشه ولی خب مشخصاً RBFS اینطور نیست.

از لحاظ مصرف حافظه sma* حافظه کمتری مصرف می کنه.

(۲۵ آذر ۱۳۹۰ ۰۷:۰۴ ب.ظ)pos نوشته شده توسط:  از لحاظ مصرف حافظه sma* حافظه کمتری مصرف می کنه.

لزوما این طور نیست!
الگوریتم RBFS در صورتی که از یک مسیر رفت و دید بهترین جواب در مسیری که داره می ره بیشتر از مقدار مسیر های دیگه بشه اون مقدار رو به نود پدر برمی گردونه و مسیر و بر می گرده(گره هایی که تولید و گسترش داده رو هم فراموش می کنه)
بنابراین حداکثر به اندازه ی( O(bd می تونه از فضا استفاده کنه و حتی بیشتر از اون هم اگر فضایی باشه نمی تونه ازش استفاده کنه!
اما تو الگوریتم SMA هر مقدار فضا بهش بدین از تمام اون مقدار فضا استفاده می کنه!چه فضا ۱کیلو بایت باشه چه ۱ ترابایت!
بنابر این نمی شه گفت که این الگوریتم لزوما فضای کمتر یا بیشتری مصرف می کنه!
هر چند که الگوریتم sma یه جاهایی گیر می کنه که اگر با الگوریتم های دیگه با فرض حافظه‌ی نا محدود جستجو انجام بشه براحتی به جواب می رسن!!!


در ضمن تو کتاب راسل به صراحت گفته الگوریتم RBFS از محدودیت حافظه رنج می بره!

فرض کنین طول مسیر مورد نظر ۳ باشه. sma-star به هیچ وجه در طول مسیریابیش بیشتر از سه خانه را در حافظه نگه نمیداره. ولی rbfs ممکن هست نیاز داشته باشه بیش از این مقدار گره را در حافظه نگه داره. ضمن اینکه sma-star کاربردش در مواقعی هست که حافظه کمی در اختیار داریم وگرنه اصلا چه نیازی به sma-star هست(اگر قرار باشه حافظه زیاد باشه که sma-star میشه همان a-star).

(۲۶ آذر ۱۳۹۰ ۰۸:۰۵ ب.ظ)mosaferkuchulu نوشته شده توسط:  هر چند که الگوریتم sma یه جاهایی گیر می کنه که اگر با الگوریتم های دیگه با فرض حافظه‌ی نا محدود جستجو انجام بشه براحتی به جواب می رسن!!!

خوب این به کارایی الگوریتم برمیگرده ضمن اینکه همانطور که گفتم اگر حافظه نامحدود باشه استفاده از sma-star بیخود هست چون نه تنها گره ای را از حافظه حذف نمی کنه بلکه مرتبا باید حافظه را چک کنه تا در صورت لزوم گره ای را خارج کنه که میشه کار اضافی.

(۲۶ آذر ۱۳۹۰ ۰۸:۰۵ ب.ظ)mosaferkuchulu نوشته شده توسط:  در ضمن تو کتاب راسل به صراحت گفته الگوریتم RBFS از محدودیت حافظه رنج می بره!

نا امیدم کرد
اشتباه چاپی نبوده؟

در مورد اینکه مربوط به کارایی هست که اس‌ام آ گیر می کنه!درسته من فقط یه توضیخ کلی داشتم می دادم.

در مورد فضای حافظه هم درسته که برای فضاهای خیلی کم کمتر مصرف می کنه اما همون طور که گفتم لزوما این طور نیست!به هر حال این الگوریتم رو می تونیم تو هر فضایی به کار ببریم!حتی اگر منطقی نباشه!

و در مورد اون جمله هم نه خیر!اشتباه تایپی نیست!اما شما نا امید نباشید!یه دور مرور کنین یاد اوری می شه و به ذهنتون می مونه!

نمی دانم والا. ولی فکر کنم یکجا یک سوال بود در همین مورد که گفته بود از بین الگوریتم های زیر کدام حافظه کمتری لازم داره؟ که این دوتا مدل هم بینشان بود و جواب داده بود sma*. فکر کنم کتاب آقای رهنمون بود. اگر پیداش کردم میگذارم که یک موقع اشتباهی پیش نیاد. شاید تو کنکور ازش سوال اومد.

(۲۶ آذر ۱۳۹۰ ۱۰:۴۵ ب.ظ)mosaferkuchulu نوشته شده توسط:  و در مورد اون جمله هم نه خیر!اشتباه تایپی نیست!اما شما نا امید نباشید!یه دور مرور کنین یاد اوری می شه و به ذهنتون می مونه!

از خودم که نا امید نشدم از راسل نا امید شدم

به نظر من کلاً بستگی به مسئله داره. توی یه مسئله‌ای ممکنه RBFS تو اولین جستجو مسیر بهینه رو پیدا کنه ولی توی گراف دیگه‌ای الزاماً اینطور نیست.

SMA هم بستگی به تعاریف مسئله٬ میتونه کامل نباشه اما چیزی که هست٬ RBFS اینطور نیست. ضمن اینکه حتا SMA میزان مراجعه‌ش به حافظه (برای حذف گره‌ای که ارزش کمتری داره) میتونه زیاد باشه. هر چند این توی RBFS در بیشتر٬ وضعیت بدتری داره.

من یه نگاهی به تست های پوران انداختم!تست شماره‌ی ۷ از فصل ۳ گفته الگوریتم‌ها رو بر اساس پیچیدگی مرتب کنین(پیچیدگی فضایی) !گزینه‌ی دو رو انتخاب کرده که به این صورت هست:
breadth first--->A*----->RBFS------>SMA


بر طبق این تست اس‌ام آ پیچیدگیش کمتره!
لطفا اگر کتاب تست دیگه ای دارین چک کنین!(جواب های خودم و نقض کردم به این می گن شهامت)
البته من هنوز فکر می کنم الزاما اینطور نیست!

(۲۷ آذر ۱۳۹۰ ۰۲:۰۳ ق.ظ)mosaferkuchulu نوشته شده توسط:  من یه نگاهی به تست های پوران انداختم!تست شماره‌ی ۷ از فصل ۳ گفته الگوریتم‌ها رو بر اساس پیچیدگی مرتب کنین(پیچیدگی فضایی) !گزینه‌ی دو رو انتخاب کرده که به این صورت هست:
breadth first--->A*----->RBFS------>SMA
بر طبق این تست اس‌ام آ پیچیدگیش کمتره!
لطفا اگر کتاب تست دیگه ای دارین چک کنین!(جواب های خودم و نقض کردم به این می گن شهامت)
البته من هنوز فکر می کنم الزاما اینطور نیست!

تست اعصاب خورد کنیه! من از روی کتاب گسترش علوم هم نگاه کردم چیز خاصی دستگیرم نشد.
شاید بشه گفت RBFS ممکن است در مسیری طولانی قرار بگیرد و بعدا متوجه بشه که باید به عقب برگشت پس تا اینجا کلی نود ذخیره کرده اما در SMA ممکن است با فضای اندک جواب رو در سطح نزدیک به ریشه پیدا کنه در حالی که در RBFS اول یه مسیر طولانی رو بررسی کرده و بعدا بازگشت کرده
البته این استدلال منه . نمی دونم درسته یا نه
البته با دوستان موافقم که بسته به مسئله داره . بنظرم در حالت کلی می تونیم بگیم مصرف sma بیشتره چون محدودیت بر روی سخت افزاره اما در RBFS همیشه از مرتبه خطی از اندازه مسئله حافظه مصرف میکنه یعنی حتی اگه هم بتونیم حافظه بیشتری بهش بدیم نمیدونه چیکارش کنه! .

(۲۷ آذر ۱۳۹۰ ۰۲:۰۳ ق.ظ)mosaferkuchulu نوشته شده توسط:  من یه نگاهی به تست های پوران انداختم!تست شماره‌ی ۷ از فصل ۳ گفته الگوریتم‌ها رو بر اساس پیچیدگی مرتب کنین(پیچیدگی فضایی) !گزینه‌ی دو رو انتخاب کرده که به این صورت هست:
breadth first--->A*----->RBFS------>SMA


بر طبق این تست اس‌ام آ پیچیدگیش کمتره!
لطفا اگر کتاب تست دیگه ای دارین چک کنین!(جواب های خودم و نقض کردم به این می گن شهامت)
البته من هنوز فکر می کنم الزاما اینطور نیست!

م در ۲ کتب مختلف و سوالای کنکورهای آزمایشی دیدم همین بود.درست هست

(۲۷ آذر ۱۳۹۰ ۰۲:۰۳ ق.ظ)mosaferkuchulu نوشته شده توسط:  لطفا اگر کتاب تست دیگه ای دارین چک کنین!(جواب های خودم و نقض کردم به این می گن شهامت)

خیلی خوابم میاد. اون تستی هم که من می گفتم همین بود. شاید من هم تو پوران دیده بودم. فردا نگاه می کنم.

مهندسی کامپیوتر سال ۸۷ )در مقایسه بین روش های مختلف جستجو از نظر حافظه بری اگر بخواهیم روش‌ها را از پیچیده ترین تا ساده ترین(از نظر پیچیدگی حافظه ای) مرتب کنیم کدام گزینه در اغلب موارد صحیح است؟

همان تستی هست که شما گذاشتین. اینجا هم گزینه دو را انتخاب کرده. یعنی:
breath first ->a-start -> RBFS -> SMA-Start

جواب آقای رهنمون‌: روش های rbfs و sma-star هر دو برای بهبود مدیریت حافظه در a-star طراحی شده اند. rbfs حداکثر میتوانداز O(bd) خانه حافظه در حین اجرا استفاده کند، حال آنکه sma-star قادر است از تمامی حافظه موجود استفاده کند و از این رو مدیریت بهتری نسبت به rbfs برای حافظه ارائه میدهد. شاید بهتر بود طراح پرسش بجای واژه‌ی حافظه بری از واژه های دیگری همانند "مدیریت حافظه" یا تخصیص حافظه مناسبتر استفاده می کرد. مسلما روش غیرآگاهانه اول - سطح نیاز به فضای مصرفی O(b^d) دارد که از دیگر روش‌ها ضعیف‌تر است.

خوب این طور که من فهمیدم گفته که مدیریت حفظه تو اس‌ام آ بهتره!اما لزوما نمی شه گفت کمتر یا بیشتره!درسته؟

درسته. منم همین به نظرم رسید. اون جمله کتاب راسل هم که گفته بودین به نظرم منظورش همین قسمت بوده که گفته فقط می تواند به اندازه O(bd) حافظه مصرف کند. اما باز به نظرمن sma مصرف حافظش کمتره ولی همانطور که میگین همیشه اینطور نیست.

MA* را یک توضیح کوچولو میدین؟

تو کتاب راسل فقط اسمش و اورده و توضیح نداده!
جایی از این الگوریتم سوالی اومده؟

من چون اولین بار بود دیدمش واسم سوال شد. می خواستم ببینم چه جوری هست.

تو کتاب راسل گفته شبیه اس‌ام آ استار هست!اما اس‌ام آ استار ساده‌تر هست!اما توضیح نداده!منم جای دیگه ندیدم که توضیح بدن!
دوستان لطفا اگر کسی این الگوریتم و می دونه یه توضیح مختصر بده!

(۰۲ بهمن ۱۳۹۱ ۰۶:۲۶ ب.ظ)drem نوشته شده توسط:  

نقل قول: من یه نگاهی به تست های پوران انداختم!تست شماره‌ی ۷ از فصل ۳ گفته الگوریتم‌ها رو بر اساس پیچیدگی مرتب کنین(پیچیدگی فضایی) !گزینه‌ی دو رو انتخاب کرده که به این صورت هست:
breadth first--->A*----->RBFS------>SMA


بر طبق این تست اس‌ام آ پیچیدگیش کمتره!
لطفا اگر کتاب تست دیگه ای دارین چک کنین!(جواب های خودم و نقض کردم به این می گن شهامت)
البته من هنوز فکر می کنم الزاما اینطور نیست!

م در ۲ کتب مختلف و سوالای کنکورهای آزمایشی دیدم همین بود.درست هست

کلید کنکور حرف شما رو تایید می کنه!
من تا حالا فکر می کردم گفته شما درسته اما تو کتاب راهیان نوشته:
"حافظه مصرفی SMA* از RBFS بیشتره!
چون SMA* از کل حافظه استفاده می کنه!"

بعد که یکم دقیق شدم و راسلو خوندم دیدم راهیان بد نمی گه!
SMA* هرچی حافظه بهش بدی تا تهش استفاد می کنه!کل RAM رو هم بهش بدی بدون هیچ هرسی همه رو استفاده می کنه!اما RBFS کلی CUT می کنه و سعی می کنه کمترین استفاده رو بکنه ها!!!
من که موندم والا!
هرچند بر اساس راسل حرف راهیان درسته!حالا تکلیف چیه؟!اگه تو کنکور اومد چی بزنیم؟!

SMA*حداکثر به اندازه ی حافظه موجود از حافظه مصرف میکند،درواقع تا وقتی درخت جستجو در حافظه قابل نگهداری باشد،مشابه *A عمل میکند،ولی از *A بهتر هست..
RBFS : پیچیدگی فضاییش خطی هست و از همه ی گزینه ها حافظه ی مصرفیش کمتر هست.
*A : این هم که نمایی
BFS :اینم که از همه بیشتر مصرف میکنه،نمایی+۱ خونه>چون فرزندان قبل از گره ی هدف در حافظه میماند
کتاب راهیان درست نوشته.

خب مشخصه که rbf کمترینه چون خطیه
اما بعدش اس ام آ هستش چون میتونه به بهترین شکل از حافظه ای که بهش دادین استفاده کنه
ببینید دوستان
توی مباحث مربوط به پیچیدگی همیشه یادتون باشه بدترین حالت رو در نظر بگبرید
که خوب اگه ما حالتی داشته باشیم که حافظه نمایی بخاد یا توان دوم یا هرچی اس ام آ این قابلیتو داره
اما ار بی اف همیشه خطیه