برق. قدرت. کنترل. الکترونیک. مخابرات. تاسیسات.

دایره المعارف تاسیسات برق (اطلاعات عمومی برق)

یک مثال کلاسیک از عقبگرد، مسئله n وزیر است.
- هدف از مسئله n وزیر ، چیدن n مهره وزیر در یک صفحه شطرنج است ، به طوری که هیچ دو وزیری یکدیگر را گارد ندهند. یعنی هیچ دو مهره ای نباید در یک سطر، ستون یا قطر یکسان باشند.

- عقبگرد حالت اصلاح شده ی جست و جوی عمقی یک درخت است.

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

الگوریتم عقبگرد برای مسئله n وزیر

كد:
void queens ( index i)
{
index j;
if ( promising(i))
if ( i == n)
cout << col [1] through col [n];
else
for ( j = 1 ; j ≤ n ; j++ ) {

col [ i +1 ] = j;
queens ( i + 1);
}
}
bool promising ( index i )
{
index k ;
bool switch;
k = 1;
switch = true ;
while ( k < i && switch ) {
if (col [i] == col[k] || abs(col[i] – col[k] == i-k)
switch = false;
k++;
}
return switch;

}


http://artificial.ir/intelligence/حل-مسائل-معروف-هوش-مصنوعی/619-حل-مسئله-8-وزیر-با-روش-های-مختلف-2.html


و توضیحی دیگر که در آدرس http://www.pcpedia.ir/ViewArticle.aspx?ID=80 بود

مساله هشت وزیر از جمله مسائل پرمخاطب مباحث طراحی الگوریتمه:۸ مهره وزیر رو روی صفحه شطرنج چنان بچینید که نتونن همدیگه رو تهدید کنن. 

موضوع مقاله: الگوریتم

مساله هشت وزیر از جمله مسائل پرمخاطب مباحث طراحی الگوریتمه:۸ مهره وزیر رو روی صفحه شطرنج چنان بچینید که نتونن همدیگه رو تهدید کنن.




برای افرادی که با بازی شطرنج آشنایی ندارن:


وزیر مهره ای از مهره های بازی شطرنجه که می تونه در تمامی 8 جهت هر تعداد خانه - تا زمانی که مهره ای مانع نباشه - حرکت کنه و اگه در یکی از این خانه ها مهره حریف قرار داشته باشه تهدیدش کنه.









ما مساله رو در حالت کلی در نظر می گیریم. یعنی زمانی که ابعاد صفحه شطرنج n در n و تعداد مهره ها n هستش. ( n > 3 )

روشهای مختلفی برای پیدا کردن جواب وجود داره. یکی از این روشها چیدن تصادفی مهره ها روی صفحه شطرنجه! به عبارت دیگه n مهره رو به صورت تصادفی در خانه های مختلف صفحه قرار می دیم و بررسی می کنیم که آیا شرط مساله رو برآورده می کنن یا نه؟ این روش بسیار سریع ما رو به جواب می رسونه. اما ایرادی که داره نمی شه مطمئن بود بشه به همه حالتهای چینش دست پیدا کرد. در صفحه 8 در 8 شطرنج این مساله 92 جواب مختلف داره. شما ممکنه روش تصادفی رو هزار بار به کار ببرید، اما نتونید همه 92 حالت ممکنه رو به دست بیارید. این روش زمانی مفیده که پیدا کردن یه جواب برای ما کافی باشه. و اما روش دیگه . . .

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







برای پیاده سازی چنین الگوریتمی و تشخیص اینکه چه خانه هایی از سطر امن هستن روشهای مختلفی وجود داره. ساده ترینشون اینه که هر بار تمامی خانه هایی رو که امکان تهدید شدن از اونها وجود داره بررسی کنیم تا از قرار نداشتن مهره وزیر در اونها مطمئن باشیم. اما این روش اصلا کارا و بهینه نیست.

روش دیگه تعریف کردن صفحه شطرنج به صورت یه آرایه n در n هستش که خونه های امن و غیر امن با علامتگذاری مشخص می شن. هر بار که مهره ای رو صفحه قرار می گیره تمام خونه هایی که توسط این مهره تهدید می شن به صورت غیر امن علامتگذاری می شن. به این ترتیب می شه فهمید که هر خونه با توجه به چینش مهره های قبلی امن هست یا نه؟ اما این روش هم معایبی داره که باعث می شه به روش سوم رجوع کنیم. برای آشنایی با این معایب کافیه سعی کنید کد برنامه رو بنویسید!

در روش سوم که من ازش استفاده کردم، برای علامتگذاری خانه های امن و غیر امن از شیوه دیگه ای بهره می بریم. به این ترتیب که اقطار راست به چپ، چپ به راست و ستونها با شماره هایی مشخص می شن که کار علامتگذاری رو بسیار ساده می کنن. این روش بدون شک از کاراترین روشهای رسیدن به جواب مساله ماست. هم سرعت اجرای بالایی داره و هم حافظه مصرفی بسیار کم!

کدی که به زبان ++C درباره این مساله نوشته شده با استفاده از روش سوم تعداد جوابهای ممکن - و نه خود جوابها - برای مقادیر مختلف n رو مشخص می کنه. به عنوان مثال اگر n رو 8 وارد کنید خروجی برنامه 92 خواهد بود. توصیه می کنم برای nهای بزرگ برنامه رو امتحان نکنید! اگر n رو 16 وارد کنید بعد از گذشتن زمان زیادی عدد 14772512 روی صفحه نمایش چاپ می شه. یعنی در صفحه شطرنج 16 در 16 حدود ۱۵ میلیون حالت مختلف برای چیدمان صحیح وجود داره!!

این برنامه که برای کامپایل در Dev C++ نوشته شده، طول اضلاع صفحه شطرنج و تعداد وزیر ها رو گرفته و سپس به کمک توابع بازگشتی، تمامی حالات قرار گرفتن اونها رو طوری که یکدیگر رو تهدید نکنند، با زدن یک کلید نمایش میده.

کد برای کامپایل با Turbo C++

#include <conio.h>
#include <iostream.h>
#include <iomanip.h>
#include <stdlib.h>

const int m=20;
int k[m][m];
int Count=0;
int v=0 , n=0 , i=0 , j=0 , state=0;

void remove(int i,int j)
{
      int p,q;
      k[i][j]=0;
      Count--;
      for(p=0;p<n;p++)
          if(p!=i)
              k[p][j]--;
      for(p=0;p<n;p++)
        if(p!=j)
                  k[i][p]--;
      p=i+1;
      q=j+1;
     while(p<n && q<n)
      {
                    k[p++][q++]--;
     }
      p=i-1;
      q=j-1;
     while(p>=0 && q>=0)
      {
               k[p--][q--]--;
      }
     p=i+1;
      q=j-1;
     while(p<n && q>=0)
      {
               k[p++][q--]--;
      }
     p=i-1;
      q=j+1;
     while(p>=0 && q<n)
     {
                    k[p--][q++]--;
     }
}

int apply(int i,int j)
{
      int p,q;
     k[i][j]=1;
     Count++;
      for(p=0;p<n;p++)
        if(p!=i)
              k[p][j]++;
      for(p=0;p<n;p++)
        if(p!=j)
              k[i][p]++;
      p=i+1;
     q=j+1;
     while(p<n && q<n)
      {
               k[p++][q++]++;
     }
      p=i-1;
     q=j-1;
     while(p>=0 && q>=0)
      {
               k[p--][q--]++;
     }
      p=i+1;
     q=j-1;
     while(p<n && q>=0)
     {
                    k[p++][q--]++;
     }
     p=i-1;
     q=j+1;
      while(p>=0 && q<n)
     {
               k[p--][q++]++;
      }
      return 0;
}

void draw()
{
      clrscr();
     for(int p=0;p<n;p++)
     {
             for(int q=0;q<n;q++)
                 {
                     if(k[p][q]!=1)
                                   cout<<setw(3)<<'.';
                     else
                                   cout<<setw(3)<<'X';
                 }
             cout<<endl<<endl;
     }
     cout<<endl<<endl<<"Total states founded for "<<n<<"*"<<n<<" boards and "<<v<<" Queens: "<<state<<endl;
}

void check()
{
     if(Count==v)
     {
                      state++;
                 draw();
                 cout<<endl<<endl<<"Press q to exit or any key to continue...";
                 int c=getch();
                      if(c=='q')exit(0);
     }
}

void move(int p,int q)
{
     apply(p,q);
     check();
      for(int i=p;i<n;i++)
     {
             for(int j=0;j<n;j++)
                 if(k[i][j]==0)
                    move(i,j);
     }
      remove(p,q);
}

int main()
{
    cout<<"**************Queens******************"<<endl<<endl;
     cout<<"Enter size of board :";
    cin>>n;
    cout<<"Enter number of queens:";
    cin>>v;
     clrscr;
    draw();
     for(i=0;i<n;i++)
        for(j=0;j<n;j++)
            move(i,j);
           
     clrscr;
    cout<<"Total states:"<<state<<endl;
     getch();
    return 0;
}


//end


 

این برنامه که برای کامپایل کردن در Turbo C++ نوشته شده، طول اضلاع صفحه شطرنج و تعداد وزیر ها رو گرفته و سپس به کمک توابع بازگشتی، تمامی حالات قرار گرفتن اونها رو طوری که یکدیگر رو تهدید نکنند، با زدن یک کلید نمایش میده.

کد برای کامپایل در Dev C++

#include <conio.h>
#include <iostream>
#include <iomanip>
#include <stdio.h>
#include <stdlib.h>
using namespace std;

const int m=20;
int k[m][m];
int Count=0;
int v=0 , n=0 , i=0 , j=0 , state=0;

void remove(int i,int j)
{
     int p,q;
     k[i][j]=0;
     Count--;
     for(p=0;p<n;p++)
        if(p!=i)
              k[p][j]--;
     for(p=0;p<n;p++)
        if(p!=j)
              k[i][p]--;
     p=i+1;
     q=j+1;
     while(p<n && q<n)
     {
               k[p++][q++]--;
     }
     p=i-1;
     q=j-1;
     while(p>=0 && q>=0)
     {
               k[p--][q--]--;
     }
     p=i+1;
     q=j-1;
     while(p<n && q>=0)
     {
               k[p++][q--]--;
     }
     p=i-1;
     q=j+1;
     while(p>=0 && q<n)
     {
               k[p--][q++]--;
     }
}

int apply(int i,int j)
{
     int p,q;
     k[i][j]=1;
     Count++;
     for(p=0;p<n;p++)
        if(p!=i)
              k[p][j]++;
     for(p=0;p<n;p++)
        if(p!=j)
              k[i][p]++;
     p=i+1;
     q=j+1;
     while(p<n && q<n)
     {
               k[p++][q++]++;
     }
     p=i-1;
     q=j-1;
     while(p>=0 && q>=0)
     {
               k[p--][q--]++;
     }
     p=i+1;
     q=j-1;
     while(p<n && q>=0)
     {
               k[p++][q--]++;
     }
     p=i-1;
     q=j+1;
     while(p>=0 && q<n)
     {
               k[p--][q++]++;
     }
}

void draw()
{
     system("cls");
     for(int p=0;p<n;p++)
     {
             for(int q=0;q<n;q++)
             {
                     if(k[p][q]!=1)
                                   cout<<setw(3)<<'.';
                     else
                                   cout<<setw(3)<<'X';
             }
             cout<<endl<<endl;
     }
     cout<<endl<<endl<<"Total states founded for "<<n<<"*"<<n<<" boards and "<<v<<" Queens: "<<state<<endl;
}

void check()
{
     if(Count==v)
     {
                 state++;
                 draw();
                 cout<<endl<<endl<<"Press q to exit or any key to continue...";
                 int c=getch();
                 if(c=='q')exit(0);
     }
}

void move(int p,int q)
{
     apply(p,q);
     check();
     for(int i=p;i<n;i++)
     {
             for(int j=0;j<n;j++)
                 if(k[i][j]==0)
                    move(i,j);
     }
     remove(p,q);
}

int main()
{
    cout<<"**************Queens******************"<<endl<<endl;
    cout<<"Enter size of board :";
    cin>>n;
    cout<<"Enter number of queens:";
    cin>>v;
    system("cls");
    draw();
    for(i=0;i<n;i++)
        for(j=0;j<n;j++)
            move(i,j);
           
    system("cls");
    cout<<"Total states:"<<state<<endl;
    getch();
    return 0;
}


//end


 

http://cppp.mihanblog.com

استراتژی جورج پولیا در حل مساله:

 

پولیا می گوید : روند حل مساله عبارت است از :" جستجوی راه خروج از دشواری ها یا مسیر عبور از مانع ها " . پولیا مراحل حل مساله را که شامل چهار مرحله است به صورت زیر بیان می کند :

 

1)   فهم مساله

