الگوریتم‌های آگاهانه
استراتژی‌های جستجوی آگاهانه یا مکاشفه‌ای از دانش مسئله استفاده می‌کند و در انتخاب گره، گره ای را انتخاب می‌کنند که شانس رسیدن به هدف در آن بیشتر باشد یا به نظر آید که به هدف نزدیک تراست. برای اینکه تخمین بزنیم که گره فرزند چقدر به هدف نزدیک تر است از تابع ارزیابی استفاده می‌کنیم. این تابع هزینه رسیدن به گره هدف راتخمین می‌زند و به عبارت دیگر میزان مفید بودن گره فعلی را بازمی‌گرداند.
الگوریتم نخست-بهترین
در این روش در هر مرتبه گرهی که بهترین ارزیابی را داشته باشد ابتدا بسط داده می‌شود به عبارت دیگر گرهی انتخاب می‌شود که تابع ارزیابی، بهترین مقدار را برای آن بازگرداند. برحسب اینکه تابع ارزیابی چگونه پیاده‌سازی شود، روش‌های گوناگونی از الگوریتم اول-بهترین خواهیم داشت. جستجوی اول-بهترین دو نوع کلی دارد که در یکی تابع ارزیابی هزینه رسیدن از گره فعلی به سمت هدف را حداقل می‌کند و در دومی هزینه کل مسیر از گره شروع تا هدف حداقل می‌شود.
جستجوی حریصانه (Greedy Search)
جستجوی حریصانه یکی از روش‌های جستجوی نخست-بهترین است. در این روش هدف به حداقل رساندن هزینه رسیدن به هدف با استفاده از تابع تخمین می‌باشد ((h(n)). بدین صورت که گرهی که به هدف نزدیکتر است ابتدا بسط داده می‌شود. تابع ارزیابی که هزینه رسیدن از یک حالت (حالت فعلی) به حالت هدف را تخمین می‌زند تابع اکتشافی(Heuristic_search) نام دارد و با حرف H بیان می‌گردد.
(h(n:هزینه تخمین زده شده از ارزان‌ترین مسیر از گره n به هدف.
Beam Search
دقیقاً همانند جستجوی حریصانه‌است با این تفاوت که در open list آن حداکثر k عضو وجود دارد. یعنی فقط kتا از بهترین گره‌ها کاندید برای توسعه دادن هستند و با بقیه از فهرست خارج می‌شوند.
نکته:
فضای حالت در این روش نسبت به روش حریصانه کاهش می‌یابد اما ممکن است که راه حل را از فهرست خارج کنیم این روش کامل و بهینه نیست.
جستجوی *A
در جستجوی حریصانه با انتخاب تابع تخمین(h(n (که هزینه تخمینی رسیدن از گره فعلی به گره هدف بود) سعی می‌کردیم که سریع تر به سمت هدف حرکت نماییم و همچنین فضای حالت را کاهش دهیم اما این روش نه کامل بود و نه بهینه. از طرفی جستجو با هزینه یکسان با انتخاب تابع (g(n (که هزینه واقعی مسیر از ریشه تا گره n بود) در پی یافتن مسیری با حداقل هزینه بود که روشی بود کامل و بهینه اما می‌توانست بسیار زمان بر و در برخی موارد بی‌فایده باشد. برای دستیابی به مزایای هر دو جستجو از ترکیب این دو روش تحت عنوان جستجوی A* استفاده می‌کنیم که تابع ارزیابی آن به صورت زیر است:
(f(n)=h(n)+g(n
(h(n: هزینه تخمینی برای رسیدن از گره n ازارزانترین راه به هدف
(g(n: هزینه رسیدن از گره ریشه به گره n
جستجوی *Intractive deeping A*) IDA)
می‌دانیم که جستجوی عمیق کننده تکراری، تکنیکی مفید برای کاهش درخواست حافظه‌است. حال می‌توانیم از این تکنیک استفاده نموده و هر بار یک جستجوی عمقی تا هزینه f-limite را جستجو کنیم. اگر به جواب نرسیدیم هزینه f-limite را افزایش داده و از اول به بسط فضای حالت می‌پردازیم.
نکته ۱: محدودیت هزینه در هر مرحله به گونه‌ای انتخاب می‌شود که در مراحل قبلی ثابت شده‌است که جوابی با هزینه کمتر از این مقدار وجود ندارد.
نکته ۲: می‌توان هزینه مرحله جدید را برابر با کمترین هزینه گرهی که در مرحله قبلی بسط داده نشده قرار داد از آنجا که این روش به صورت عمقی است پس پیچیدگی فضایی آن در بدترین حالت (S(b.d است.
نکته ۳: پیچیدگی زمانی بستگی به تابع اکتشافی دارد.
نکته ۴: این روش نیز مشابه *A کامل و بهینه‌است.
جستجوی *Simplified Memory Bounded A*) SMA)
در روش قبلی، *IDA استفاده بسیار جزئی از حافظه داشت و بین تکرارها این جستجو فقط یک عدد خاص از محدوده جاری را نگه می‌داشت (f-cost) و چون نمی‌توانست تاریخچه اش را به خاطر آورد مجبور به تکرار می‌شد الگوریتم *SMA قادر خواهد بود تا از تمام حافظه موجود برای اجرای جستجو استفاده نماید. هرچه حافظه بیشتر باشد کارایی جستجو بالاتر خواهد بود.
ویژگی‌ها
1- می‌توان از تمام حافظه مورد دسترس خود استفاده کرد.
2- تا جایی که حافظ اجازه می‌دهد از تولید حالات تکراری جلوگیری می‌کند.
3- در صورتی کامل است که حافظه برای ذخیره کم عمق‌ترین مسیر راه حل وجود داشته باشد.
4- در صورتی بهینه‌است که حافظه کافی برای ذخیره کم عمق‌ترین مسیر راه حل وجود داشته باشد.
زمانی که نیاز به تولید فرزند باشد ولی حافظه‌ای در اختیار نداشته باشیم نیاز به نوشتن مجدد به روی حافظه قبلی است. برای انجام این امر الگوریتم یک گره را حذف می‌کند و فرزند جدید از حافظه آن استفاده خواهد کرد. گره‌هایی که بدین طریق حذف می‌شوند گره‌های فراموش شده نام دارند. همیشه گره‌هایی برای حذف شدن انتخاب می‌شوند که هزینه آنها بالا است. برای جلوگیری از جستجوی مجدد زیر درخت‌هایی که از حافظه حذف شده‌اند، در گره پدر آنها اطلاعاتی در مورد کیفیت بهترین مسیر در زیر درخت فراموش شده نگهداری می‌شود. بدین طریق فقط زمانی زیر درخت‌ها دوباره تولید می‌شوند که ثابت شود تمام مسیرهای دیگر بدتر از مسیر فراموش شده باشد.
الگوریتم تپه نوردی
تپه نوردی نمونه‌ای از الگوریتم‌های جستجوی آگاهانه می‌باشد چرا که از اطلاعاتی در مورد فضای جستجو به منظور جستجو و با استفاده از یک راه کار منطقی استفاده می‌نماید. اگر سعی داشته باشید تا در حالیکه فقط یک ارتفاع سنج در اختیاردارید و نقشه نیز ندارید از یک تپه بالا بروید می‌توانید از روش تولید و تست تپه نوردی استفاده نمایید.
در هر مرحله بررسی نمایید تا ببینید در کدام جهت (شمال، جنوب، شرق و غرب)، ارتفاع قدری بیشتر است؛ به محض اینکه موقعیتی را پیدا کردید که ارتفاع در آن موقعیت بیشتر از موقعیت فعلی تان می‌باشد به آنجا بروید و الگوریتم را از اول تکرار کنید.
اگر همه جهت‌ها ارتفاع کمتری نسبت به موقعیت فعلی تان دارند توقف نمایید و چنین تصور کنید که به محلی که خواسته‌اید رسیده‌اید. البته لزومی ندارد که این تصور همواره درست باشد! (بخاطر وجود بیشینه‌های محلی که در آن نقاط ماکزیمم نسبی، ظاهراً نسبت به تمام نقاط اطرافش وضعیت بهتری دارد اما نسبت به کل مسیر لزوماً بهترین نیست)
تپه نوردی شما را در یک درخت جستجو به سمت اولین نود بعدی که نسبت به نود فعلی بهتر باشد رهنمون می‌سازد. در میان نودهای در دسترس مستقیم یک نود، نودی بهتر خواهد بود که نسبت به نود فعلی مقدار مکاشفه‌ای کمتری داشته باشد.
منابع
- ↑ شایگان، عادله (۲۱). a*جستجویحریصانه. عادله.