الگوریتم جستجو

در علوم کامپیوتر و ریاضیات، یک الگوریتم جستجو، الگوریتمی است که یک مسئله را به عنوان ورودی می‌گیرد و بعد از ارزیابی کردن راه حل‌های ممکن، یک راه حل برای آن مسئله برمی‌گرداند. مجموعهٔ راه حل‌های ممکن برای یک مسئله را فضای جستجو می‌نامند. بعضی از الگوریتم‌ها که با عنوان الگوریتم‌های ناآگاهانه شناخته می‌شوند الگوریتم‌هایی هستند که از متدهای ساده‌ای برای جستجوی فضای نمونه استفاده می‌کنند. در حالی که الگوریتم‌های آگاهانه با استفاده روش‌هایی مبتنی بر دانش در بارهٔ ساختار فضای جستجو، می‌کوشند تا زمان جستجو را کاهش دهند.

رده‌بندی

در کتاب راسل این الگوریتم‌ها به شکل زیر رده‌بندی شده‌اند.

• الگوریتم‌های ناآگاهانه
  • الگوریتم نخست-پهنا
  • الگوریتم نخست-ژرفا
• الگوریتم‌های آگاهانه
  • الگوریتم نخست-بهترین
  • الگوریتم مکاشفه‌ای

جستجوی ناآگاهانه

یک الگوریتم جستجوی ناآگاهانه الگوریتمی است که به ماهیت مسئله کاری ندارد. از این رو می‌توانند به‌طور عمومی طراحی شوند و از همان طراحی برای محدودهٔ عظیمی از مسائل استفاده کنند، این امر نیاز به طراحی انتزاعی دارد. از جمله مشکلاتی که این چنین الگوریتم‌هایی دارند این است که اغلب فضای جستجو بسیار بزرگ است و نیازمند زمان زیادی (حتی برای نمونه‌های کوچک) می‌باشد. از این رو برای بالا بردن سرعت پردازش غالباً از الگوریتم‌های آگاهانه استفاده می‌کنند.

در این نوع الگوریتم‌ها، اگر اطلاعات اضافی دربارهٔ نودهایی (گره‌هایی) که هنوز بیان و بسط داده نشده‌اند نداشته باشد تا بتواند تصمیم بگیرد که ابتدا کدام نود را بررسی نماید به عبارت دیگر روش‌های جستجویی که از مکاشفه استفاده نمی‌کنند غیر فعال هستند.

روش‌های جستجوی ناآگاهانه عبارتند از:

1. الگوریتم جستجوی اول سطح
2. الگوریتم جستجوی اول عمق
3. الگوریتم جستجو با هزینه یکنواخت
4. الگوریتم جستجوی عمقی محدود شده
5. جستجوی عمق اول عمیق‌کننده تکراری
6. الگوریتم جستجوی دو طرفه

جستجوی لیست

