توضیحات فایل

 

الگوریتم جستجوی اول سطح (BFS)

معرفی الگوریتم جستجوی اول سطح (BFS) برای پیمایش گراف و کاربردهای آن به همراه قطعه کد به زبان برنامه‌نویسی ++C

الگوریتم پیمایش اول سطح یا جستجوی اول سطح (Breadth First Search – BFS) از جمله الگوریتم‌های مشهور پیمایش و جستجوی گراف است که در حل مسائل الگوریتمی و هوش مصنوعی کاربرد دارد. این الگوریتم برای پیمایش و جستجوی گراف از یک صف برای نگهداری ترتیب جستجو استفاده می‌کند.

الگوریتم BFS با وارد کردن گره مبدأ به صف پردازش شروع شده و تا خالی نشدن این صف مراحل زیر را تکرار می‌شود:

۱- عنصر جلوی صف را به عنوان گره جاری انتخاب و از صف حذف کن.

۲- گره جاری را پردازش کن.

۳- گره‌های مجاور گره جاری که پردازش نشده و در صف پردازش نیز قرار ندارند به این صف اضافه کن.

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

به عنوان مثال در گراف زیر:

 

جستجوی اول سطح - BFS

 

ترتیب پیمایش گره‌ها با شروع از گره شماره‌ی ۱ به این ترتیب خواهد بود:

 

۱, ۲, ۳, ۴, ۸, ۷, ۵, ۶

جستجوی اول سطح - BFS

 

دلیل نام‌گذاری این روش با عبارت “اول سطح” در پیمایش یک درخت از ریشه مشخص می‌شود که گره‌ها به صورت سطح به سطح پیمایش می‌شوند و اولویت پیمایش با سطح گره است.

نکته: ممکن است هدف از اجرای الگوریتم BFS یافتن یک گره با مشخصات خاص در گراف باشد. در این حالت گره مذکور (در صورت وجود) ممکن است زودتر از خالی شدن صف پردازش یافت شده و نیازی به ادامه‌ی الگوریتم و پیمایش سایر گره‌ها نباشد.

 

پیاده‌سازی الگوریتم جستجوی اول سطح

تابع bfs یک پیاده‌سازی ساده از الگوریتم BFS به زبان برنامه‌نویسی ++C است که با دریافت مشخصات گراف و شماره‌ی اندیس گره مبدأ، گراف را پیمایش کرده و شماره‌ی عدد هر گره را به عنوان پردازش آن چاپ می‌کند:

 

void bfs( int graph[ MAX ][ MAX ], int numberOfNodes, int sourceNode )

{

queue<int> processQueue;

bool visited[ MAX ] = { false };

processQueue.push( sourceNode );

visited[ sourceNode ] = true;

while ( !processQueue.empty() )

{

int currentNode = processQueue.front();

processQueue.pop();

cout << currentNode + 1 << “\t” << endl;

for( int i = 0 ; i < numberOfNodes ; i++ )

{

if( graph[ currentNode ][ i ] < INT_MAX && !visited[ i ] )

{

processQueue.push( i );

visited[ i ] = true;

}

}

}

}

 

این تابع با استفاده از آرایه‌ی visited قرار گرفتن گره در صف و پردازش آن را مشخص می‌کند. حلقه‌ی forبررسی یال‌های مجاور گره جاری برای اضافه شدن به صف را بر عهده داشته و حلقه‌ی while تا زمان خالی شدن صف تکرار می‌شود.

 

مرتبه‌ی زمانی الگوریتم جستجوی اول سطح

در گراف (G = (V, E مرتبه‌ی زمانی الگوریتم جستجوی اول سطح (|O(|V| + |E است؛ چرا که این الگوریتم در بزرگترین حالت تمامی گره‌ها را پیمایش کرده و نیاز به بررسی تمامی یال‌ها دارد. این مرتبه‌ی اجرایی در یک گراف همبند به صورت (|O(|E بوده (چرا؟) و در حالت کلی متناسب با تعداد یال‌ها حداکثر از مرتبه‌ی (O(n2است.

 

کاربردهای الگوریتم جستجوی اول سطح

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

کاربرد دیگری از الگوریتم BFS تولید یک درخت پوشا برای گراف است. اگر هر گره پیمایش شده در الگوریتم BFS را به گره‌هایی که توسط آن وارد صف می‌شوند متصل کنیم، یک درخت پوشا از مجموعه‌ی آن گره‌ها تولید می‌شود. اگر گراف همبند باشد، درخت حاصل درخت پوشای کل گراف خواهد بود. تکرار این کار روی مؤلفه‌های همبندی یک گراف ناهمبند نیز یک جنگل از درخت‌های پوشای محلی تولید می‌کند.

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

کاربرد دیگر الگوریتم BFS برای پیمایش صفحات مارپیچ (Maze) است که در بازی‌ها و همینطور مباحث رباتیک برای تشخیص مسیر بسیار کاربرد دارد. یک صفحه‌ی مشبک را در نظر بگیرید که دو ربات (موش) و چند خانه‌ی هدف (پنیر) در یک محوطه‌ی محصور توسط موانع قرار دارند:

 

جستجوی اول سطح - BFS - مارپیچ (Maze)

 

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

 

جستجوی اول سطح - BFS - مارپیچ (Maze)

 

تذکر: در الگوریتم جستجوی اول سطح جهت یال‌ها مهم بوده، اما وزن یال‌ها هیچ نقشی ندارند. ممکن است متناسب با نیاز، معیار وزن به طریقی در الگوریتم وارد شود؛ به عنوان مثال گره‌ها به ترتیب وزنشان وارد صف شده و پیمایش شوند؛ اما چنین قانونی در ذات این الگوریتم وجود ندارد. استفاده از این الگوریتم درmaze به خاطر بدون وزن بودن گراف معادل صفحه است. به عبارت دیگر، هزینه‌ی حرکت از یک گره به گره دیگر برابر تعداد یال‌های مسیر است. اگر یال‌ها وزن‌دار باشند، مسیر مشخص شده توسط این الگوریتم لزوما کم‌هزینه‌ترین مسیر نیست. الگوریتم دایکسترا نمونه‌ای از راهکاری مبتنی بر پیمایش BFS است که کوتاهترین مسیر در گراف‌های وزن‌دار با وزن‌های متنوع را مشخص می‌کند.

منبع: سایت الگوریتم ها

2,650,000 ریال – خرید
پسوند فایل
انتخاب دسته