روش بازگشت به عقب و مسئله ی n وزیر و الگوریتم و توضیحات آن
یکی از مسائل جالب تکنیک backtracking یا بازگشت به عقب همین مسئله ی n وزیر است.
بررسی یک تکنیک طراحی الگوریتم - روش بازگشت به عقب
قبل از شروع یک توضیح کوتاهی بر روی تکنیک بازگشت به عقب می دهیم :
در این روش ، در هر زمان که متوجه شدیم مسیر انتخاب شده به جواب نمیرسد، یک مرحله به عقب برگشته و مسیر دیگری را دنبال می کنیم.
مسائلی که با روش عقب گرد حل می شوند اغلب مسائل تصمیم گیری هستند و باید توجه کنید که این روش فقط با کاهش حالت ها ، زمان اجرا را کاهش می دهد و مرتبه ی زمانی را تغییر نمی دهد
این روش از اصول درخت ها و به ویژه پیمایش preorder استفاده می کند.
برای مثال در کتاب طراحی الگوریتم انتشارت پوران پژوهش مثالی برای درک این مورد زده است.
"فرض کنید یک قفل رمزی دیجیتالی دارید و رمز قفل یک عدد n بیتی است.تعدا حالت های امتحان 2 به توان n خواهد بود، در حالی که قفل با یک حالت باز می شود.
اگر n=3 باشد باید 8 حالت را بررسی کنیم اما اگر بدانیم که رمز شامل رو رقم 11 هست تعدا حالت های بررسی کمتر می شود.
درخت فضای حالت state tree برای این کار است "
دقت کنید در این درخت وقتی به یک گره می رسیم بررسی می کند که آیا این گره امید بخش هست یا نه؟
اگر بود چک می کند که آیا جواب در این گره هست ؟ اگر بود آن را چاپ می کند و اگر نبود همین عمل را به صورت بازگشتی با child های آن گره انجام می دهد.
اگر یک گره امید بخش نبود، خود به خود عقب گرد کرده و کار با فرزند دیگر پدر آن گره ادامه می دهد.
شکل 1 این را نشان می دهد.
نتیجه : الگوریتم عقبگرد همانند جست و جوی عمقی است، با این تفاوت که فرزندان یک گره فقط هنگامی ملاقات می شوند که گره امید بخش باشدو در آن گره حلی وجود نداشته باشد.
یک برنامه ی سطح بالا برای این روش به صورت زیر است :
reject(P,c): return true only if the partial candidate c is not worth completing.
accept(P,c): return true if c is a solution of P, and false otherwise.
first(P,c): generate the first extension of candidate c.
next(P,s): generate the next alternative extension of a candidate, after the extension s.
output(P,c): use the solution c of P, as appropriate to the application.
کد:
کد PHP:
procedure bt(c)
if reject(P,c) then return
if accept(P,c) then output(P,c)
s ← first(P,c)
while s ≠ Λ do
bt(s)
s ← next(P,s)
توضیحات مسئله ی n وزیر :
صورت مسئله : هشت وزير را در هشت خانه شطرنج (8*8) طوري قرار دهيد كه هيچكدام يكديگر را تهديد نكنند. وزير در خانه هاي شطرنج به صورت عرضي،طولي و قطري مي تواند حركت كند. اين مسئله قابل تعميم به مسئله N وزير در يك شطرنج N*N است.
سایت برنامه نویس در مورد تاریخچه ی این الگوریتم می نویسد :
"تاريخچه: اين مسئله در سالي 1848 توسط شطرنج بازي به نام Max Bezzel عنوان شد و رياضي دانان بسياري ازجمله Gauss و Georg Cantor بر روي اين مسئله كار كرده و در نهايت آنرا به N وزير تعميم دادند. اولين راه حل توسط Franz Nauck در سال 1850 ارائه شد كه به همان مسئله N وزير تعميم داده شد. پس از آن Gunther راه حلي با استفاده از دترمينان ارائه داد كه J.W.L. Glaisher آنرا كامل نمود.
در سال 1979 ، Edsger Dijkstra با استفاده از الگوريتم عقب گرد اول عمق اين مسئله را حل كرد."
با توجه به اینکه هیچ 2 وزیری نباید همدیگر را گارد کنند و در یک سطر نمی توانند باشند، تعداد کل حالت ها برای n=4 برابر 4*4*4*4=256 است.
یک راه حل برای این مسئله :
"میدانیم که در شطرنج یک وزیر میتواند به مهرههایی که در خانههای عمود یا مورب به وی قرار دارند حمله کند. یا به عبارت ریاضی، اگر ردیفها و ستونهای شطرنج را از یک تا هشت شماره گذاری کنیم و وزیر در خانه (i, j) قرار داشته باشد، مهرههایی که در خانههای (i, m) یا (m, j) یا (i ± m, j ± m) قرار دارند توسط وزیر تهدید میشوند.
برای سادگی تشریح این مسئله با استفاده از روش بازگشت به عقب، فرض میکنیم که خانههای شطرنج 4x4 و تعداد وزیرها نیز 4 باشد. سپس بعد از یافتن راه حل برای این مسئله ساده شده، اقدام به نوشتن الگوریتم برای مسئله اصلی میکنیم.
خوب، مراحل جستجو برای یافتن جواب را به این صورت دنبال می کنیم که:
وزیر اول را در ردیف اول و ستون اول قرار میدهیم.
در ردیف دوم از اولین ستون به جلو رفته و به دنبال خانهای میگردیم که مورد تهدید وزیر اول نباشد و وزیر دوم را در این خانه قرار میدهیم.
همانند قبل، در ردیف سوم از اولین ستون به جلو رفته و به دنبال خانهای میگردیم که مورد تهدید وزیران اول و دوم نباشد. میبینیم که چنین خانهای موجود نیست.
پس به عقب یعنی ردیف دوم برگشته و وزیر دوم را به خانهای دیگر از ردیف دوم منتقل میکنیم که مورد تهدید وزیر اول نباشد.
دوباره در ردیف سوم اولین خانهای را میابیم که مورد تهدید دو وزیر قبلی نباشد. این بار خانه را مییابیم و وزیر سوم را در آن قرار میدهیم.
همانند قبل، در ردیف چهارم به دنبال اولین خانهای میگردیم که مورد تهدید وزیران پیشین نباشد. چنین خانهای موجود نیست.
به ردیف قبل یعنی ردیف سوم باز میگردیم تا خانهای دیگر برای وزیر سوم بیابیم. خانه دیگری وجود ندارد.
به ردیف قبل یعنی ردیف دوم بر میگردیم تا خانه دیگری برای وزیر دوم پیدا کنیم. به آخرین ستون رسیدهایم و خانه دیگری نیست.
به ردیف قبل یعنی ردیف اول بر میگردیم و وزیر اول را یک ستون به جلو میبریم.
در ردیف دوم اولین خانهای را میابیم که مورد تهدید وزیر اول نباشد و وزیر دوم را در آن خانه قرار میدهیم.
در ردیف سوم اولین خانهای را میابیم که مورد تهدید وزیران اول و دوم نباشد و وزیر سوم را در آن خانه میگذاریم.
در ردیف چهارم اولین خانهای را میابیم که مورد تهدید وزیران پیشین نباشد. این بار خانه را مییابیم و وزیر چهارم را در آن خانه قرار می دهیم.
خوب به یک جواب رسیدیم. حال اگر فرض کنیم که این خانه جواب نیست و به مسیر خود ادامه دهیم، احتمالا" میتوانیم جوابهای دیگری نیز بیابیم."
پیاده سازی الگوریتم عقبگرد برای مسئله n وزیر :
یک شبه کد برای این الگوریت که در کتاب نپولیتان هم نوشته شده است به صورت زیر است :
کد:
کد PHP:
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;
}
پاسخ : روش بازگشت به عقب و مسئله ی n وزیر و الگوریتم و توضیحات آن
برای اینکه با این مسئله خوب آشنا بشید و به صورت ویژوال کار آن را ببینید به لینک زیر بروید :
این لینک کد زیر را به صورت انیمیشن به شما نشان داده است :
کد PHP:
کد:
/** Recursive 8 Queens Solution.
* @author John McHugh
*/
private void expand (BitSet RowsToBeFilled, BitSet ColsToBeFilled,
BitSet LeftDiag, BitSet RightDiag)
{
int r, c ;
BitSet CopyOfColsToBeFilled = (BitSet) ColsToBeFilled.clone () ;
BitSet CopyOfRowsToBeFilled = (BitSet) RowsToBeFilled.clone () ;
if (empty (RowsToBeFilled))
{
store (Solution) ;
found++;
}
else
{
r = AnyFrom (CopyOfRowsToBeFilled) ;
CopyOfRowsToBeFilled.clear (r) ;
while (! empty (CopyOfColsToBeFilled))
{
c = AnyFrom (CopyOfColsToBeFilled) ;
CopyOfColsToBeFilled.clear (c) ;
if (LeftDiag.get (r + c - 1) & RightDiag.get (r - c + 8))
{
Solution [r] = c ;
ColsToBeFilled.clear (c) ;
LeftDiag.clear (r + c - 1) ;
RightDiag.clear (r - c + 8) ;
expand (CopyOfRowsToBeFilled, ColsToBeFilled,
LeftDiag, RightDiag) ;
ColsToBeFilled.set (c) ;
Solution [r] = 0 ;
LeftDiag.set (r + c - 1) ;
RightDiag.set (r - c + 8) ;
}
}
}
ورود به این سایت :
http://www.animatedrecursion.com/advance...oblem.html
همچنین یک Depth First Algorithm برای n وزیر به صورت زیر می تواند باشد :
http://img134.imageshack.us/img134/4...owchartaa6.jpg
Download source files - 3 Kb
Download demo project - 5 Kb
پاسخ : روش بازگشت به عقب و مسئله ی n وزیر و الگوریتم و توضیحات آن
همچنین این برنامه به زبان c# نیز نوشته شده است که 1نمونه ی آن را برای شما می آورم :
Contents: Executable (Windows), Source Code (C#)
همچنین سورس کد در c++ به صورت زیر است :
کد:
کد PHP:
using System;
namespace EightQueen
{
public enum SIZE
{
size = 8
}
public class EightQueen
{
public static int count = 0;
public static bool isValidMove(int[,] boardArr, int row, int col)
{
for (int i = 0; i < SIZE.size.GetHashCode(); i++)
if (boardArr[row,i] == 1)
return false;
for (int i = 0; i < SIZE.size.GetHashCode(); i++)
if (boardArr[i,col] == 1)
return false;
int tempCol = col + 1, tempRow = row ;
for (int i = row + 1; i < SIZE.size.GetHashCode(); i++)
{
if (tempCol < SIZE.size.GetHashCode())
{
if (boardArr[i,tempCol] == 1)
return false;
else
tempCol++;
}
else
break;
}
tempCol = col - 1;
for (int i = row - 1; i >= 0; i--)
{
if (tempCol >= 0)
{
if (boardArr[i,tempCol] == 1)
return false;
else
tempCol --;
}
else
break;
}
tempCol = col - 1;
for (int i = row + 1; i < SIZE.size.GetHashCode(); i++)
{
if (tempCol >= 0)
{
if (boardArr[i, tempCol] == 1)
return false;
else
tempCol--;
}
else
break;
}
tempCol = col + 1;
for (int i = row - 1; i >= 0; i--)
{
if (tempCol < SIZE.size.GetHashCode())
{
if (boardArr[i, tempCol] == 1)
return false;
else
tempCol++;
}
else
break;
}
return true;
}
public static void ShouldPrintBoard(int[,] boardArr)
{
int count = 0;
for (int i = 0; i < SIZE.size.GetHashCode(); i++)
for(int j = 0; j < SIZE.size.GetHashCode() ;j++)
if (boardArr[i,j] == 1)
count++;
if (count >= 8)
PrintBoard(boardArr);
}
public static void PrintBoard(int[,] boardArray)
{
for (int i = 0; i < SIZE.size.GetHashCode(); i++)
{
for (int j = 0; j < SIZE.size.GetHashCode(); j++)
Console.Write("{0} ", boardArray[i, j]);
Console.WriteLine();
}
count++;
Console.WriteLine();
//Console.ReadKey();
}
public static void PermuteBoard(int[,] boardArr, int row, int col)
{
for (int i = row; i < SIZE.size.GetHashCode(); i++)
{
for (int j = 0; j < SIZE.size.GetHashCode(); j++)
{
if (isValidMove(boardArr, i, j))
{
boardArr[i, j] = 1;
ShouldPrintBoard(boardArr);
PermuteBoard(boardArr, i + 1, j + 1);
boardArr[i, j] = 0;
}
}
}
}
static void Main(string[] args)
{
int [,]boardArr = new int[SIZE.size.GetHashCode(),SIZE.size.GetHashCode()];
for(int i = 0 ; i < SIZE.size.GetHashCode() ; i++)
for(int j = 0 ; j < SIZE.size.GetHashCode() ; j++)
boardArr[i,j] = 0;
PermuteBoard(boardArr, 0, 0);
Console.WriteLine("Total Solutions {0}", count);
Console.ReadKey();
}
3 فایل پیوست
پروژه هاي دانشجويي - پروژه های آماده c , c++
- الگوریتم پرایم همراه با سورس کامل برنامه
- الگوريتم استراسن با حل و سورس کامل برنامه
- الگوریتم کراسکال با سورس کامل برنامه
پاسخ : پروژه هاي دانشجويي - پروژه های آماده c , c++
- ماشين حساب مهندسي همراه با سورس کامل برنامه 1
لینک دانلود فایل اجرایی EXE برنامه
DOWNLOAD - ماشين حساب مهندسي همراه با سورس کامل برنامه 2
لینک دانلود فایل اجرایی EXE برنامه
DOWNLOAD
پیاده سازی درخت جستجوی دو دویی Binary Search Tree
لینک دانلود فایل اجرایی EXE برنامه DOWNLOAD
کلیه عملیات ماتريس ها (ضرب ، جمع ، تفريق ، تقسيم ماتريس
مغلوب و ترانهاده و ...)
لینک دانلود فایل اجرایی EXE برنامه
DOWNLOAD
- برنامه دفترچه تلفن (با امکانات حذف - اضافه - جستجو - گزارش
گیری و نمایش )
لینک دانلود فایل اجرایی EXE برنامه
DOWNLOAD
پاسخ : پروژه هاي دانشجويي - پروژه های آماده c , c++
- پروژه هشت وزير شطرنج در 92 حالت مختلف
لینک دانلود فایل اجرایی EXE برنامه
DOWNLOAD پروژه N وزیر شطرنج (هوش مصنوعی) - الگوریتم ژنتیک
لینک دانلود فایل اجرایی EXE برنامه
DOWNLOAD - بازی پازل اعداد PUZZLE به زبان سی پلاس C++
لینک دانلود فایل اجرایی EXE برنامه DOWNLOAD - بازی پازل اعداد PUZZLE به زبان سی C
لینک دانلود فایل اجرایی EXE برنامه DOWNLOAD -پياده سازي كليه روشهاي مرتب سازي
لینک دانلود فایل اجرایی EXE برنامه
DOWNLOAD
پاسخ : پروژه هاي دانشجويي - پروژه های آماده c , c++
- مثلث خيام پاسكال
لینک دانلود فایل اجرایی EXE برنامه
DOWNLOAD
- برنامه دانش آموزان : گرفتن اطلاعات و ذخيره - حذف - اضافه گزارش گيري - جستجو - و ...
لینک دانلود فایل اجرایی EXE برنامه DOWNLOAD - لينك ليست
- بازي مار پله
- برنامه فاكتوريل
- حركت اسب شطرنج
- بازي پارانوئيد - پارانوييد Paranoid
لینک دانلود فایل اجرایی EXE برنامه DOWNLOAD
- يك ماشين حساب خطي با در نظر گرفتن پرانتزها
و تقدم عملگرها
- لینک دانلود فایل اجرایی EXE برنامه DOWNLOAD
پاسخ : پروژه هاي دانشجويي - پروژه های آماده c , c++
- بازي حافظه - در يك پازل بعد از پيدا كردن خانه هايي كه 2 عدد شبيه هم هستند را حذف مي كند
لینک دانلود فایل اجرایی EXE برنامه DOWNLOAD
- حل مسئله رياضي سري تيلور
لینک دانلود فایل اجرایی EXE برنامه DOWNLOAD
- شبيه سازي بازي تانك
لینک دانلود فایل اجرایی EXE برنامه DOWNLOAD
- بازي دوز
dooz لینک دانلود فایل اجرایی EXE برنامه DOWNLOAD
- يك برنامه
ويرايشگر متن اديتور Text Editor مانند اديتور سيستم ويندوز - لینک دانلود فایل اجرایی EXE برنامه DOWNLOAD
- برنامه ي معكوس نمودن عدد ورودي : 124 421
لینک دانلود فایل اجرایی EXE برنامه DOWNLOAD
- برنامه مربع جادويي
- ماتريسي كه جمع سطر و ستونهاي آن و همچنين جمع قطرهاي آن از همه طرف برابر است . لینک دانلود فایل اجرایی EXE برنامه DOWNLOAD
پاسخ : پروژه هاي دانشجويي - پروژه های آماده c , c++
مقسوم علیه ها
این برنامه برای محاسبه مقسوم علیه هاست که می تونید از اینجا بیگیرید
طرز کار برنامه بدین صورت است که شما یک عدد طبیعی را وارد می کنید و برنامه مقسوم علیه های آن را بر می گرداند
تبدیل دما
این برنامه که این دفعه می ذارم ، برنامه تبدیل واحدهاست.البته تا الان فقط مخصوص دما رو آماده کردم که می تونید از اینجا دانلود کنید و لذت ببرید.
این برنامه امکان تبدیل واحدهای سانتیگراد ، فارنهایت و کلوین به یکدیگر را دارد.
مقلوب
این برنامه که در این قسمت برای دانلود قرار گرفته ، برای محاسبه مقلوب عدد می باشد
شما عدد خود را وارد می کنید و برنامه مقلوب آنرا بر می گرداند
تبدیل عدد به حروف
این برنامه که خودش و سورسش رو تو این قسمت می ذارم،برنامه نوشتن عدد به حروف است.
(در زبان انگلیسی) شما عدد خود را وارد می کنید، حداکثر تا میلیون و با دقت اندازه گیری یک،
و بعد برنامه آنرا بصورت حروف برمی گرداند.
در این برنامه از ساختار switch و case استفاده شده است و با اینکه تعداد خطوط زیادی را شامل می شودُ برنامه بسیار ساده ایست..
دانلود فایل zip حجم:۱۳۰ کیلوبایت