الگوریتم جستجوی عمقی Depth First Search — راهنمای جامع همراه با مثال

مقدمه مقاله الگوریتم جستجوی عمقی Depth First Search

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

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

جستجوی عمقی در درخت

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

مراحل طی شده توسط الگوریتم جستجوی عمقی به شکل زیر خواهد بود. در مرحله اول ریشه درخت را انتخاب خواهیم کرد.

بررسی کارایی الگوریتم جستجوی عمقی

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

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

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

مشکلات و راه حل‌ها در الگوریتم جستجوی عمقی

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

جستجوی با عمق محدود

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

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

مرحله اول

مرحله دوم

مرحله سوم

مرحله چهارم

مرحله پنجم

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

• کامل بودن: خیر ( اگر سطحی‌ترین هدف در خارج از عمق محدوده قرار داشته باشد، این راهبرد کامل نخواهد بود)
• بهینگی: خیر ( با توجه به کامل نبودن قطعا بهینه نیز نخواهد بود)
• پیچیدگی زمانی: بصورت نمایی
• پیچیدگی فضا: بصورت خطی

جستجوی عمیق کننده تکراری

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

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

در مثال بالایی روش جستجوی عمیق کننده تکراری را اجرا می‌کنیم. محدوده عمق جستجو در هر مرحله با خط چین قرمز نمایش داده می‌شود.

مرحله ۱

مرحله ۲

مرحله ۳

مرحله ۴

مرحله ۵

مرحله ۶

مرحله ۷

مرحله ۸

مرحله ۹

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

• کامل بودن: بله ( در صورتی که فاکتور انشعاب محدود باشد)
• بهینگی: بله ( وقتی که هزینه مسیر، تابعی غیر نزولی از عمق گره باشد )
• پیچیدگی زمانی: بصورت نمایی
• پیچیدگی فضا: بصورت خطی

با بررسی این دو روش اصلاحی الگوریتم جستجوی عمقی مشاهده کردید که هرچند نسبت به نسخه اولیه خود عملکرد بهتری دارند ولی باز مشکلات خاص خود را هم دارند.