ورود به حساب ثبت نام جدید فراموشی کلمه عبور
برای ورود به حساب کاربری خود، نام کاربری و کلمه عبورتان را در زیر وارد کرده و روی “ ورود به حساب” کلیک کنید.





اگر فرم ثبت نام برای شما نمایش داده نمیشود، اینجا را کلیک کنید.









اگر فرم بازیابی کلمه عبور برای شما نمایش داده نمیشود، اینجا را کلیک کنید.





نمایش نتایج: از 1 به 1 از 1
  1. #1
    sina
    sina
    Guest

    تکنیکهای طراحی الگوریتم - روش بازگشت به عقب

    فرض کنید که در محله*ای به دنبال یک کتاب فروشی خاص می*گردیم. این کتاب فروشی در کوچه*ای قرار دارد که نبش آن یک خواربار فروشی است و همچنین در ابتدای خیابانی که این کوچه قرار دارد یک مدرسه هست.

    کاری که برای یافتن این کتاب فروشی می*کنیم این است که در این محله ابتدا به دنبال آن خیابان فرعی می*گردیم که در ابتدای آن یک مدرسه قرار دارد. سپس در این خیابان به دنبال کوچه*ای می*گردیم که یک خواربار فروشی در نبش آن است. هنگامی که کوچه را یافتیم، اگر در آن کتاب فروشی بود به جواب رسیده*ایم وگرنه به خیابان فرعی برگشته و به دنبال کوچه*ای دیگر می*گردیم که یک خواربار فروشی در نبش آن باشد. اگر در این خیابان چنین کوچه*ای وجود نداشت به خیابان اصلی برگشته و جستجوی خود را با یافتن خیابان فرعی دیگری با یک مدرسه در آن دنبال می کنیم.

    روالی که برای یافتن جواب در مثال بالا دنبال شد، روش بازگشت به عقب (Backtracking) نام دارد. در این روش همانطور که در مثال مشاهده کردید، در هر زمان که متوجه شدیم مسیر انتخاب شده به جواب نمی*رسد، یک مرحله به عقب برگشته و مسیر دیگری را دنبال می کنیم.

    روش بازگشت به عقب برای آن دسته از مسائلی قابل استفاده است که برای رسیدن به جواب بتوان یک جستجوی سیستماتیک را دنبال کرد. به عنوان نمونه می*توان بهره*گیری از این روش را در بازیهای کامپیوتری، سیستمهای اثبات تئوریها، شبکه*های مفهومی، هایپرتکس و ... دید.


    مثال:

    چگونه هشت وزیر را بر روی صفحه شطرنج قرار دهیم به گونه*ای که هیچ یک از آنها مورد تهدید دیگری قرار نگیرد؟

    می*دانیم که در شطرنج یک وزیر می*تواند به مهره*هایی که در خانه*های عمود یا مورب به وی قرار دارند حمله کند. یا به عبارت ریاضی، اگر ردیفها و ستونهای شطرنج را از یک تا هشت شماره گذاری کنیم و وزیر در خانه (i, j) قرار داشته باشد، مهره*هایی که در خانه*های (i, m) یا (m, j) یا (i ± m, j ± m) قرار دارند توسط وزیر تهدید می*شوند.


    [برای نمایش لینک باید عضو شوید. ]


    برای سادگی تشریح این مسئله با استفاده از روش بازگشت به عقب، فرض می*کنیم که خانه*های شطرنج 4x4 و تعداد وزیرها نیز 4 باشد. سپس بعد از یافتن راه حل برای این مسئله ساده شده، اقدام به نوشتن الگوریتم برای مسئله اصلی می*کنیم.

    خوب، مراحل جستجو برای یافتن جواب را به این صورت دنبال می کنیم که:

    وزیر اول را در ردیف اول و ستون اول قرار می*دهیم.


    در ردیف دوم از اولین ستون به جلو رفته و به دنبال خانه*ای می*گردیم که مورد تهدید وزیر اول نباشد و وزیر دوم را در این خانه قرار می*دهیم.


    همانند قبل، در ردیف سوم از اولین ستون به جلو رفته و به دنبال خانه*ای می*گردیم که مورد تهدید وزیران اول و دوم نباشد. می*بینیم که چنین خانه*ای موجود نیست.
    پس به عقب یعنی ردیف دوم برگشته و وزیر دوم را به خانه*ای دیگر از ردیف دوم منتقل می*کنیم که مورد تهدید وزیر اول نباشد.


    دوباره در ردیف سوم اولین خانه*ای را میابیم که مورد تهدید دو وزیر قبلی نباشد. این بار خانه را می*یابیم و وزیر سوم را در آن قرار می*دهیم.


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


    در ردیف دوم اولین خانه*ای را میابیم که مورد تهدید وزیر اول نباشد و وزیر دوم را در آن خانه قرار می*دهیم.


    در ردیف سوم اولین خانه*ای را میابیم که مورد تهدید وزیران اول و دوم نباشد و وزیر سوم را در آن خانه می*گذاریم.


    در ردیف چهارم اولین خانه*ای را میابیم که مورد تهدید وزیران پیشین نباشد. این بار خانه را می*یابیم و وزیر چهارم را در آن خانه قرار می دهیم.


    خوب به یک جواب رسیدیم. حال اگر فرض کنیم که این خانه جواب نیست و به مسیر خود ادامه دهیم، احتمالا" می*توانیم جوابهای دیگری نیز بیابیم.

    در نهایت پیاده سازی الگوریتم مسئله هشت وزیر با روش برگشت به عقب بصورت زیر خواهد بود:




    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;
  2. 1
نمایش نتایج: از 1 به 1 از 1

اطلاعات موضوع

کاربرانی که در حال مشاهده این موضوع هستند

در حال حاضر 1 کاربر در حال مشاهده این موضوع است. (0 کاربران و 1 مهمان ها)

کلمات کلیدی این موضوع

مجوز های ارسال و ویرایش

  • شما نمیتوانید موضوع جدیدی ارسال کنید
  • شما امکان ارسال پاسخ را ندارید
  • شما نمیتوانید فایل پیوست کنید.
  • شما نمیتوانید پست های خود را ویرایش کنید
  •  

Content Relevant URLs by vBSEO 3.6.0 RC 2