موضوع مقاله: الگوریتم‌های آگاهانه | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # الگوریتم‌های آگاهانه | مقدمه: استراتژی‌های جستجوی آگاهانه یا مکاشفه‌ای از دانش مسئله استفاده می‌کند و در انتخاب گره، گره ای را انتخاب می‌کنند که شانس رسیدن به هدف در آن بیشتر باشد یا به نظر آید که به هدف نزدیک تراست. | ## بخش 1: الگوریتم‌های آگاهانه | برای اینکه تخمین بزنیم که گره فرزند چقدر به هدف نزدیک تر است از تابع ارزیابی استفاده می‌کنیم. این تابع هزینه رسیدن به گره هدف راتخمین می‌زند و به عبارت دیگر میزان مفید بودن گره فعلی را بازمی‌گرداند. الگوریتم نخست-بهترین در این روش در هر مرتبه گرهی که بهترین ارزیابی را داشته باشد ابتدا بسط داده می‌شود به عبارت دیگر گرهی انتخاب می‌شود که تابع ارزیابی، بهترین مقدار را برای آن بازگرداند. برحسب اینکه تابع ارزیابی چگونه پیاده‌سازی شود، روش‌های گوناگونی از الگوریتم اول-بهترین خواهیم داشت. جستجوی اول-بهترین دو نوع کلی دارد که در یکی تابع ارزیابی هزینه رسیدن از گره فعلی به سمت هدف را حداقل می‌کند و در دومی هزینه کل مسیر از گره شروع تا هدف حداقل می‌شود. در این روش هدف به حداقل رساندن هزینه رسیدن به هدف با استفاده از تابع تخمین می‌باشد h(n . یعنی فقط kتا از بهترین گره‌ها کاندید برای توسعه دادن هستند و با بقیه از فهرست خارج می‌شوند. نکته: فضای حالت در این روش نسبت به روش حریصانه کاهش می‌یابد اما ممکن است که راه حل را از فهرست خارج کنیم این روش کامل و بهینه نیست. | ## بخش 2: الگوریتم‌های آگاهانه | جستجوی *A در جستجوی حریصانه با انتخاب تابع تخمین(h(n (که هزینه تخمینی رسیدن از گره فعلی به گره هدف بود) سعی می‌کردیم که سریع تر به سمت هدف حرکت نماییم و همچنین فضای حالت را کاهش دهیم اما این روش نه کامل بود و نه بهینه. از طرفی جستجو با هزینه یکسان با انتخاب تابع (g(n (که هزینه واقعی مسیر از ریشه تا گره n بود) در پی یافتن مسیری با حداقل هزینه بود که روشی بود کامل و بهینه اما می‌توانست بسیار زمان بر و در برخی موارد بی‌فایده باشد. حال می‌توانیم از این تکنیک استفاده نموده و هر بار یک جستجوی عمقی تا هزینه f-limite را جستجو کنیم. نکته ۱: محدودیت هزینه در هر مرحله به گونه‌ای انتخاب می‌شود که در مراحل قبلی ثابت شده‌است که جوابی با هزینه کمتر از این مقدار وجود ندارد. نکته ۲: می‌توان هزینه مرحله جدید را برابر با کمترین هزینه گرهی که در مرحله قبلی بسط داده نشده قرار داد از آنجا که این روش به صورت عمقی است پس پیچیدگی فضایی آن در بدترین حالت (S(b.d است. 3- در صورتی کامل است که حافظه برای ذخیره کم عمق‌ترین مسیر راه حل وجود داشته باشد. 4- در صورتی بهینه‌است که حافظه کافی برای ذخیره کم عمق‌ترین مسیر راه حل وجود داشته باشد. الگوریتم: زمانی که نیاز به تولید فرزند باشد ولی حافظه‌ای در اختیار نداشته باشیم نیاز به نوشتن مجدد به روی حافظه قبلی است. | ## بخش 3: الگوریتم‌های آگاهانه | برای انجام این امر الگوریتم یک گره را حذف می‌کند و فرزند جدید از حافظه آن استفاده خواهد کرد. برای جلوگیری از جستجوی مجدد زیر درخت‌هایی که از حافظه حذف شده‌اند، در گره پدر آنها اطلاعاتی در مورد کیفیت بهترین مسیر در زیر درخت فراموش شده نگهداری می‌شود. بدین طریق فقط زمانی زیر درخت‌ها دوباره تولید می‌شوند که ثابت شود تمام مسیرهای دیگر بدتر از مسیر فراموش شده باشد. الگوریتم تپه نوردی تپه نوردی نمونه‌ای از الگوریتم‌های جستجوی آگاهانه می‌باشد چرا که از اطلاعاتی در مورد فضای جستجو به منظور جستجو و با استفاده از یک راه کار منطقی استفاده می‌نماید. اگر سعی داشته باشید تا در حالیکه فقط یک ارتفاع سنج در اختیاردارید و نقشه نیز ندارید از یک تپه بالا بروید می‌توانید از روش تولید و تست تپه نوردی استفاده نمایید. در هر مرحله بررسی نمایید تا ببینید در کدام جهت (شمال، جنوب، شرق و غرب)، ارتفاع قدری بیشتر است؛ به محض اینکه موقعیتی را پیدا کردید که ارتفاع در آن موقعیت بیشتر از موقعیت فعلی تان می‌باشد به آنجا بروید و الگوریتم را از اول تکرار کنید. اگر همه جهت‌ها ارتفاع کمتری نسبت به موقعیت فعلی تان دارند توقف نمایید و چنین تصور کنید که به محلی که خواسته‌اید رسیده‌اید. (بخاطر وجود بیشینه‌های محلی که در آن نقاط ماکزیمم نسبی، ظاهراً نسبت به تمام نقاط اطرافش وضعیت بهتری دارد اما نسبت به کل مسیر لزوماً بهترین نیست) تپه نوردی شما را در یک درخت جستجو به سمت اولین نود بعدی که نسبت به نود فعلی بهتر باشد رهنمون می‌سازد. | ## جمع‌بندی | در میان نودهای در دسترس مستقیم یک نود، نودی بهتر خواهد بود که نسبت به نود فعلی مقدار مکاشفه‌ای کمتری داشته باشد.