مقایسه روشهای مختلف جستجو از نظر حافظه بری از پیچیده ترین تا ساده ترین به چه صورته؟(تست کامپیوتر ۸۹)
پوران گفته:
BFS<A*<RBFS<SMA
راهیان گفته:
BFS<A*<SMA*<RBFS
حالا کدوم درسته؟
این دو الگوریتم مقایسشون تقریبا درست نیست . مگه اینکه میزان حافظه ی [tex]SMA^{*}[/tex] مشخص بشه . به طور کلی [tex]SMA^{*}[/tex] مانند [tex]A^{*}[/tex] هست . با این تفاوت که از یک حافظه ی محدود شده استفاده میکنیم .
دو حالت رو در نظر میگیریم :
اگه در یک حافظه نامحدود مقایسه رو انجام بدیم RBFS تعداد نود کمتری در حافظه نگه میداره . که البته این استدلال غلطه چون اساس [tex]SMA^{*}[/tex] استفاده از حافظه ی محدود شدست .
اگه حافظه رو محدود در نظر بگیریم مثلا در یک حافظه که میتونه ۱۰۰ تا نود رو نگه داره خب مسلما RBFS تعداد نود کمتری رو بازم در حافظه نگه میداره .
بنابراین میشه گفت که RBFS پیچیدگی مکانی کمتری داره و به این صورت میشه :
[tex]BFS < A^{*} < SMA^{*} <RBFS[/tex]
خوب این ۳ تا الگوریتم اومدن برای بهبود فضای مصرفی (حافظه)
طبق گفته رامین رهنمون که دقیقا میگه طبق کتاب راسل - نورویگ
*IDA از همه ضعیفتره!
RBFS کمی بهتره!
اما از همه بهتر *SMA است!
علت هم داره چون *SMA از صف اولویت نسبت به دوتای قبل استفاده میکنه فضای بیشتری از حافظه رو برای مدیریت حافظه اختصاص میده!
دوتای اول از پشته استفاده میکنند!
ولی *IDA یک ضعف جدی داره اونم اینه که از یک خانه استفاده میکنه!
RBFS هم از bd خانه استفاده میکنه!
در واقع این دوتا از فضای حافظه استفاده بهینه نمیکنند یکیشون به اندازه یک خونه یکیشون b ضربدر d خونه استفاده میکنه!
لینک ویدئو رامین رهنمون دقیقا این ویدئوش به مقایسه روشها در زمینه مدیریت حافظه میپردازه
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
(۰۷ آبان ۱۳۹۲ ۰۹:۲۸ ب.ظ)AMMehr نوشته شده توسط: خوب این ۳ تا الگوریتم اومدن برای بهبود فضای مصرفی (حافظه)
طبق گفته رامین رهنمون که دقیقا میگه طبق کتاب راسل - نورویگ
*IDA از همه ضعیفتره!
RBFS کمی بهتره!
اما از همه بهتر *SMA است!
علت هم داره چون *SMA از صف اولویت نسبت به دوتای قبل استفاده میکنه فضای بیشتری از حافظه رو برای مدیریت حافظه اختصاص میده!
دوتای اول از پشته استفاده میکنند!
ولی *IDA یک ضعف جدی داره اونم اینه که از یک خانه استفاده میکنه!
RBFS هم از bd خانه استفاده میکنه!
در واقع این دوتا از فضای حافظه استفاده بهینه نمیکنند یکیشون به اندازه یک خونه یکیشون b ضربدر d خونه استفاده میکنه!
لینک ویدئو رامین رهنمون دقیقا این ویدئوش به مقایسه روشها در زمینه مدیریت حافظه میپردازه
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
منظورتون اینه که جوابه راهیان درسته؟
تا اونجایی که من فهمیدم گفته ی پوران درست تره ولی خود نویسنده هم نمی دونه چرا
درمتن کتاب درمورد RBFS نوشته شده :پیچیدگی مکانی آن تابع خطی آن از عمق عمیق ترین راه حل بهینه است دلیلش اینه که امکان داره یک گره نزدیک به عمیقترین جواب باشه که این گره با یال های سبک به اونجا رسیده باشه و انجا یک فاصله ی بزرگ داشته باشه
در SMA دقیقا همون شرایط بالا برقرار ه
پس در مسائل بزرگ یک کار را انجام می دهند
پس دلیل اینکه SMA بهتر است :در مسائل خیلی بزرگ(خارج از حد حل شدن با حافظه ی موجود) حداکثر حافظه ای که به او داده شده است ثابت است ولی در RBFS این مقدار افزایش می یابد به طوری که از کنترل خارج و سیستم از کار می افتد
(در SMA احتمال دارد باز جواب پیدا شود)
درمورد IDA هم شبیه IDS هست با این تفاوت که dfs ای که اجرا می کند محدود به تابع f(n) می باشد و این تصور اشتباهه که فقط یک خانه ی حافظه در اختیار دارد
(۱۱ آبان ۱۳۹۲ ۰۹:۵۷ ق.ظ)afshin18 نوشته شده توسط: درمورد IDA هم شبیه IDS هست با این تفاوت که dfs ای که اجرا می کند محدود به تابع f(n) می باشد و این تصور اشتباهه که فقط یک خانه ی حافظه در اختیار دارد
البته به نظر من هنوزم این الگوریتم داره از یک خانه حافظه استفاده میکنه!
نکته رو کپی میکنم که براتون:
"الگوریتم *IDA بر خلاف *A نیازی به نگهداری گره های حاشیه در صف اولویت ندارد"
اما سوال سحر خانوم!
والا این سوال اینقدر گیج کنندس که سخت بشه فهمید جواب درست کدومه چون سوال داره میگه پیچیدگی فضایی!!! نه بهینگی در فضای مصرفی !!
در کل به نظر من گزینه ۲ که سازمان سنجش درست اعلام کرده رو باید مبنا قرار داد!
هر چند ایراد داره که نازنین خانوم هم گفتن ایراد رو!
یعنی ما بالاخره حافظه مون یک محدودیتی داره دیگه!
خوب *SMA تمام حافظه رو استفاده میکنه!
ولی RBFS پیچیدگی فضایی خطی داره! و از اونجایی که این الگوریتم کامل هست پس جواب رو پیدا میکنه با پیچیدگی فضایی خطی!!!
برای همین سوال رو حذف کنیم راحتریم
(۱۲ آبان ۱۳۹۲ ۰۳:۵۵ ق.ظ)AMMehr نوشته شده توسط:(11 آبان ۱۳۹۲ ۰۹:۵۷ ق.ظ)afshin18 نوشته شده توسط: درمورد IDA هم شبیه IDS هست با این تفاوت که dfs ای که اجرا می کند محدود به تابع f(n) می باشد و این تصور اشتباهه که فقط یک خانه ی حافظه در اختیار دارد
البته به نظر من هنوزم این الگوریتم داره از یک خانه حافظه استفاده میکنه!
نکته رو کپی میکنم که براتون:
"الگوریتم *IDA بر خلاف *A نیازی به نگهداری گره های حاشیه در صف اولویت ندارد"
اما سوال سحر خانوم!
والا این سوال اینقدر گیج کنندس که سخت بشه فهمید جواب درست کدومه چون سوال داره میگه پیچیدگی فضایی!!! نه بهینگی در فضای مصرفی !!
در کل به نظر من گزینه ۲ که سازمان سنجش درست اعلام کرده رو باید مبنا قرار داد!
هر چند ایراد داره که نازنین خانوم هم گفتن ایراد رو!
یعنی ما بالاخره حافظه مون یک محدودیتی داره دیگه!
خوب *SMA تمام حافظه رو استفاده میکنه!
ولی RBFS پیچیدگی فضایی خطی داره! و از اونجایی که این الگوریتم کامل هست پس جواب رو پیدا میکنه با پیچیدگی فضایی خطی!!!
برای همین سوال رو حذف کنیم راحتریم
من نگفتم که گره های حاشیه رو ذخیره می کنه گفتم چون از dfs استفاده می کنه گره ها از ریشه تا نود الانی رو در پشته ذخیره می کنه پس به اندازه ی ارتفاع درخت دخیره می کنه و فقط یک نود ذخیره نمی کنه
(۱۲ آبان ۱۳۹۲ ۰۵:۴۷ ق.ظ)afshin18 نوشته شده توسط:(12 آبان ۱۳۹۲ ۰۳:۵۵ ق.ظ)AMMehr نوشته شده توسط:(11 آبان ۱۳۹۲ ۰۹:۵۷ ق.ظ)afshin18 نوشته شده توسط: درمورد IDA هم شبیه IDS هست با این تفاوت که dfs ای که اجرا می کند محدود به تابع f(n) می باشد و این تصور اشتباهه که فقط یک خانه ی حافظه در اختیار دارد
البته به نظر من هنوزم این الگوریتم داره از یک خانه حافظه استفاده میکنه!
نکته رو کپی میکنم که براتون:
"الگوریتم *IDA بر خلاف *A نیازی به نگهداری گره های حاشیه در صف اولویت ندارد"
اما سوال سحر خانوم!
والا این سوال اینقدر گیج کنندس که سخت بشه فهمید جواب درست کدومه چون سوال داره میگه پیچیدگی فضایی!!! نه بهینگی در فضای مصرفی !!
در کل به نظر من گزینه ۲ که سازمان سنجش درست اعلام کرده رو باید مبنا قرار داد!
هر چند ایراد داره که نازنین خانوم هم گفتن ایراد رو!
یعنی ما بالاخره حافظه مون یک محدودیتی داره دیگه!
خوب *SMA تمام حافظه رو استفاده میکنه!
ولی RBFS پیچیدگی فضایی خطی داره! و از اونجایی که این الگوریتم کامل هست پس جواب رو پیدا میکنه با پیچیدگی فضایی خطی!!!
برای همین سوال رو حذف کنیم راحتریم
من نگفتم که گره های حاشیه رو ذخیره می کنه گفتم چون از dfs استفاده می کنه گره ها از ریشه تا نود الانی رو در پشته ذخیره می کنه پس به اندازه ی ارتفاع درخت دخیره می کنه و فقط یک نود ذخیره نمی کنه
پس پوران طبق سنجش جواب داده! من ترجیح میدم اونی رو که سنجش جواب گرفته حفظ کنم خدارو چه دیدی شاید تکراری دادن!
پارسه هم مثل پوران گفته که چون SMA روی حافظه مدیریت داره پس بهتر از RBFS هست
یه موضوع دیگه هم هست اینه که مثل بحث مجانب ها میشه بهش نگاه کرد که SMA همیشه بدون توجه به مسئله ، حافظه ثابتی داره ولی RBFS پیچیدگی خطی از عمق داره.
(۱۳ آبان ۱۳۹۲ ۰۹:۰۳ ب.ظ)zimenswall نوشته شده توسط: پارسه هم مثل پوران گفته که چون SMA روی حافظه مدیریت داره پس بهتر از RBFS هست
یه موضوع دیگه هم هست اینه که مثل بحث مجانب ها میشه بهش نگاه کرد که SMA همیشه بدون توجه به مسئله ، حافظه ثابتی داره ولی RBFS پیچیدگی خطی از عمق داره.
ولی مقایسه باید در شرایط مساوی انجام بشه . اینکه بگیم SMA حافظه ثابتی همیشه داره ولی RBFS نه، زمانی درست هست که برای RBFS حافظه نامحدود در نظر بگیریم و SMA رو با توجه به محدودیت بررسی کنیم . البته به صورت طبیعی این درسته اما قابل قبول نیست به نظرم...
نبودن شرایط مساوی رو قبول دارید؟
آخه داریم در مورد یه مسئله با دو شرط متفاوت بحث میکنیم! اصن میشه همچین چیزی؟