Kambiz
یک شنبه 04 آبان 1382, 03:58 صبح
موضوعات مرتبط:
تحلیل مقدماتی الگوریتمها (http://www.barnamenevis.org/forum/viewtopic.php?t=2909)
تکنیکهای طراحی الگوریتم - مقدمه (http://www.barnamenevis.org/forum/viewtopic.php?t=2796)
تکنیکهای طراحی الگوریتم - روش تقسیم و تسخیر (http://www.barnamenevis.org/forum/viewtopic.php?t=2874)
تکنیکهای طراحی الگوریتم - روش برنامه نویسی پویا (http://www.barnamenevis.org/forum/viewtopic.php?t=3563)
تکنیکهای طراحی الگوریتم - روش سیری ناپذیر (http://www.barnamenevis.org/forum/viewtopic.php?t=3807)_____________________________ __________________________________________
فرض کنید که در محله‌ای به دنبال یک کتاب فروشی خاص می‌گردیم. این کتاب فروشی در کوچه‌ای قرار دارد که نبش آن یک خواربار فروشی است و همچنین در ابتدای خیابانی که این کوچه قرار دارد یک مدرسه هست.
کاری که برای یافتن این کتاب فروشی می‌کنیم این است که در این محله ابتدا به دنبال آن خیابان فرعی می‌گردیم که در ابتدای آن یک مدرسه قرار دارد. سپس در این خیابان به دنبال کوچه‌ای می‌گردیم که یک خواربار فروشی در نبش آن است. هنگامی که کوچه را یافتیم، اگر در آن کتاب فروشی بود به جواب رسیده‌ایم وگرنه به خیابان فرعی برگشته و به دنبال کوچه‌ای دیگر می‌گردیم که یک خواربار فروشی در نبش آن باشد. اگر در این خیابان چنین کوچه‌ای وجود نداشت به خیابان اصلی برگشته و جستجوی خود را با یافتن خیابان فرعی دیگری با یک مدرسه در آن دنبال می کنیم.
روالی که برای یافتن جواب در مثال بالا دنبال شد، روش بازگشت به عقب (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;
تحلیل مقدماتی الگوریتمها (http://www.barnamenevis.org/forum/viewtopic.php?t=2909)
تکنیکهای طراحی الگوریتم - مقدمه (http://www.barnamenevis.org/forum/viewtopic.php?t=2796)
تکنیکهای طراحی الگوریتم - روش تقسیم و تسخیر (http://www.barnamenevis.org/forum/viewtopic.php?t=2874)
تکنیکهای طراحی الگوریتم - روش برنامه نویسی پویا (http://www.barnamenevis.org/forum/viewtopic.php?t=3563)
تکنیکهای طراحی الگوریتم - روش سیری ناپذیر (http://www.barnamenevis.org/forum/viewtopic.php?t=3807)_____________________________ __________________________________________
فرض کنید که در محله‌ای به دنبال یک کتاب فروشی خاص می‌گردیم. این کتاب فروشی در کوچه‌ای قرار دارد که نبش آن یک خواربار فروشی است و همچنین در ابتدای خیابانی که این کوچه قرار دارد یک مدرسه هست.
کاری که برای یافتن این کتاب فروشی می‌کنیم این است که در این محله ابتدا به دنبال آن خیابان فرعی می‌گردیم که در ابتدای آن یک مدرسه قرار دارد. سپس در این خیابان به دنبال کوچه‌ای می‌گردیم که یک خواربار فروشی در نبش آن است. هنگامی که کوچه را یافتیم، اگر در آن کتاب فروشی بود به جواب رسیده‌ایم وگرنه به خیابان فرعی برگشته و به دنبال کوچه‌ای دیگر می‌گردیم که یک خواربار فروشی در نبش آن باشد. اگر در این خیابان چنین کوچه‌ای وجود نداشت به خیابان اصلی برگشته و جستجوی خود را با یافتن خیابان فرعی دیگری با یک مدرسه در آن دنبال می کنیم.
روالی که برای یافتن جواب در مثال بالا دنبال شد، روش بازگشت به عقب (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;