الگوریتم‌های جستجو در «ساختمان داده‌‌ها» (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 را ملاحظه می‌کنید:

DFS(G,v)   ( v is the vertex where the search starts )    
        Stack S := {};   ( start with an empty stack )    
        for each vertex u, set visited[u] := false;    
        push S, v;    
        while (S is not empty) do    
           u := pop S;    
           if (not visited[u]) then    
              visited[u] := true;    
              for each unvisited neighbour w of uu    
                 push S, w;    
           end if    
        end while    
     END DFS()    

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

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

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

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

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

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

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

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

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

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

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

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

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

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

معایب الگوریتم DFS چیست ؟

الگوریتم DFS علاوه‌بر ویژگی‌های مثبت، دارای معایبی نیز است که در ادامه به برخی از مهم‌ترین معایب آن اشاره می‌کنیم:

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

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

در این بخش، نحوه پیاده‌سازی الگوریتم DFS را برای مثال گرافی ملاحظه می‌کنید که در بخش قبل ارائه کردیم. قطعه کدهای ارائه شده به ۶ زبان برنامه نویسی C ،C++‎ ،C#‎ ،جاوا، جاوا اسکریپت و پایتون هستند که خروجی تمامی این قطعه کدها، یکسان است.

پیاده سازی الگوریتم DFS با زبان برنامه نویسی ++C

در قطعه کد زیر، نحوه پیاده‌سازی الگوریتم جستجوی اول عمق را با زبان برنامه نویسی ++C ملاحظه می‌کنید.

// C++ program to print DFS traversal from
// a given vertex in a  given graph
#include <bits/stdc++.h>
using namespace std;
 
// Graph class represents a directed graph
// using adjacency list representation
class Graph {
public:
    map<int, bool> visited;
    map<int, list<int> > adj;
 
    // Function to add an edge to graph
    void addEdge(int v, int w);
 
    // DFS traversal of the vertices
    // reachable from v
    void DFS(int v);
};
 
void Graph::addEdge(int v, int w)
{
    // Add w to v’s list.
    adj[v].push_back(w);
}
 
void Graph::DFS(int v)
{
    // Mark the current node as visited and
    // print it
    visited[v] = true;
    cout << v << " ";
 
    // Recur for all the vertices adjacent
    // to this vertex
    list<int>::iterator i;
    for (i = adj[v].begin(); i != adj[v].end(); ++i)
        if (!visited[*i])
            DFS(*i);
}
 
// Driver code
int main()
{
    // Create a graph given in the above diagram
    Graph g;
    g.addEdge(0, 1);
    g.addEdge(0, 2);
    g.addEdge(1, 2);
    g.addEdge(2, 0);
    g.addEdge(2, 3);
    g.addEdge(3, 3);
 
    cout << "Following is Depth First Traversal"
            " (starting from vertex 2) n";
 
    // Function call
    g.DFS(2);
 
    return 0;
}

خروجی قطعه کد بالا در ادامه دیده می‌شود:

Following is Depth First Traversal (starting from vertex 2) 
2 0 1 3 

پیاده سازی الگوریتم جستجوی عمقی با زبان برنامه نویسی جاوا

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

// Java program to print DFS traversal
// from a given graph
import java.io.*;
import java.util.*;
 
// This class represents a
// directed graph using adjacency
// list representation
class Graph {
    private int V;
 
    // Array  of lists for
    // Adjacency List Representation
    private LinkedList<Integer> adj[];
 
    // Constructor
    @SuppressWarnings("unchecked") Graph(int v)
    {
        V = v;
        adj = new LinkedList[v];
        for (int i = 0; i < v; ++i)
            adj[i] = new LinkedList();
    }
 
    // Function to add an edge into the graph
    void addEdge(int v, int w)
    {
        // Add w to v's list.
        adj[v].add(w);
    }
 
    // A function used by DFS
    void DFSUtil(int v, boolean visited[])
    {
        // Mark the current node as visited and print it
        visited[v] = true;
        System.out.print(v + " ");
 
        // Recur for all the vertices adjacent to this
        // vertex
        Iterator<Integer> i = adj[v].listIterator();
        while (i.hasNext()) {
            int n = i.next();
            if (!visited[n])
                DFSUtil(n, visited);
        }
    }
 
    // The function to do DFS traversal.
    // It uses recursive DFSUtil()
    void DFS(int v)
    {
        // Mark all the vertices as
        // not visited(set as
        // false by default in java)
        boolean visited[] = new boolean[V];
 
        // Call the recursive helper
        // function to print DFS
        // traversal
        DFSUtil(v, visited);
    }
 
    // Driver Code
    public static void main(String args[])
    {
        Graph g = new Graph(4);
 
        g.addEdge(0, 1);
        g.addEdge(0, 2);
        g.addEdge(1, 2);
        g.addEdge(2, 0);
        g.addEdge(2, 3);
        g.addEdge(3, 3);
 
        System.out.println(
            "Following is Depth First Traversal "
            + "(starting from vertex 2)");
 
        // Function call
        g.DFS(2);
    }
}

پیاده سازی الگوریتم جستجوی اول عمق با زبان برنامه نویسی پایتون

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

# Python3 program to print DFS traversal
# from a given  graph
from collections import defaultdict
 
 
# This class represents a directed graph using
# adjacency list representation
class Graph:
 
    # Constructor
    def __init__(self):
 
        # Default dictionary to store graph
        self.graph = defaultdict(list)
 
     
    # Function to add an edge to graph
    def addEdge(self, u, v):
        self.graph[u].append(v)
 
     
    # A function used by DFS
    def DFSUtil(self, v, visited):
 
        # Mark the current node as visited
        # and print it
        visited.add(v)
        print(v, end=' ')
 
        # Recur for all the vertices
        # adjacent to this vertex
        for neighbour in self.graph[v]:
            if neighbour not in visited:
                self.DFSUtil(neighbour, visited)
 
     
    # The function to do DFS traversal. It uses
    # recursive DFSUtil()
    def DFS(self, v):
 
        # Create a set to store visited vertices
        visited = set()
 
        # Call the recursive helper function
        # to print DFS traversal
        self.DFSUtil(v, visited)
 
 
# Driver's code
if __name__ == "__main__":
    g = Graph()
    g.addEdge(0, 1)
    g.addEdge(0, 2)
    g.addEdge(1, 2)
    g.addEdge(2, 0)
    g.addEdge(2, 3)
    g.addEdge(3, 3)
 
    print("Following is Depth First Traversal (starting from vertex 2)")
     
    # Function call
    g.DFS(2)

پیاده سازی الگوریتم جستجوی هوش مصنوعی اول عمق با زبان برنامه نویسی C#‎

در قطعه کد زیر، نحوه پیاده‌سازی الگوریتم پیمایش عمقی در هوش مصنوعی را با زبان برنامه نویسی C#‎ ملاحظه می‌کنید.

// C# program to print DFS traversal
// from a given graph
using System;
using System.Collections.Generic;
 
// This class represents a directed graph
// using adjacency list representation
class Graph {
    private int V;
 
    // Array of lists for
    // Adjacency List Representation
    private List<int>[] adj;
 
    // Constructor
    Graph(int v)
    {
        V = v;
        adj = new List<int>[ v ];
        for (int i = 0; i < v; ++i)
            adj[i] = new List<int>();
    }
 
    // Function to Add an edge into the graph
    void AddEdge(int v, int w)
    {
        // Add w to v's list.
        adj[v].Add(w);
    }
 
    // A function used by DFS
    void DFSUtil(int v, bool[] visited)
    {
        // Mark the current node as visited
        // and print it
        visited[v] = true;
        Console.Write(v + " ");
 
        // Recur for all the vertices
        // adjacent to this vertex
        List<int> vList = adj[v];
        foreach(var n in vList)
        {
            if (!visited[n])
                DFSUtil(n, visited);
        }
    }
 
    // The function to do DFS traversal.
    // It uses recursive DFSUtil()
    void DFS(int v)
    {
        // Mark all the vertices as not visited
        // (set as false by default in c#)
        bool[] visited = new bool[V];
 
        // Call the recursive helper function
        // to print DFS traversal
        DFSUtil(v, visited);
    }
 
    // Driver Code
    public static void Main(String[] args)
    {
        Graph g = new Graph(4);
 
        g.AddEdge(0, 1);
        g.AddEdge(0, 2);
        g.AddEdge(1, 2);
        g.AddEdge(2, 0);
        g.AddEdge(2, 3);
        g.AddEdge(3, 3);
 
        Console.WriteLine(
            "Following is Depth First Traversal "
            + "(starting from vertex 2)");
 
        // Function call
        g.DFS(2);
        Console.ReadKey();
    }
}

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

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

// Javascript program to print DFS
// traversal from a given 
// graph
 
// This class represents a
// directed graph using adjacency
// list representation
class Graph
{
     
    // Constructor
    constructor(v)
    {
        this.V = v;
        this.adj = new Array(v);
        for(let i = 0; i < v; i++)
            this.adj[i] = [];
    }
     
    // Function to add an edge into the graph
    addEdge(v, w)
    {
         
        // Add w to v's list.
        this.adj[v].push(w); 
    }
     
    // A function used by DFS
    DFSUtil(v, visited)
    {
         
        // Mark the current node as visited and print it
        visited[v] = true;
        console.log(v + " ");
  
        // Recur for all the vertices adjacent to this
        // vertex
        for(let i of this.adj[v].values())
        {
            let n = i
            if (!visited[n])
                this.DFSUtil(n, visited);
        }
    }
     
    // The function to do DFS traversal.
    // It uses recursive
    // DFSUtil()
    DFS(v)
    {
         
        // Mark all the vertices as
        // not visited(set as
        // false by default in java)
        let visited = new Array(this.V);
        for(let i = 0; i < this.V; i++)
            visited[i] = false;
  
        // Call the recursive helper
        // function to print DFS
        // traversal
        this.DFSUtil(v, visited);
    }
}
 
// Driver Code
g = new Graph(4);
  
g.addEdge(0, 1);
g.addEdge(0, 2);
g.addEdge(1, 2);
g.addEdge(2, 0);
g.addEdge(2, 3);
g.addEdge(3, 3);
 
console.log("Following is Depth First Traversal " + 
               "(starting from vertex 2)");
 
g.DFS(2);

جمع‌بندی

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