الگوریتم‌های جستجوی لیست شاید از ابتدایی‌ترین انواع الگوریتم‌های جستجو باشند. هدف آن پیدا کردن یک عنصر از مجموعه‌ای از کلید هاست (ممکن است شامل اطلاعات دیگری مرتبط با آن کلید نیز باشد). ساده‌ترین این الگوریتم‌ها، الگوریتم جستجوی ترتیبی است که هر عنصر از لیست را با عنصر مورد نظر مقایسه می‌کند. زمان اجرای این الگوریتم از $O(n)$ است وقتی که $n$ تعداد عناصر در لیست باشد. اما می‌توان از روش دیگری استفاده کرد که نیازی به جستجوی تمام لیست نباشد. جستجوی دودویی اندکی از جستجوی خطی سریع‌تر است. زمان اجرای آن از $O(\log n)$ است. این روش برای لیستی با تعداد دادهٔ زیاد بسیار کار آمد تر از روش الگوریتم جستجوی ترتیبی است. اما در این روش لیست باید قبل از جستجو مرتب شده باشد. جستجو با میان یابی برای داده‌های مرتب شده با تعداد زیاد و توزیع یکنواخت، مناسب تر از جستجوی دودویی است. زمان اجرای آن به‌طور متوسط $O(\log(\log n))$ است ولی بدترین زمان اجرای آن $O(n)$ می‌باشد. الگوریتم گروور (Grover's algorithm) الگوریتم پله‌ای است که برای لیست‌های مرتب نشده استفاده می‌شود. جدول درهم‌سازی نیز برای جستجوی لیست به کار می‌رود. به‌طور متوسط زمان اجرای ثابتی دارد. اما نیاز به فضای اضافه داشته و بدترین زمان اجرای آن از $O(n)$ است.

جستجوی درختی

الگوریتم‌های جستجوی درختی، قلب شیوه‌های جستجو برای داده‌های ساخت یافته هستند. مبنای اصلی جستجوی درختی، گره‌هایی است که از یک ساختمان داده گرفته شده‌اند. هر عنصر که بخواهد اضافه شود با داده‌های موجود در گره‌های درخت مقایسه می‌شود و به ساختار درخت اضافه می‌شود. با تغییر ترتیب داده‌ها و قرار دادن آن‌ها در درخت، درخت با شیوه‌های مختلفی جستجو می‌شود. برای مثال سطح به سطح (جستجوی نخست-پهنا) یا پیمایش معکوس درخت (جستجوی نخست-ژرفا). از مثال‌های دیگر جستجوهای درختی می‌توان به جستجوی عمقی تکرار شونده، جستجوی عمقی محدود شده، جستجوی دوطرفه، جستجوی هزینه یکنواخت اشاره کرد.

جستجوی گراف

بسیاری از مسائل در نظریهٔ گراف می‌تواند با الگوریتم‌ها ی پیمایش درخت حل شوند، مثل الگوریتم دیکسترا، الگوریتم کروسکال، الگوریتم نزدیک‌ترین همسایه و الگوریتم پریم. می‌توان این الگوریتم‌ها را توسعه یافتهٔ الگوریتم‌های جستجوی درختی دانست.

جستجوی آگاهانه

در یک جستجوی آگاهانه، از نوع خاصی از مسائل به عنوان راهنما استفاده می‌شود. یک گونهٔ خوب یک جستجوی آگاهانه با کارایی قابل توجهی نسبت به جستجوی ناآگاهانه به وجود می‌آورد. الگوریتم‌های برجستهٔ کمی از جستجوی آگاهانهٔ یک لیست وجود دارد. یکی از این الگوریتم‌ها جدول درهم‌سازی (hash table) با یک تابع درهم‌ساز (hash function) است که بر مبنای نوع مسئله‌ای که در دست است کار می‌کند. بیشتر الگوریتم‌های جستجوی آگاهانه، بسطی از درخت‌ها هستند. همانند الگوریتم‌های ناآگاهانه، این الگوریتم‌ها برای گراف‌ها نیز می‌توانند به کار روند.

استراتژی‌های جستجوی آگاهانه یا مکاشفه‌ای از دانش مسئله استفاده می‌کنند و در انتخاب گره، گره‌ای را انتخاب می‌کنند که شانس رسیدن به هدف در آن بیشتر باشد یا به نظر آید که به هدف نزدیک‌تر است. برای اینکه تخمین بزنیم که گره فرزند چقدر به هدف نزدیک‌تر است از تابع ارزیابی استفاده می‌کنیم. این تابع هزینه رسیدن به گره هدف را تخمین می‌زند و به عبارت دیگر میزان مفید بودن گره فعلی را بازمی‌گرداند.

الگوریتم نخست-بهترین

در این روش در هر مرتبه گرهی که بهترین ارزیابی را داشته باشد ابتدا بسط داده می‌شود؛ به عبارت دیگر گرهی انتخاب می‌شود که تابع ارزیابی، بهترین مقدار را برای آن بازگرداند. برحسب اینکه تابع ارزیابی چگونه پیاده‌سازی شود، روش‌های گوناگونی از الگوریتم اول-بهترین خواهیم داشت. جستجوی اول-بهترین دو نوع کلی دارد که در یکی تابع ارزیابی هزینه رسیدن از گره فعلی به سمت هدف را حداقل می‌کند و در دومی هزینه کل مسیر از گره شروع تا هدف حداقل می‌شود.

جستجوی حریصانه

جستجوی حریصانه (Greedy Search) یکی از روش‌های جستجوی نخست-بهترین است. در این روش هدف به حداقل رساندن هزینه رسیدن به هدف با استفاده از تابع تخمین می‌باشد ($h(n)$). بدین صورت که گرهی که به هدف نزدیک‌تر است ابتدا بسط داده می‌شود. تابع ارزیابی که هزینه رسیدن از یک حالت (حالت فعلی) به حالت هدف را تخمین می‌زند تابع اکتشافی (Heuristic Search) نام دارد و با حرف $h$ بیان می‌گردد.

• $h(n)$: هزینه تخمین زده شده از ارزان‌ترین مسیر از گره $n$ به هدف.

در جستجوی حریصانه با انتخاب تابع تخمین $h(n)$ (که هزینه تخمینی رسیدن از گره فعلی به گره هدف بود) سعی می‌کردیم که سریع‌تر به سمت هدف حرکت نماییم و همچنین فضای حالت را کاهش دهیم اما این روش نه کامل بود و نه بهینه. از طرفی جستجو با هزینه یکسان با انتخاب تابع $g(n)$ (که هزینه واقعی مسیر از ریشه تا گره $n$ بود) در پی یافتن مسیری با حداقل هزینه بود که روشی کامل و بهینه به‌شمار می‌رفت اما می‌توانست بسیار زمان‌بر و در برخی موارد بی‌فایده باشد. برای دستیابی به مزایای هر دو جستجو، از ترکیب این دو روش تحت عنوان جستجوی $A^{*}$ استفاده می‌کنیم که تابع ارزیابی آن به صورت زیر است:

$f(n)=h(n)+g(n)$

• $h(n)$: هزینه تخمینی برای رسیدن از گره $n$ از ارزان‌ترین راه به هدف
• $g(n)$: هزینه رسیدن از گره ریشه به گره $n$

جستجوی پرتو (Beam Search)

دقیقاً همانند جستجوی حریصانه است با این تفاوت که در فهرست باز (open list) آن حداکثر $k$ عضو وجود دارد. یعنی فقط $k$ تا از بهترین گره‌ها کاندید برای توسعه دادن هستند و بقیه از فهرست خارج می‌شوند.

نکته: فضای حالت در این روش نسبت به روش حریصانه کاهش می‌یابد اما ممکن است که راه حل را از فهرست خارج کنیم؛ بنابراین این روش کامل و بهینه نیست.

جستجوی عمیق‌کننده تکراری (IDA)

می‌دانیم که جستجوی عمیق‌کننده تکراری، تکنیکی مفید برای کاهش درخواست حافظه است. حال می‌توانیم از این تکنیک استفاده نموده و هر بار یک جستجوی عمقی تا حد هزینه (f-limit) را جستجو کنیم. اگر به جواب نرسیدیم، حد هزینه را افزایش داده و از اول به بسط فضای حالت می‌پردازیم.

• نکته ۱: محدودیت هزینه در هر مرحله به گونه‌ای انتخاب می‌شود که در مراحل قبلی ثابت شده‌است که جوابی با هزینه کمتر از این مقدار وجود ندارد.
• نکته ۲: می‌توان هزینه مرحله جدید را برابر با کمترین هزینه گرهی که در مرحله قبلی بسط داده نشده قرار داد. از آنجا که این روش به صورت عمقی است، پس پیچیدگی فضایی آن در بدترین حالت $S(b\cdot d)$ است.
• نکته ۳: پیچیدگی زمانی بستگی به تابع اکتشافی دارد.
• نکته ۴: این روش نیز مشابه $A^{*}$ کامل و بهینه است.

جستجوی محدود به حافظه ساده‌شده (SMA)

در روش قبلی ($IDA^{*}$)، الگوریتم استفاده بسیار جزئی از حافظه داشت و بین تکرارها این جستجو فقط یک عدد خاص از محدوده جاری (f-cost) را نگه می‌داشت و چون نمی‌توانست تاریخچه‌اش را به خاطر آورد مجبور به تکرار می‌شد. الگوریتم $SMA^{*}$ قادر خواهد بود تا از تمام حافظه موجود برای اجرای جستجو استفاده نماید. هرچه حافظه بیشتر باشد کارایی جستجو بالاتر خواهد بود.

ویژگی‌ها:

1. می‌توان از تمام حافظه مورد دسترس خود استفاده کرد.
2. تا جایی که حافظه اجازه می‌دهد از تولید حالات تکراری جلوگیری می‌کند.
3. در صورتی کامل است که حافظه برای ذخیره کم‌عمق‌ترین مسیر راه حل وجود داشته باشد.
4. در صورتی بهینه است که حافظه کافی برای ذخیره کم‌عمق‌ترین مسیر راه حل وجود داشته باشد.

روند الگوریتم: زمانی که نیاز به تولید فرزند باشد ولی حافظه‌ای در اختیار نداشته باشیم، نیاز به نوشتن مجدد روی حافظه قبلی است. برای انجام این امر، الگوریتم یک گره را حذف می‌کند و فرزند جدید از حافظه آن استفاده خواهد کرد. گره‌هایی که بدین طریق حذف می‌شوند «گره‌های فراموش‌شده» نام دارند. همیشه گره‌هایی برای حذف شدن انتخاب می‌شوند که هزینه آن‌ها بالا است. برای جلوگیری از جستجوی مجدد زیردرخت‌هایی که از حافظه حذف شده‌اند، در گره پدر آن‌ها اطلاعاتی در مورد کیفیت بهترین مسیر در زیردرخت فراموش‌شده نگهداری می‌شود. بدین طریق فقط زمانی زیردرخت‌ها دوباره تولید می‌شوند که ثابت شود تمام مسیرهای دیگر بدتر از مسیر فراموش‌شده باشد.

الگوریتم تپه‌نوردی

تپه‌نوردی نمونه‌ای از الگوریتم‌های جستجوی آگاهانه می‌باشد چرا که از اطلاعاتی در مورد فضای جستجو به منظور پیشروی و با استفاده از یک راهکار منطقی بهره می‌برد. اگر سعی داشته باشید در حالی که فقط یک ارتفاع‌سنج در اختیار دارید و نقشه نیز ندارید از یک تپه بالا بروید، می‌توانید از روش تولید و تست تپه‌نوردی استفاده نمایید.

در هر مرحله بررسی نمایید تا ببینید در کدام جهت (شمال، جنوب، شرق و غرب)، ارتفاع قدری بیشتر است؛ به محض اینکه موقعیتی را پیدا کردید که ارتفاع در آن موقعیت بیشتر از موقعیت فعلی‌تان می‌باشد به آنجا بروید و الگوریتم را از اول تکرار کنید.

اگر همه جهت‌ها ارتفاع کمتری نسبت به موقعیت فعلی‌تان دارند، توقف نمایید و چنین تصور کنید که به محلی که خواسته‌اید رسیده‌اید. البته لزومی ندارد که این تصور همواره درست باشد! (به‌خاطر وجود بیشینه‌های محلی که در آن نقاط، ماکزیمم نسبی ظاهراً نسبت به تمام نقاط اطرافش وضعیت بهتری دارد اما نسبت به کل مسیر لزوماً بهترین نیست).

تپه‌نوردی شما را در یک درخت جستجو به سمت اولین گره بعدی که نسبت به گره فعلی بهتر باشد رهنمون می‌سازد. در میان گره‌های در دسترس مستقیم یک گره، گرهی بهتر خواهد بود که نسبت به گره فعلی مقدار مکاشفه‌ای کمتری داشته باشد.

جستجوی خصمانه

در یک بازی مثل شطرنج، یک درخت بازی شامل تمام حرکات ممکن توسط هر دو بازیکن و نتایج حاصل از ترکیب این حرکات وجود دارد، و ما می‌توانیم این درخت را جستجو کرده و مؤثرترین استراتژی برای بازی را بیابیم. این چنین مسائلی دارای مشخصهٔ منحصر به فردی هستند. برنامه‌های بازی‌های رایانه‌ای، و همچنین فرم‌های هوش مصنوعی مثل برنامه‌ریزی ماشین‌ها، اغلب از الگوریتم‌های جستجو مثل الگوریتم minimax (مینیمم مجموعه‌ای از ماکزیمم‌ها)، هرس کردن درخت جستجو و هرس کردن آلفا-بتا استفاده می‌کنند.

الگوریتم اف اسکن

F-SCAN یا اف-اسکن یک الگوریتم زمان‌بندی دیسک است که حرکت آرم (بازو) و هد دیسک را در سرویس‌دهی درخواست‌های خواندن و نوشتن تعیین می‌کند. طی روبش، تمام درخواست‌ها در صف اول داده‌های اولیه هستند و تمام درخواست‌های جدید در صف داده‌های ثانویه قرار داده می‌شوند. بنابراین سرویس‌دهی به درخواست‌های جدید به تأخیر می‌افتد تا زمانی که تمام درخواست‌های قدیمی تحت پردازش قرار گیرد. هنگامی که روبش پایان می‌یابد، بازو به ابتدای صف داده‌های اولیه برده می‌شود و دوباره سرتاسر آن شروع می‌شود.

تحلیل الگوریتم

الگوریتم F-SCAN مطابق N-Step-SCAN از چسبانکی بازو (Arm stickiness) جلوگیری می‌کند؛ در صورتی که در الگوریتم‌های دیگر مانند SSTF, SCAN و C-LOOK چنین امری اتفاق نمی‌افتد. چسبانکی بازو در الگوریتم‌های دیگر وقتی رخ می‌دهد که هجمه‌ای از درخواست‌ها برای مسیر مشترک موجب می‌شود تا بازوی دیسک در آن مسیر متوقف گردد؛ از این رو ترجیح داده می‌شود که هیچ جستجویی برای درخواست‌های آن مسیری که در آن است مورد تأیید واقع نشود. از آنجا که F-SCAN درخواست‌ها را به دو صف داده مجزا تقسیم می‌کند، روبرو شدن با درخواست‌های جدید به صف داده‌های در حال انتظار برده می‌شود، بازو روبش خود را تا مسیر بیرونی ادامه می‌دهد و از این رو چسبانکی پیش روی الگوریتم نیست. یک موازنه آشکار وجود دارد به‌طوری که درخواست‌ها در صف داده‌های در حال انتظار باید انتظار طولانی‌تری را برای به اجرا درآوردن بکشند، اما در مقابل، موازنه F-SCAN برای تمام درخواست‌ها رضایت‌بخش‌تر است.

دیگر متغیرها شامل موارد زیر می‌شود:

• الگوریتم آسانسور – اسکن (SCAN)
• LOOK (و C-LOOK)
• N-Step-SCAN

منابع

• الگوریتم‌های جستجو (انگلیسی)
• Donald Knuth. The Art of Computer Programming. Volume ۳: Sorting and Searching. شابک ‎۰−۲۰۱−۸۹۶۸۵−۰.
• مشارکت‌کنندگان ویکی‌پدیا. «FSCAN». در دانشنامهٔ ویکی‌پدیای انگلیسی.

پیوند به بیرون

• A Field Guide to Genetic Programming by Poli, Langdon, and McPhee. Available as a free PDF, or in printed form from Lulu.com.
• Self-Guided Lesson on Uninformed Search Go to the Wikiversity and teach yourself to program an uninformed search solution.