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

۱۶۴۸ بازدید
آخرین به‌روزرسانی: ۲۴ مهر ۱۴۰۲
زمان مطالعه: ۱۰ دقیقه
جستجوی عمقی در هوش مصنوعی – توضیح الگوریتم به زبان ساده

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1// C++ program to print DFS traversal from
2// a given vertex in a  given graph
3#include <bits/stdc++.h>
4using namespace std;
5 
6// Graph class represents a directed graph
7// using adjacency list representation
8class Graph {
9public:
10    map<int, bool> visited;
11    map<int, list<int> > adj;
12 
13    // Function to add an edge to graph
14    void addEdge(int v, int w);
15 
16    // DFS traversal of the vertices
17    // reachable from v
18    void DFS(int v);
19};
20 
21void Graph::addEdge(int v, int w)
22{
23    // Add w to v’s list.
24    adj[v].push_back(w);
25}
26 
27void Graph::DFS(int v)
28{
29    // Mark the current node as visited and
30    // print it
31    visited[v] = true;
32    cout << v << " ";
33 
34    // Recur for all the vertices adjacent
35    // to this vertex
36    list<int>::iterator i;
37    for (i = adj[v].begin(); i != adj[v].end(); ++i)
38        if (!visited[*i])
39            DFS(*i);
40}
41 
42// Driver code
43int main()
44{
45    // Create a graph given in the above diagram
46    Graph g;
47    g.addEdge(0, 1);
48    g.addEdge(0, 2);
49    g.addEdge(1, 2);
50    g.addEdge(2, 0);
51    g.addEdge(2, 3);
52    g.addEdge(3, 3);
53 
54    cout << "Following is Depth First Traversal"
55            " (starting from vertex 2) \n";
56 
57    // Function call
58    g.DFS(2);
59 
60    return 0;
61}

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

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

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

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

1// Java program to print DFS traversal
2// from a given graph
3import java.io.*;
4import java.util.*;
5 
6// This class represents a
7// directed graph using adjacency
8// list representation
9class Graph {
10    private int V;
11 
12    // Array  of lists for
13    // Adjacency List Representation
14    private LinkedList<Integer> adj[];
15 
16    // Constructor
17    @SuppressWarnings("unchecked") Graph(int v)
18    {
19        V = v;
20        adj = new LinkedList[v];
21        for (int i = 0; i < v; ++i)
22            adj[i] = new LinkedList();
23    }
24 
25    // Function to add an edge into the graph
26    void addEdge(int v, int w)
27    {
28        // Add w to v's list.
29        adj[v].add(w);
30    }
31 
32    // A function used by DFS
33    void DFSUtil(int v, boolean visited[])
34    {
35        // Mark the current node as visited and print it
36        visited[v] = true;
37        System.out.print(v + " ");
38 
39        // Recur for all the vertices adjacent to this
40        // vertex
41        Iterator<Integer> i = adj[v].listIterator();
42        while (i.hasNext()) {
43            int n = i.next();
44            if (!visited[n])
45                DFSUtil(n, visited);
46        }
47    }
48 
49    // The function to do DFS traversal.
50    // It uses recursive DFSUtil()
51    void DFS(int v)
52    {
53        // Mark all the vertices as
54        // not visited(set as
55        // false by default in java)
56        boolean visited[] = new boolean[V];
57 
58        // Call the recursive helper
59        // function to print DFS
60        // traversal
61        DFSUtil(v, visited);
62    }
63 
64    // Driver Code
65    public static void main(String args[])
66    {
67        Graph g = new Graph(4);
68 
69        g.addEdge(0, 1);
70        g.addEdge(0, 2);
71        g.addEdge(1, 2);
72        g.addEdge(2, 0);
73        g.addEdge(2, 3);
74        g.addEdge(3, 3);
75 
76        System.out.println(
77            "Following is Depth First Traversal "
78            + "(starting from vertex 2)");
79 
80        // Function call
81        g.DFS(2);
82    }
83}

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

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

1# Python3 program to print DFS traversal
2# from a given  graph
3from collections import defaultdict
4 
5 
6# This class represents a directed graph using
7# adjacency list representation
8class Graph:
9 
10    # Constructor
11    def __init__(self):
12 
13        # Default dictionary to store graph
14        self.graph = defaultdict(list)
15 
16     
17    # Function to add an edge to graph
18    def addEdge(self, u, v):
19        self.graph[u].append(v)
20 
21     
22    # A function used by DFS
23    def DFSUtil(self, v, visited):
24 
25        # Mark the current node as visited
26        # and print it
27        visited.add(v)
28        print(v, end=' ')
29 
30        # Recur for all the vertices
31        # adjacent to this vertex
32        for neighbour in self.graph[v]:
33            if neighbour not in visited:
34                self.DFSUtil(neighbour, visited)
35 
36     
37    # The function to do DFS traversal. It uses
38    # recursive DFSUtil()
39    def DFS(self, v):
40 
41        # Create a set to store visited vertices
42        visited = set()
43 
44        # Call the recursive helper function
45        # to print DFS traversal
46        self.DFSUtil(v, visited)
47 
48 
49# Driver's code
50if __name__ == "__main__":
51    g = Graph()
52    g.addEdge(0, 1)
53    g.addEdge(0, 2)
54    g.addEdge(1, 2)
55    g.addEdge(2, 0)
56    g.addEdge(2, 3)
57    g.addEdge(3, 3)
58 
59    print("Following is Depth First Traversal (starting from vertex 2)")
60     
61    # Function call
62    g.DFS(2)

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

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

