بدست اوردن پیچیدگی زمانی ومکانی الگوریتمهای RBFS و IDA* و SMA* - نسخه‌ی قابل چاپ

بدست اوردن پیچیدگی زمانی ومکانی الگوریتمهای RBFS و IDA* و SMA* - saho - 03 اردیبهشت ۱۳۹۱ ۰۶:۳۱ ب.ظ سلام به دوستان کسی میتونه راه حل بدست اوردن پیچیدگی زمانی ومکانی الگوریتم های Rbfsوida*وsma*رو برام بنویسه؟

بدست اوردن پیچیدگی زمانی ومکانی - yaser_ilam_com - 03 اردیبهشت ۱۳۹۱ ۰۹:۵۳ ب.ظ دو تا مقاله قرار دادم امیدوارم بدردت بخوره البته در مورد ida,sma منبع ویکی پیدا : A * Search در جستجوی حریصانه با انتخاب تابع تخمین(h(n که هزینهٔ تخمینی رسیدن از نود فعلی به نود هدف بود سعی می‌کردیم که سریع تر به سمت هدف حرکت نماییم و همچنین فضای حالت را کاهش دهیم اما این روش نه کامل بود و نه بهینه. از طرفی در جستجو با هزینهٔ یکسان با انتخاب تابع(g(n که هزینهٔ واقعی مسیر از ریشه تا نود n بود در پی یافتن مسیری با حداقل هزینه بود که روشی بود کامل و بهینه اما می‌توانست بسیار زمان بر بوده و در برخی موارد بی فایده باشد. برای دستیابی به مزایای هر دو جستجو از ترکیب این دو روش تحت عنوان جستجوی A* استفاده می‌کنیم که تابع ارزیابی آن به صورت زیر است: (f(n)=h(n)+g(n (h(nهزینه تخمینی برای رسیدن از نود n ازارزانترین راه به هدف (g(n :هزینهٔ رسیدن از نود ریشه به نود n == جستجوی *Intractive deeping A*) IDA) == می‌دانیم که جستجوی عمیق کننده تکراری تکنیکی مفید برای کاهش درخواست حافظه‌است حال می‌توانیم از این تکنیک استفاده نموده و هر بار یک جستجوی عمقی تا هزینهٔ f-cost را جستجو کنیم. اگر به جواب نرسیدیم هزینه f-cost را افزایش داده و از اول به بسط فضای حالت می‌پردازیم. نکته ۱: محدودیت هزینه در هر مرحله به گونه‌ای انتخاب می‌شود که در مراحل قبلی ثابت شده‌است که جوابی با هزینهٔ کمتر از این مقدار وجود ندارد. نکته ۲: می‌توان هزینه مرحله جدید را برابر با کمترین هزینهٔ نودی که در مرحله قبلی بسط داده نشده قرار داد از آنجا که این روش به صورت عمقی است پس پیچیدگی فضایی آن در بدترین حالت (S(b.d است. نکته ۳: پیچیدگی زمانی بستگی به تابع اکتشافی دارد. نکته ۴: این روش نیز مشابه *A کامل و بهینه‌است جستجوی *Simplified Memory Bounded A*) SMA) [ویرایش] در روش قبلی(*IDA)استفاده بسیار جزئی از حافظه داشت و بین تکرارها این جستجو فقط یک عدد خاص از محدوده جاری را نگه می‌داشت (f-cost) و چون نمی‌توانست تاریخچه اش را به خاطر آورد مجبور به تکرار می‌شد الگوریتم *SMA قادر خواهد بود تا از تمام حافظه موجود برای اجرای جستجو استفاده نماید هرچه حافظه بیشتر باشد کارآیی جستجو بالاتر خواهد بود. ویژگی ها ۱ می‌توان از تمام حافظه مورد دسترس خود استفاده کرد. ۲ تا جایی که حافظ اجازه می‌دهد از تولید حالات تکراری جلوگیری می‌کند. ۳ در صورتی کامل است که حافظه برای ذخیره کم عمق‌ترین مسیر راه حل وجود داشته باشد. ۴ در صورتی بهینه‌است که حافظهٔ کافی برای ذخیره کم عمق‌ترین مسیر راه حل وجود داشته باشد. الگوریتم: زمانی که نیاز به تولید فرزند باشد ولی حافظه‌ای در اختیار نداشته باشیم نیاز به نوشتن مجدد به روی حافظه قبلی است برای انجام این امر الگوریتم یک گره را حذف می‌کند و فرزند جدید از حافظه آن استفاده خواهد کرد گره‌هایی که بدین طریق حذف می‌شوند گره‌های فراموش شده نام دارند. همیشه گره‌هایی برای حذف شدن انتخاب می‌شوند که هزینهٔ آﻧﻬا بالا است. برای جلوگیری از جستجوی مجدد زیر درخت‌هایی که از حافظه حذف شده‌اند، در گره پدر آﻧﻬا اطلاعاتی در مورد کیفیت بهترین مسیر در زیر درخت فراموش شده نگهداری می‌شود. بدین طریق فقط زمانی زیر درخت‌ها دوباره تولید می‌شوند که ثابت شود تمام مسیرهای دیگر بدتر از مسیر فراموش شده باشد.