تکنیکهای طراحی الگوریتم - روش بازگشت به عقب
موضوعات مرتبط:
__________________________________________________ _____________________
فرض کنید که در محله‌ای به دنبال یک کتاب فروشی خاص می‌گردیم. این کتاب فروشی در کوچه‌ای قرار دارد که نبش آن یک خواربار فروشی است و همچنین در ابتدای خیابانی که این کوچه قرار دارد یک مدرسه هست.
کاری که برای یافتن این کتاب فروشی می‌کنیم این است که در این محله ابتدا به دنبال آن خیابان فرعی می‌گردیم که در ابتدای آن یک مدرسه قرار دارد. سپس در این خیابان به دنبال کوچه‌ای می‌گردیم که یک خواربار فروشی در نبش آن است. هنگامی که کوچه را یافتیم، اگر در آن کتاب فروشی بود به جواب رسیده‌ایم وگرنه به خیابان فرعی برگشته و به دنبال کوچه‌ای دیگر می‌گردیم که یک خواربار فروشی در نبش آن باشد. اگر در این خیابان چنین کوچه‌ای وجود نداشت به خیابان اصلی برگشته و جستجوی خود را با یافتن خیابان فرعی دیگری با یک مدرسه در آن دنبال می کنیم.
روالی که برای یافتن جواب در مثال بالا دنبال شد، روش بازگشت به عقب (Backtracking) نام دارد. در این روش همانطور که در مثال مشاهده کردید، در هر زمان که متوجه شدیم مسیر انتخاب شده به جواب نمی‌رسد، یک مرحله به عقب برگشته و مسیر دیگری را دنبال می کنیم.
روش بازگشت به عقب برای آن دسته از مسائلی قابل استفاده است که برای رسیدن به جواب بتوان یک جستجوی سیستماتیک را دنبال کرد. به عنوان نمونه می‌توان بهره‌گیری از این روش را در بازیهای کامپیوتری، سیستمهای اثبات تئوریها، شبکه‌های مفهومی، هایپرتکس و ... دید.
مثال:
چگونه هشت وزیر را بر روی صفحه شطرنج قرار دهیم به گونه‌ای که هیچ یک از آنها مورد تهدید دیگری قرار نگیرد؟
می‌دانیم که در شطرنج یک وزیر می‌تواند به مهره‌هایی که در خانه‌های عمود یا مورب به وی قرار دارند حمله کند. یا به عبارت ریاضی، اگر ردیفها و ستونهای شطرنج را از یک تا هشت شماره گذاری کنیم و وزیر در خانه (i, j) قرار داشته باشد، مهره‌هایی که در خانه‌های (i, m) یا (m, j) یا (i ± m, j ± m) قرار دارند توسط وزیر تهدید می‌شوند.
http://delphiarea.com/external/8queens/queen.gif
برای سادگی تشریح این مسئله با استفاده از روش بازگشت به عقب، فرض می‌کنیم که خانه‌های شطرنج 4x4 و تعداد وزیرها نیز 4 باشد. سپس بعد از یافتن راه حل برای این مسئله ساده شده، اقدام به نوشتن الگوریتم برای مسئله اصلی می‌کنیم.
خوب، مراحل جستجو برای یافتن جواب را به این صورت دنبال می کنیم که:
- وزیر اول را در ردیف اول و ستون اول قرار می‌دهیم.
http://delphiarea.com/external/8queens/q1.gif
- در ردیف دوم از اولین ستون به جلو رفته و به دنبال خانه‌ای می‌گردیم که مورد تهدید وزیر اول نباشد و وزیر دوم را در این خانه قرار می‌دهیم.
http://delphiarea.com/external/8queens/q2.gif
- همانند قبل، در ردیف سوم از اولین ستون به جلو رفته و به دنبال خانه‌ای می‌گردیم که مورد تهدید وزیران اول و دوم نباشد. می‌بینیم که چنین خانه‌ای موجود نیست.
- پس به عقب یعنی ردیف دوم برگشته و وزیر دوم را به خانه‌ای دیگر از ردیف دوم منتقل می‌کنیم که مورد تهدید وزیر اول نباشد.
http://delphiarea.com/external/8queens/q3.gif
- دوباره در ردیف سوم اولین خانه‌ای را میابیم که مورد تهدید دو وزیر قبلی نباشد. این بار خانه را می‌یابیم و وزیر سوم را در آن قرار می‌دهیم.
http://delphiarea.com/external/8queens/q4.gif
- همانند قبل، در ردیف چهارم به دنبال اولین خانه‌ای می‌گردیم که مورد تهدید وزیران پیشین نباشد. چنین خانه‌ای موجود نیست.
- به ردیف قبل یعنی ردیف سوم باز می‌گردیم تا خانه‌ای دیگر برای وزیر سوم بیابیم. خانه دیگری وجود ندارد.
- به ردیف قبل یعنی ردیف دوم بر می‌گردیم تا خانه دیگری برای وزیر دوم پیدا کنیم. به آخرین ستون رسیده‌ایم و خانه دیگری نیست.
- به ردیف قبل یعنی ردیف اول بر می‌گردیم و وزیر اول را یک ستون به جلو می‌بریم.
http://delphiarea.com/external/8queens/q5.gif
- در ردیف دوم اولین خانه‌ای را میابیم که مورد تهدید وزیر اول نباشد و وزیر دوم را در آن خانه قرار می‌دهیم.
http://delphiarea.com/external/8queens/q6.gif
- در ردیف سوم اولین خانه‌ای را میابیم که مورد تهدید وزیران اول و دوم نباشد و وزیر سوم را در آن خانه می‌گذاریم.
http://delphiarea.com/external/8queens/q7.gif
- در ردیف چهارم اولین خانه‌ای را میابیم که مورد تهدید وزیران پیشین نباشد. این بار خانه را می‌یابیم و وزیر چهارم را در آن خانه قرار می دهیم.
http://delphiarea.com/external/8queens/q8.gif
خوب به یک جواب رسیدیم. حال اگر فرض کنیم که این خانه جواب نیست و به مسیر خود ادامه دهیم، احتمالا" می‌توانیم جوابهای دیگری نیز بیابیم.
در نهایت پیاده سازی الگوریتم مسئله هشت وزیر با روش برگشت به عقب بصورت زیر خواهد بود:
procedure ListEightQueenPositions;
var
Queens: array[1..8] of Integer; (* Holds the column number of each queen *)
NumPos: Integer;
Q, N: Integer;
SafePos: Boolean;
begin
(* Set position of all queens to undefined *)
for Q := 1 to 8 do
Queens[Q] := 0;
(* Set the number of found positions to zero *)
NumPos := 0;
(* Start by positioning the first queen *)
Q := 1;
(* While there's any possible position *)
while (Q <> 1) or (Queens[1] <> 8) do
begin
SafePos := False;
(* while a non-conflict position for the current queen has not found *)
while (Queens[Q] < 8) and not SafePos do
begin
(* Advance one colume the position of the queen *)
Queens[Q] := Queens[Q] + 1;
(* Check whether this column has any confilict with the the other queens *)
SafePos := True;
N := 1;
while (N < Q) and SafePos do
begin
(* Two queens are not in confilict with each other when *)
SafePos :=
(* They are not on the same column, and *)
(Queens[N] <> Queens[Q]) and
(* They are not on the same oblique line *)
(Abs(Queens[N] - Queens[Q]) <> Abs(N - Q));
(* Check with another queen *)
N := N + 1;
end;
end;
(* If there was a non-coflict position for the current queen *)
if SafePos then
begin
(* If it is the last queen *)
if Q = 8 then
begin
(* Increase the number of found positions by one *)
NumPos := NumPos + 1;
(* Print out the position of queens *)
Write(NumPos:2, ' -> ');
for N := 1 to 8 do
Write('(', N:1, ',', Queens[N]:1, ') ');
Writeln;
end
else
begin
(* Continue with the next queen *)
Q := Q + 1;
end;
end
else
begin
(* Set the position of the current queen undefined *)
Queens[Q] := 0;
(* Reposition the previous queen *)
Q := Q - 1;
end;
end;
end;
نقل قول: تکنیکهای طراحی الگوریتم - روش بازگشت به عقب
سلام
دوست گرامی درک مسئله N وزیر به صورت سه بعدی یعنی ( N*N*N )چگونه است من که نفهمیدم
با تشکر از شما
