زمان کنونی: ۲۴ آذر ۱۳۹۷, ۱۱:۴۲ ب.ظ مهمان گرامی به انجمن مانشت خوش آمدید. برای استفاده از تمامی امکانات انجمن می‌توانید عضو شوید.
گزینه‌های شما (ورودثبت نام)

کاریی و مشخصات این دو الگوریتم: *RBFS vs SMA

ارسال:
  

lonelyforever پرسیده:

کاریی و مشخصات این دو الگوریتم: *RBFS vs SMA

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

۰
ارسال:
  

Mohammad-A پاسخ داده:

RBFS vs SMA*

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

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

۰
ارسال:
  

Mohammad-A پاسخ داده:

RBFS vs SMA*

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

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

۰
ارسال:
  

pos پاسخ داده:

RBFS vs SMA*

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

ارسال:
  

mosaferkuchulu پاسخ داده:

RE: RBFS vs SMA*

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

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


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

۰
ارسال:
  

pos پاسخ داده:

RBFS vs SMA*

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

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


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

۰
ارسال:
  

mosaferkuchulu پاسخ داده:

RBFS vs SMA*

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

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

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

۰
ارسال:
  

pos پاسخ داده:

RBFS vs SMA*

نمی دانم والا. ولی فکر کنم یکجا یک سوال بود در همین مورد که گفته بود از بین الگوریتم های زیر کدام حافظه کمتری لازم داره؟ که این دوتا مدل هم بینشان بود و جواب داده بود sma*. فکر کنم کتاب آقای رهنمون بود. اگر پیداش کردم میگذارم که یک موقع اشتباهی پیش نیاد. شاید تو کنکور ازش سوال اومد.
(۲۶ آذر ۱۳۹۰ ۱۰:۴۵ ب.ظ)mosaferkuchulu نوشته شده توسط:  و در مورد اون جمله هم نه خیر!اشتباه تایپی نیست!اما شما نا امید نباشید!یه دور مرور کنین یاد اوری می شه و به ذهنتون می مونه!Big Grin

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

۰
ارسال:
  

Mohammad-A پاسخ داده:

RBFS vs SMA*

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

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

۰
ارسال: #۱۰
  

mosaferkuchulu پاسخ داده:

RBFS vs SMA*

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


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

ارسال: #۱۱
  

Masoud05 پاسخ داده:

RE: RBFS vs SMA*

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

ارسال: #۱۲
  

drem پاسخ داده:

RE: RBFS vs SMA*

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


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

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

۰
ارسال: #۱۳
  

pos پاسخ داده:

RBFS vs SMA*

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

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

۰
ارسال: #۱۴
  

pos پاسخ داده:

RBFS vs SMA*

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

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

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

۰
ارسال: #۱۵
  

mosaferkuchulu پاسخ داده:

RBFS vs SMA*

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

۰
ارسال: #۱۶
  

pos پاسخ داده:

RBFS vs SMA*

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

۰
ارسال: #۱۷
  

pos پاسخ داده:

RBFS vs SMA*

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

۰
ارسال: #۱۸
  

mosaferkuchulu پاسخ داده:

RBFS vs SMA*

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

۰
ارسال: #۱۹
  

pos پاسخ داده:

RBFS vs SMA*

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

۰
ارسال: #۲۰
  

mosaferkuchulu پاسخ داده:

RBFS vs SMA*

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

۰
ارسال: #۲۱
  

۸Operation پاسخ داده:

کاریی و مشخصات این دو الگوریتم: *RBFS vs SMA

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


بر طبق این تست اس‌ام آ پیچیدگیش کمتره!
لطفا اگر کتاب تست دیگه ای دارین چک کنین!(جواب های خودم و نقض کردمBig Grin به این می گن شهامت)
البته من هنوز فکر می کنم الزاما اینطور نیست!
م در ۲ کتب مختلف و سوالای کنکورهای آزمایشی دیدم همین بود.درست هست
کلید کنکور حرف شما رو تایید می کنه!
من تا حالا فکر می کردم گفته شما درسته اما تو کتاب راهیان نوشته:
"حافظه مصرفی SMA* از RBFS بیشتره!
چون SMA* از کل حافظه استفاده می کنه!"

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

۰
ارسال: #۲۲
  

jameshenas پاسخ داده:

کاریی و مشخصات این دو الگوریتم: *RBFS vs SMA

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

۰
ارسال: #۲۳
  

mohandeszahra پاسخ داده:

RE: کاریی و مشخصات این دو الگوریتم: *RBFS vs SMA

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



موضوع‌های مرتبط با این موضوع...
موضوع: نویسنده پاسخ: بازدید: آخرین ارسال
  نوشتن این روابط با prolog mahyar_delsuz ۴ ۱,۴۴۶ ۱۴ اردیبهشت ۱۳۹۱ ۰۱:۵۴ ب.ظ
آخرین ارسال: mahyar_delsuz
  SMA* چگونه کار می کند. pos ۴ ۲,۱۲۲ ۲۶ آبان ۱۳۹۰ ۱۰:۱۳ ب.ظ
آخرین ارسال: pos

پرش به انجمن:

Can I see some ID?

به خاطر سپاری رمز Cancel

Feeling left out?


نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close

رمزت رو فراموش کردی؟

Feeling left out?


نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. close