2)   تهیه طرح یا نقشه مناسب برای حل مساله

3)   اجرای طرح یا نقشه

4)   بازنگری

1-   فهم مساله : برای حل مساله ابتدا باید صورت مساله را خوب درک کرد . پس اولین وظیفه برای حل یک مساله , فهم درست و کامل یک مساله است . پولیا معتقد است برای حل یک مساله باید موارد زیر به خوبی روشن شود :

 الف) چه چیزی را باید پیدا کرد ؟ ( مجهول چیست ؟)

ب) چه چیزی مفروض است ؟( معلومات چیست ؟)

ج) چه رابطه ای بین مجهولات و معلومات موجود است ؟

   2- تهیه طرح یا نقشه برای حل مساله : ممکن است برای حل یک مساله چندین راه موجود باشد اما باید به دنبال طرحی بگردیم که ما را مستقیما به هدف برساند . درین راه می توان از مسایل کمکی نیز استفاده کرد .

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

2-   اجرای طرح یا نقشه : پس از تهیه طرح باید آنرا به اجرا گذاشت . نکته اساسی این است که شخص نظارت کامل بر پیشرفت اجرای طرح داشته باشد تا اگر زمانی احساس کرد که ممکن است او را به حل مساله نرساند بتواند طرح جدیدی را تهیه و اجرا کند .

3-   بازنگری : پس از اتمام مرحله اجرا , حل کننده مساله باید یک بازنگری بر تمامی مراحل داشته باشد و جوابها و برهان ها را امتحان کند .

 

(( اگر می خواهید شنا یاد بگیرید با شجاعت وارد آب شوید و اگر می خواهید مساله ها را یاد بگیرید آنها را حل کنید . ))

/

صفحات جانبی

نظرسنجی

    لطفاً نظرات خود را درمورد وبلاگ با اینجانب در میان بگذارید.(iman.sariri@yahoo.com)نتایج تاکنون15000مفید و 125غیرمفید. با سپاس


  • آخرین پستها

آمار وبلاگ

  • کل بازدید :
  • تعداد نویسندگان :
  • تعداد کل پست ها :
  • آخرین بازدید :
  • آخرین بروز رسانی :