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

مقدمه مقاله الگوریتم جستجوی عرضی

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

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

روش جستجوی اول سطح

جستجوی عرضی همواره جوابی با کم‌ترین تعداد کنش‌ها را پیدا می‌کند، زیرا وقتی گره‌ها را در عمق d ایجاد می‌کند، تمام گره‌ها در عمق d-1 را قبلا تولید کرده است. پیچیدگی زمانی و فضا در این الگوریتم به‌طور نمایی است. به‌طور مثال مسئله‌ای را با ضریب انشعاب b=10 سرعت پردازش یک میلیون گره در ثانیه، حافظه مورد نیاز یک کیلو بایت برای هر گره را با جستجوی عمق در نظر بگیرید.

جستجوی عمق d=10 کم‌تر از ۳ ساعت طول می‌کشد ولی به ۱۰ ترابایت حافظه نیاز دارد، نیازمندی حافظه نسبت به زمان اجزا در الگوریتم‌های عرضی، مشکل جدی‌تر است. اما زمان هنوز فاکتور مهمی است. در عمق d=14 حتی با حافظه نامتناهی، جستجو ۳.۵ سال طول می‌کشد. به‌طور کلی مسئله جستجو با پیچیدگی نمایی، نمی‌تواند با الگوریتم ناآگاهانه حل شود مگر این که نمونه مسئله بسیار کوچک باشد.

جستجوی عرضی در درخت

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

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

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

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

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

شبه کد الگوریتم BFS

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

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

1. شروع از رأس مبدأ: الگوریتم از یک رأس انتخاب شده به‌عنوان نقطه شروع آغاز می‌کند.

2. صف: رأس شروع به یک صف اضافه می‌شود.

3. پردازش رأس‌ها: تا زمانی که صف خالی نشود، مراحل زیر ادامه می‌یابد:

   • رأس جلوی صف برداشته می‌شود.
   • اگر رأس برداشته شده قبلاً بازدید نشده باشد، آن را به عنوان بازدید شده علامت‌گذاری می‌کنیم.
   • تمام رأس‌های همسایه رأس برداشته شده و که هنوز بازدید نشده‌اند به صف اضافه می‌شوند.

4. تکرار: این فرآیند تا زمان خالی شدن صف ادامه می‌یابد.

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

BFS(start):
    enqueue(start)          // Enqueue the start node
    mark start as visited   // Mark the start node as visited

    while queue is not empty:
        current = dequeue()   // Dequeue a node from the front of the queue
        print current.value   // Process the current node

        for each neighbor in current.neighbors:
            if neighbor is not visited:
                enqueue(neighbor)         // Enqueue the neighbor if not visited
                mark neighbor as visited  // Mark the neighbor as visited

کد الگوریتم جستجوی سطحی در ++C

کد الگوریتم جستجوی عرضی (Breadth First Search) در ++C به‌صورت زیر است:

#include <iostream>
#include <queue>
#include <vector>

using namespace std;

// ساختار یک گره در گراف
struct Node {
    int data;
    vector<Node*> neighbors;
    bool visited;

    Node(int value) : data(value), visited(false) {}
};

// تابع افزودن یک یال بین دو گره
void addEdge(Node* node1, Node* node2) {
    node1->neighbors.push_back(node2);
    node2->neighbors.push_back(node1);
}

// الگوریتم جستجوی عرضی
void BFS(Node* start) {
    // استفاده از یک صف برای ذخیره گره‌های در حال پردازش
    queue<Node*> q;

    // اضافه کردن گره شروع به صف
    q.push(start);
    start->visited = true;

    while (!q.empty()) {
        // گره جاری را از صف حذف و چاپ کن
        Node* current = q.front();
        cout << current->data << " ";
        q.pop();

        // پیمایش همسایگان گره جاری
 for (vector<Node*>::iterator it = current->neighbors.begin(); it != current->neighbors.end(); ++it) {
Node* neighbor = *it;            // اگر هنوز بازدید نشده باشد، به صف اضافه کن و علامت بزن
            if (!neighbor->visited) {
                q.push(neighbor);
                neighbor->visited = true;
            }
        }
    }
}

int main() {
    // ساخت گراف
    Node* node1 = new Node(1);
    Node* node2 = new Node(2);
    Node* node3 = new Node(3);
    Node* node4 = new Node(4);
    Node* node5 = new Node(5);

    addEdge(node1, node2);
    addEdge(node1, node3);
    addEdge(node2, node4);
    addEdge(node2, node5);

    // اجرای الگوریتم جستجوی عرضی از گره ۱
    cout << "BFS starting from node 1: ";
    BFS(node1);

    // گرداننده حافظه
    delete node1;
    delete node2;
    delete node3;
    delete node4;
    delete node5;

    return 0;
}

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

کد الگوریتم جستجوی سطحی در پایتون

کد الگوریتم جستجوی عرضی (Breadth First Search) در پایتون به صورت زیر است:

from queue import Queue

class Node:
    def __init__(self, value):
        self.data = value
        self.neighbors = []
        self.visited = False

def add_edge(node1, node2):
    node1.neighbors.append(node2)
    node2.neighbors.append(node1)

def bfs(start):
    # استفاده از یک صف برای ذخیره گره‌های در حال پردازش
    q = Queue()

    # اضافه کردن گره شروع به صف
    q.put(start)
    start.visited = True

    while not q.empty():
        # گره جاری را از صف حذف و چاپ کردن
        current = q.get()
        print(current.data, end=" ")

        # پیمایش همسایگان گره جاری
        for neighbor in current.neighbors:
            # اگر هنوز بازدید نشده باشد، به صف اضافه کردن و علامت بزن
            if not neighbor.visited:
                q.put(neighbor)
                neighbor.visited = True

# ساخت گراف
node1 = Node(1)
node2 = Node(2)
node3 = Node(3)
node4 = Node(4)
node5 = Node(5)

add_edge(node1, node2)
add_edge(node1, node3)
add_edge(node2, node4)
add_edge(node2, node5)

# اجرای الگوریتم جستجوی عرضی از گره ۱
print("BFS starting from node 1:", end=" ")
bfs(node1)

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

• پاورپوینت کتابخانه های پایتون در علوم داده — کلیک کنید.
• مدل های یادگیری ماشین در پایتون — پاورپوینت کلاسی — کلیک کنید.
• پاورپوینت مقایسه پایتون و سی شارپ

سخن آخر در مورد الگوریتم جستجوی سطحی

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

در پایان ذکر دوباره این نکته ضروری است که به طور کلی مسئله جستجو با پیچیدگی نمایی، نمی‌تواند با الگوریتم ناآگاهانه حل شود مگر این که نمونه مسئله بسیار کوچک باشد.