تالار گفتمان مانشت

سلام‌، کسی از دوستان می تونه در مورد کاریی و مشخصات این دو الگوریتم جستجو راهنمایی‌ام کنه؟
تا یه حدی نحوه کار کردشون رو می دونم اما از لحاظ کاریی میخواستم باهم مقایسه کنیم‌، کدوم بهتره‌، حافظه کمتری نیاز داره و ...

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

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

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

(25 آذر 1390 07:04 ب.ظ)pos نوشته شده توسط: [ -> ]از لحاظ مصرف حافظه sma* حافظه کمتری مصرف می کنه.

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


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

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

(26 آذر 1390 08:05 ب.ظ)mosaferkuchulu نوشته شده توسط: [ -> ]هر چند که الگوریتم sma یه جاهایی گیر می کنه که اگر با الگوریتم های دیگه با فرض حافظه‌ی نا محدود جستجو انجام بشه براحتی به جواب می رسن!!!

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

(26 آذر 1390 08:05 ب.ظ)mosaferkuchulu نوشته شده توسط: [ -> ]در ضمن تو کتاب راسل به صراحت گفته الگوریتم RBFS از محدودیت حافظه رنج می بره!

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

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

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

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

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

(26 آذر 1390 10:45 ب.ظ)mosaferkuchulu نوشته شده توسط: [ -> ]و در مورد اون جمله هم نه خیر!اشتباه تایپی نیست!اما شما نا امید نباشید!یه دور مرور کنین یاد اوری می شه و به ذهنتون می مونه!

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

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

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

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


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

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

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

(27 آذر 1390 02:03 ق.ظ)mosaferkuchulu نوشته شده توسط: [ -> ]لطفا اگر کتاب تست دیگه ای دارین چک کنین!(جواب های خودم و نقض کردم به این می گن شهامت)

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

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

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

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

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

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

دوستان من تعابیر راسل رو اینجا میارم٬ در این موارد هم اگر موافق باشید٬ بحث کنیم:

۱. RBFS از مشکل تولید مجدد گره‌های زیاد رنج می‌برد.
۲. RBFS از استفاده‌ی بسیار اندک از حافظه نیز رنج می‌برد. (میشه این رو با مورد ۱ مقایسه کرد)
۳. MA* و SMA* دو الگوریتمی هستند که از تمامی حافظه‌ی قابل دسترس استفاده می‌کنند.
۴. مسائلی که عملاً در A* با فرض حافظه‌ی نامحدود قابل حل هستند٬ برای SMA* مهارنشدنی هستند.