الگوریتم جستجوی عرضی Breadth First Search — راهنمای جامع همراه با مثال
در این بخش از آموزش های درس هوش مصنوعی به الگوریتم جستجوی عرضی Breadth first search یا همان الگوریتم BFS می رسیم. در این آموزش الگوریتم جستجوی عرضی را همراه با مثال و چگونگی پیمایش آموزش خواهیم داد. این الگوریتم که به اختصار BFS نامیده می شود، جزو الگوریتم های معروف هوش مصنوعی برای جستجو است. در ادامه با ما همراه باشید تا این الگوریتم را با یکدیگر بررسی کنیم.
مقدمه
در درس هوش مصنوعی دو نوع جستجو از اهمیت بیشتری برخوردار هستند که هر کدام نیز به چند الگوریتم تقسیم بندی می شوند. این دو، جستجوی آگاهانه و جستجوی ناآگاهانه نام دارند. الگوریتمی که مدنظر ما است، الگوریتم جستجوی سطح اول یا همان جستجوی عرضی می باشد که در دسته الگوریتم های جستجو ناآگاهانه قرار دارد. وقتی تمام عمل ها هزینه یکسانی دارند، یک استراتژی مناسب، جستجوی عرضی است.
در این جستجو ابتدا گره ریشه بسط داده می شود و سپس تمام گره های بعدی ریشه و سپس گره های بعدی این گره ها و غیره بسط داده می شوند. جستجوی عرضی یک استراتژی جستجوی منظم است و در نتیجه حتی در فضای حالت نا متناهی نیز کامل است. می توان این ساختار را در یک صف FIFO پیاده سازی کرد. گره های جدید که همیشه عمیق تر از والدهای خود هستند، در انتهای صف قرار می گیرد و گره های قدیمی که عمق آن ها از گره های جدید کمتر است، زودتر بسط داده می شوند.
روش جستجوی اول سطح
جستجوی عرضی همواره جوابی با کمترین تعداد کنش ها را پیدا می کند، زیرا وقتی گره ها را در عمق d ایجاد می کند، تمام گره ها در عمق d-1 را قبلا تولید کرده است. پیچیدگی زمانی و فضا در این الگوریتم بطور نمایی است. بطور مثال مسئله ای را با ضریب انشعاب b=10 سرعت پردازش یک میلیون گره در ثانیه، حافظه مورد نیاز یک کیلو بایت برای هر گره را با جستجوی عمق در نظر بگیرید.
جستجوی عمق d=10 کمتر از 3 ساعت طول می کشد ولی به 10 ترابایت حافظه نیاز دارد، نیازمندی حافظه نسبت به زمان اجزا در الگوریتم های عرضی، مشکل جدی تر است. اما زمان هنوز فاکتور مهمی است. در عمق d=14 حتی با حافظه نامتناهی، جستجو 3.5 سال طول می کشد. به طور کلی مسئله جستجو با پیچیدگی نمایی، نمی تواند با الگوریتم ناآگاهانه حل شود مگر این که نمونه مسئله بسیار کوچک باشد.
جستجوی عرضی در درخت
برای درک بهتر الگوریتم، از این روش جستجو در درخت جستجویی به شکل زیر استفاده می کنیم. فرض کنید فضای جستجوی یک مسئله بصورت درخت زیر است.
الگوریتم جستجوی عرضی در طی مراحل زیر انجام می گیرد. در مرحله اول، اولین گره که ملاقات و صف قرار می گیرد گره A می باشد و در ادامه خواهیم داشت.
بررسی کارایی الگوریتم جستجوی عرضی
در ادامه آموزش الگوریتم جستجوی عرضی به بررسی کارایی این الگوریتم می رسیم. کارایی این الگوریتم را با چهار معیار کامل بودن، بهینه بودن، پیچیدگی زمان و پیچیدگی فضا مورد ارزیابی و بررسی قرار می دهیم.
- کامل بودن: بله، این الگوریتم کامل است.
- بهینه بودن: بله (مشروط) در صورتی بهینه است که هزینه مسیر، تابعی غیر نزولی از عمق گره باشد.(مثل وقتی که فعالیتها هزینه یکسانی دارند)
- پیچیدگی زمان: پیچیدگی زمان در این روش بصورت نمایی است.
- پیچیدگی فضا: پیچیدگی فضا در این روش بصورت خطی است.
شبه کد الگوریتم BFS
این الگوریتم با استفاده از یک صف برای نگه داری رأسهایی که باید بازدید شوند، به صورت عرضی در گراف یا درخت پیش میرود.
در اینجا نحوه عملکرد الگوریتم جستجوی عرضی توضیح داده میشود:
-
شروع از رأس مبدأ: الگوریتم از یک رأس انتخاب شده به عنوان نقطه شروع آغاز میکند.
-
صف: رأس شروع به یک صف اضافه میشود.
-
پردازش رأسها: تا زمانی که صف خالی نشود، مراحل زیر ادامه مییابد:
- رأس جلوی صف برداشته میشود.
- اگر رأس برداشته شده قبلاً بازدید نشده باشد، آن را به عنوان بازدید شده علامتگذاری میکنیم.
- تمام رأسهای همسایه رأس برداشته شده و که هنوز بازدید نشدهاند به صف اضافه میشوند.
-
تکرار: این فرایند تا زمان خالی شدن صف ادامه مییابد.
بصورت کلی شبه کد الگوریتم جستجوی عرضی به صورت زیر خواهد بود:
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
ویژگی الگوریتم BFS
الگوریتم جستجوی عرضی معمولاً برای پیدا کردن کوتاهترین مسیر در گرافهای بدون وزن، کشف ساختار گرافها، و در مسائل مختلف دیگری که نیاز به جستجوی سیستماتیک است، استفاده میشود. این الگوریتم به ویژه مفید است زمانی که میخواهیم تمامی رأسها یا یالهای یک گراف را بدون تکرار بازدید کنیم. یکی از ویژگیهای کلیدی الگوریتم BFS این است که آن مسیرهای کوتاهترین (به لحاظ تعداد یالها) از رأس شروع به تمام رأسهای دیگر در گراف را پیدا میکند، به شرطی که گراف بدون وزن باشد.
مزایای الگوریتم جستجوی عرضی
-
یافتن کوتاهترین مسیر: در گرافهای بدون وزن، BFS کوتاهترین مسیر (به لحاظ تعداد یالها) را بین دو رأس پیدا میکند.
-
استفاده در شبکههای اجتماعی: برای یافتن افراد با حداقل تعداد ارتباط (مانند دوستان دوستان) در شبکههای اجتماعی کاربرد دارد.
-
کاربرد در الگوریتمهای پیچیدهتر: به عنوان یک بخش از الگوریتمهای پیچیدهتر مانند الگوریتمهای تطبیق گراف استفاده میشود.
-
کشف سطح: BFS میتواند برای تعیین “سطح” یا “فاصله” هر رأس از رأس شروع استفاده شود.
محدودیتهای الگوریتم جستجوی عرضی
-
مصرف حافظه: به دلیل استفاده از صف، ممکن است در گرافهای بزرگ حافظه زیادی مصرف کند.
-
کارایی در گرافهای وزندار: BFS برای یافتن کوتاهترین مسیر در گرافهای وزندار مناسب نیست.
-
تعیین مسیر واقعی: در حالی که BFS کوتاهترین مسیر را از نظر تعداد یالها پیدا میکند، اما لزوماً بهترین مسیر را از نظر دیگر معیارها (مانند هزینه، زمان و غیره) پیدا نمیکند.
کد الگوریتم جستجوی سطحی در ++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); // اجرای الگوریتم جستجوی عرضی از گره 1 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) # اجرای الگوریتم جستجوی عرضی از گره 1 print("BFS starting from node 1:", end=" ") bfs(node1)
سخن آخر در مورد الگوریتم جستجوی سطحی
در کل، الگوریتم جستجوی عرضی یک روش قدرتمند و پایهای برای کاوش در ساختارهای گراف است که در بسیاری از مسائل محاسباتی کاربرد دارد. این الگوریتم به ویژه در موقعیتهایی که نیاز به جستجوی سریع و کامل در یک گراف وجود دارد، مؤثر است و میتواند به عنوان یک ابزار اساسی در حل مسائل مختلف محاسباتی مورد استفاده قرار گیرد. در پایان ذکر دوباره این نکته ضروری است که به طور کلی مسئله جستجو با پیچیدگی نمایی، نمی تواند با الگوریتم ناآگاهانه حل شود مگر این که نمونه مسئله بسیار کوچک باشد.
- فضای جستجو در الگوریتم — بررسی فضای حالات 2 مسئله معروف
- آموزش پیمایش درخت به صورت جامع همراه با مثال
- پیاده سازی الگوریتم *A در بازی maze برای یافتن کوتاهترین مسیر
- سورس کد بازی دوز یا XO با الگوریتم Max-Min در ++C
- آموزش الگوریتم دیکسترا Dijkstra برای یافتن کوتاهترین مسیر
- آموزش 0 تا 100 الگوریتم Huffman بصورت مرحله به مرحله
- پاورپوینت درمورد زبان های برنامه نویسی هوش مصنوعی
- آموزش طراحی الگوریتم از پایه — اصول 7 گانه طراحی الگوریتم
- آموزش کامل درخت پوشای مینیمم
- سورس کد حل مسئله 8 وزیر با روش عقبگرد Back tracking در متلب
درباره مرتضی نصیر اقدم
دانشجوی دکتری تخصصی هوش مصنوعی، مدرس دانشگاه آزاد اسلامی، کارآفرین برتر در حوزه کسب و کارهای هوشمند، ایده پرداز در حوزه کسب و کارهای دیجیتال. ایشان در زمینه برنامه نویسی های هوشمند، الگوریتم های تکاملی و زبان های برنامه نویسی هوش مصنوعی سابقه تدریس فعال دارند.