نمايش پست تنها
قديمي ۰۹-۱۳-۱۳۸۸, ۰۷:۵۱ بعد از ظهر   #11 (لینک دائم)
Astaraki Female
Administrator
 
آواتار Astaraki
 
تاريخ عضويت: خرداد ۱۳۸۷
محل سكونت: تهران-کرج!
پست ها: 3,465
تشكرها: 754
16,337 تشكر در 3,127 پست
My Mood: Mehrabon
ارسال پيغام Yahoo به Astaraki
Wink

یک مثال کلاسیک از عقبگرد، مسئله 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;
 }
Astaraki آفلاين است   پاسخ با نقل قول
از Astaraki تشكر كرده اند:
green_Dream (۱۱-۲۲-۱۳۸۸), hacking lover (۱۱-۲۷-۱۳۹۰), tohidsabunchi (۰۸-۱۰-۱۳۸۹)

  #ADS
نشان دهنده تبلیغات
تبليغگر
 
 
 
تاريخ عضويت: -
محل سكونت: -
سن: 2010
پست ها: -
 

نشان دهنده تبلیغات is online