پیاده سازی مسئله ۸ وزیر شطرنج توسط الگوریتم BFS

پیاده سازی مسئله ۸ وزیر شطرنج توسط

زبان برنامه نویسی : c / c++

شرح الگوریتم BFS :

الگوریتم جستجوی اول سطح (BFS)
معرفی الگوریتم جستجوی اول سطح (BFS) برای پیمایش گراف و کاربردهای آن به همراه قطعه کد به زبان برنامه‌نویسی ++C
الگوریتم پیمایش اول سطح یا جستجوی اول سطح (Breadth First Search – 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 است.

======

تصویری از فایل اجرایی پروژه : 

sample-BFS

======

بخشهایی از سورس کد این پروژه : 

# include <stdio.h>
# include <stdlib.h>
# define N 8
int board[N][N];
int Queen;
int check(int x, int y)
{
int lx,ly;
int flg=0;
lx=x;
ly=y;
//check right
while(lx<N){
if(board[lx][ly]==1)
return 1;
lx++;
}
lx=x;
ly=y;
//check left
while(lx>=0){
if(board[lx][ly]==1)
return 1;
lx–;
}
lx=x;
ly=y;
//check down
while(ly<N){
if(board[lx][ly]==1)
return 1;
ly++;
}
lx=x;
ly=y;
//check up
while(ly>=0){
if(board[lx][ly]==1)
return 1;
ly–;
}
lx=x;
ly=y;
//dia-down-right
while(lx<8 && ly<N){
if(board[lx][ly]==1)
return 1;
lx++;
ly++;
}
lx=x;
ly=y;
//dia-down-left
while(lx>=0 && ly<N){
if(board[lx][ly]==1)
return 1;
lx–;
ly++;
}
lx=x;
ly=y;
//dia-up-left
while(lx>=0 && ly>=0){
if(board[lx][ly]==1)
return 1;
lx–;
ly–;
}
lx=x;
ly=y;
//dia-up-right
while(lx<N && ly>=0){
if(board[lx][ly]==1)
return 1;
lx++;
ly–;
}
return flg;
}
void disp()
{
int i,j;
for(i=0;i<N;i++)
{
for(j=0;j<N;j++)
{
printf(“%d “,board[j][i]);
}
printf(“\n”);
}
}
void init()
{
int i,j;
for(i=0;i<N;i++)
{
for(j=0;j<N;j++)
{
board[j][i]=0;
}
}
}
void placeQueen(int x,int y)
{
board[x][y]=1;
Queen++;
}
int main(int argc, char* argv[])
{
int x,y;
int initx=0;
int inity=0;

start:
Queen=0;
init();

//printf(“FirstQ x-%d y-%d\n”,initx,inity);
placeQueen(initx,inity);
y=0;
while(y<N)
{
x=0;
while(x<N)
{
if(!check(x,y))
placeQueen(x,y);
x++;
}

 

 

 

======

دانلود کامل پروژه همراه با فایل سورس کد و فایل اجرایی آن
در تمامی ساعات شبانه روز >> پرداخت آنلاین و دانلود آنلاین پروژه

پذیرش و انجام سفارشات پروژه های شما
شماره تماس پشتیبانی سایت : ۰۹۳۹۲۷۶۱۶۳۰

======

توجه مهم :

*دوست عزیز در صورت نداشتن رمز پویا یا قطع بودن درگاه بانکی ، لطفا نام پروژه درخواستی خود را جهت هماهنگی برای دریافت شماره کارت واریزی و دریافت لینک دانلود، به واتساپ پشتیبانی سایت  ۰۹۳۹۲۷۶۱۶۳۰  ارسال کنید *(از ساعت ۸ الی ۲۳)

Related posts