1// C# program to print DFS traversal
2// from a given graph
3using System;
4using System.Collections.Generic;
5 
6// This class represents a directed graph
7// using adjacency list representation
8class Graph {
9    private int V;
10 
11    // Array of lists for
12    // Adjacency List Representation
13    private List<int>[] adj;
14 
15    // Constructor
16    Graph(int v)
17    {
18        V = v;
19        adj = new List<int>[ v ];
20        for (int i = 0; i < v; ++i)
21            adj[i] = new List<int>();
22    }
23 
24    // Function to Add an edge into the graph
25    void AddEdge(int v, int w)
26    {
27        // Add w to v's list.
28        adj[v].Add(w);
29    }
30 
31    // A function used by DFS
32    void DFSUtil(int v, bool[] visited)
33    {
34        // Mark the current node as visited
35        // and print it
36        visited[v] = true;
37        Console.Write(v + " ");
38 
39        // Recur for all the vertices
40        // adjacent to this vertex
41        List<int> vList = adj[v];
42        foreach(var n in vList)
43        {
44            if (!visited[n])
45                DFSUtil(n, visited);
46        }
47    }
48 
49    // The function to do DFS traversal.
50    // It uses recursive DFSUtil()
51    void DFS(int v)
52    {
53        // Mark all the vertices as not visited
54        // (set as false by default in c#)
55        bool[] visited = new bool[V];
56 
57        // Call the recursive helper function
58        // to print DFS traversal
59        DFSUtil(v, visited);
60    }
61 
62    // Driver Code
63    public static void Main(String[] args)
64    {
65        Graph g = new Graph(4);
66 
67        g.AddEdge(0, 1);
68        g.AddEdge(0, 2);
69        g.AddEdge(1, 2);
70        g.AddEdge(2, 0);
71        g.AddEdge(2, 3);
72        g.AddEdge(3, 3);
73 
74        Console.WriteLine(
75            "Following is Depth First Traversal "
76            + "(starting from vertex 2)");
77 
78        // Function call
79        g.DFS(2);
80        Console.ReadKey();
81    }
82}

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

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

1// Javascript program to print DFS
2// traversal from a given 
3// graph
4 
5// This class represents a
6// directed graph using adjacency
7// list representation
8class Graph
9{
10     
11    // Constructor
12    constructor(v)
13    {
14        this.V = v;
15        this.adj = new Array(v);
16        for(let i = 0; i < v; i++)
17            this.adj[i] = [];
18    }
19     
20    // Function to add an edge into the graph
21    addEdge(v, w)
22    {
23         
24        // Add w to v's list.
25        this.adj[v].push(w); 
26    }
27     
28    // A function used by DFS
29    DFSUtil(v, visited)
30    {
31         
32        // Mark the current node as visited and print it
33        visited[v] = true;
34        console.log(v + " ");
35  
36        // Recur for all the vertices adjacent to this
37        // vertex
38        for(let i of this.adj[v].values())
39        {
40            let n = i
41            if (!visited[n])
42                this.DFSUtil(n, visited);
43        }
44    }
45     
46    // The function to do DFS traversal.
47    // It uses recursive
48    // DFSUtil()
49    DFS(v)
50    {
51         
52        // Mark all the vertices as
53        // not visited(set as
54        // false by default in java)
55        let visited = new Array(this.V);
56        for(let i = 0; i < this.V; i++)
57            visited[i] = false;
58  
59        // Call the recursive helper
60        // function to print DFS
61        // traversal
62        this.DFSUtil(v, visited);
63    }
64}
65 
66// Driver Code
67g = new Graph(4);
68  
69g.addEdge(0, 1);
70g.addEdge(0, 2);
71g.addEdge(1, 2);
72g.addEdge(2, 0);
73g.addEdge(2, 3);
74g.addEdge(3, 3);
75 
76console.log("Following is Depth First Traversal " + 
77               "(starting from vertex 2)");
78 
79g.DFS(2);

جمع‌بندی

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

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

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *