جستجوی عمقی در هوش مصنوعی – توضیح الگوریتم به زبان ساده

الگوریتم‌های جستجو در «ساختمان داده‌‌ها» (Data Structures) یکی از موضوعات مهم در مباحث طراحی الگوریتم و برنامه نویسی محسوب می‌شوند. این نوع الگوریتم‌‌ها برای پیدا کردن مقادیر خاصی از اطلاعات ذخیره شده در ساختار داده‌های مختلف نظیر درخت و گراف کاربرد دارند. الگوریتم «جستجوی عمقی» (Depth First Search | DFS) به عنوان یکی از الگوریتم‌های جستجوی رایج در هوش مصنوعی تلقی می‌شود که قصد داریم این مطلب از مجله فرادرس را به آن اختصاص دهیم.

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

الگوریتم پیمایش گراف چیست ؟

در ساختمان داده‌هایی نظیر درخت و گراف از الگوریتم‌های پیمایش برای پیدا کردن مقداری خاص استفاده می‌شوند. در این نوع ساختار داده‌ها، حلقه‌ای وجود ندارد و در روال پیمایش، هر راس از درخت یا گراف با ترتیبی خاص مورد بررسی قرار می‌گیرند که آیا دربرگیرنده مقدار «هدف» (Target) هستند و عملیات پیمایش خاتمه یابد یا باید روال جستجو ادامه پیدا کند؟

برای انجام روال پیمایش، می‌توان درخت یا گراف را به دو شیوه کلی پیمایش کرد که در ادامه به آن‌ها اشاره شده است:

• روش «جستجوی اول سطح» (Breadth-First Search) یا همان الگوریتم BFS
• روش «جستجوی اول عمق» (Depth-First Search) یا الگوریتم DFS

در مطلب پیشین از مجله فرادرس با عنوان «الگوریتم BFS» روال پیمایش گراف را به همراه مثال کاربردی توضیح دادیم. در مطلب فعلی قصد داریم روال جستجوی درخت یا گراف را با روش جستجوی DFS توضیح دهیم و برای درک این الگوریتم مثالی ساده از آن ارائه کنیم.

الگوریتم جستجوی عمقی چیست ؟

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

فیلم آموزش هوش مصنوعی – تکمیلی در فرادرس

کلیک کنید

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

کاربرد الگوریتم جستجوی عمقی در هوش مصنوعی

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

فیلم آموزش ساختمان داده ها با پایتون

کلیک کنید

• از الگوریتم جستجوی DFS در مرتب‌سازی توپولوژی استفاده می شود.
• الگوریتم جستجوی عمقی در هوش مصنوعی در پیدا کردن مسیر بین دو راس کاربرد دارد.
• از روش پیمایش جستجوی اول عمق برای تشخیص وجود حلقه در گراف استفاده می‌شود. زمانی در گراف حلقه وجود دارد که یک راس را دو بار در پیمایش ملاحظه کنیم.
• از الگوریتم جستجوی DFS برای تشخیص نوع «گراف دو بخشی» (Bipartite Graph) استفاده می‌شود.
• از الگوریتم جستجوی اول عمق در مسائل و معماهایی استفاده می‌شود که تنها دارای یک راه‌حل هستند.

مراحل الگوریتم جستجوی اول عمق چیست ؟

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

فیلم آموزش طراحی الگوریتم + حل مثال های عملی در فرادرس

کلیک کنید

1. پشته‌ و لیستی را به اندازه تعداد گره‌های گراف یا درخت ایجاد کنید.
2. گره‌ای ریشه را از درخت انتخاب و آن را به لیست اضافه کنید. اگر از ساختمان داده گراف استفاده می‌کنید، می‌توانید یکی از گره‌ها را به عنوان نقطه شروع جستجو به لیست اضافه کنید.
3. تمامی گره‌های مجاور (گره‌های فرزند) گره دیده شده را در بالای پشته قرار دهید.
4. به ترتیب گره‌های موجود در پشته را خارج کرده و به لیست اضافه کنید.
5. مرحله ۳ و ۴ را آنقدر تکرار کنید تا پشته خالی شود.

در ادامه، شبه کد الگوریتم جستجوی DFS را ملاحظه می‌کنید:

1DFS(G,v)   ( v is the vertex where the search starts )    
2        Stack S := {};   ( start with an empty stack )    
3        for each vertex u, set visited[u] := false;    
4        push S, v;    
5        while (S is not empty) do    
6           u := pop S;    
7           if (not visited[u]) then    
8              visited[u] := true;    
9              for each unvisited neighbour w of uu    
10                 push S, w;    
11           end if    
12        end while    
13     END DFS()    

در بخش بعدی، به ارائه یک مثال کاربردی از الگوریتم DFS می‌پردازیم.

مثال کاربردی از الگوریتم DFS

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

فیلم آموزش هوش مصنوعی – تکمیلی در فرادرس

کلیک کنید

گراف و پشته خالی زیر را در نظر بگیرید. از یک لیست نیز برای ذخیره کردن گره‌های ملاحظه شده استفاده می‌شود.

مرحله اول: گره ۰ از گراف بالا را به عنوان نقطه آغاز پیمایش جستجوی اول عمق در نظر می‌گیریم و این گره را به لیست اضافه می‌کنیم:

مرحله دوم: یکی از گره‌‌هایی را که در مجاورت با گره ۰ در گراف وجود دارد و در بالای پشته ذخیره شده است، درون لیست ذخیره می‌کنیم. در این مرحله گره ۱ را اضافه کردیم:

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

مرحله چهارم: حال، گره بالای پشته (یعنی گره ۴) را می‌خوانیم و آن را درون لیست قرار می‌دهیم. اگر این گره فرزندی داشته باشد، در بالای پشته قرار می‌گیرد.

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

پیچیدگی زمانی و پیچیدگی فضایی الگوریتم جستجوی عمقی چیست؟

پیچیدگی زمانی الگوریتم جستجوی عمقی برابر با O(V + E) است. مقدار V برابر با تعداد راس‌ها و مقدار E برابر با تعداد یال‌های گراف است. پیچیدگی فضایی الگوریتم جستجوی اول عمق نیز برابر با O(V) است زیرا در بدترین وضعیت، الگوریتم باید تمام راس‌های گراف را برای پیدا کردن مقدار هدف در حافظه ذخیره کند.

فیلم آموزش مروری بر پیچیدگی محاسبات Computational Complexity در فرادرس

کلیک کنید