روش پس‌گرد

روش پس‌گرد

روش پس‌گرد (Back traking)

از روش پس‌گرد براي حل مسائلي استفاده مي‌شود كه در آن‌ها يك دنباله از اشياء با شرايط داده شده بايد از يك مجموعهء مشخص انتخاب شود. يك مثال كلاسيك از اين روش، مسالهء n وزير (n-queen problem) مي‌باشد. هدف از اين مسأله قرار دادن n مهرهء وزير در يك صفحه شطرنجي n  nبه گونه‌اي است كه هيچ دو وزير همديگر را نزنند (تهدید نکنند). به عبارت دقيق‌تر، دو مهره وزير هيچگاه نبايد در يك سطر، ستون يا قطر چيده شوند. در اين مسأله، دنباله عبارت است از n مكاني كه در آن‌ها بايد مهره وزير‌ها قرار داده شوند. مجموعه براي هر انتخاب، 2n موقعيت روي صفحه شطرنج و شرط داده شده اين است كه هيچ دو وزيري، همديگر را نزنند.

در تمامي مسائل اين فصل، درخت فضاي حالت تعداد نمايي از گره‌ها را شامل مي‌شود و از روش پس‌گرد جهت پرهيز از چك‌كردن بيهوده گره‌ها استفاده مي‌شود.

روش پس‌گرد، حالت اصلاح شده جستجوي در عمق يك درخت است و جستجوي در عمق يك درخت، پيمايش پيش ترتيب آن درخت مي‌باشد، به اين معنا كه در ابتدا ريشه درخت و سپس همه فرزندانش ملاقات مي‌شوند كه عموماً فرزندان يك گره از چپ به راست ملاقات مي‌شوند. در جستجو در عمق يك مسير را آنقدر در عمق پيش مي‌رويم تا به بن‌بست برسيم. در بن‌بست، دوباره آنقدر به عقب بر مي‌گرديم تا به يك گره با يك فرزند ملاقات نشده برسيم. سپس، از اين فرزند ملاقات نشده، پيشروي در عمق را مجدداً تا رسيدن به بن‌بست ديگر ادامه مي‌دهيم.

شكل 1- جستجو در عمق يك درخت را نشان مي دهد. گره‌ها به‌ترتيب ملاقات شدن، شماره‌گذاري شده‌اند.

6-1- مسأله n وزير

مسأله n وزير، صورت عمومي مسأله 8- وزير است كه در آن از صفحه شطرنجي استاندارد استفاده مي‌شود. روش پس گرد را با نمونه‌اي از مسأله n وزير كه در آن 4 = n است، نشان مي دهيم. هدف قرار دادن چهار وزير بر روي يك صفحهء شطرنجي  4  4  است به گونه‌اي كه هيچ دو وزيري همديگر را نزنند.

مي‌توانيم با نسبت دادن هر وزير به يك سطر متفاوت و بررسي اين كه چه تركيبي از ستون‌ها جواب است مسأله را حل كنيم. با توجه به اينكه هر وزير را مي‌توان در يكي از چهار ستون قرار داد، تعداد جوابهاي ممكن 256 = 4  4  4  4 مي‌باشد.

درخت فضاي حالت را براي اين مسأله تشكيل مي‌دهيم، بدين ترتيب كه با تشكيل درختي كه در آن انتخابهاي ستون براي وزير سطر اول در گره‌هاي سطح 1 درخت و انتخاب هاي ستون براي وزير سطر دوم در گره‌هاي سطح 2 و به همين ترتيب تا به آخر، نگهداري مي‌شوند، مي‌توان جواب‌هاي ممكن را توليد كرد و از آنجايي كه يك مسير از ريشه به برگ، يك جواب ممكن است و كل درخت 256 برگ دارد: هر كدام مربوط به يك جواب ممكن است.

شكل 2- بخشي از درخت فضاي حالت براي مسأله 4- وزير

هر زوج مرتب <i,j> به اين معناست كه وزير i ام در ستون j ام قرار داده شده است.

هر يك از مسيرها از ريشه به برگ يك جواب ممكن براي مسأله است. مانند مسيرهاي زير:

[<1, 1> , <2, 1>, <3, 1>, <4, 1>]

[<1, 1> , <2, 1>, <3, 1>, <4, 2>]

[<1, 1> , <2, 1>, <3, 1>, <4, 3>]

[<1, 1> , <2, 1>, <3, 2>, <4, 1>]

با توجه به اينكه هيچ دو وزيري نمي‌توانند در يك ستون قرار بگيرند زير شاخه‌هاي گره <2,1> را بررسي نمي‌كنيم زيرا وزير 1 را قبلاً در ستون 1 قرار داده­ايم و ديگر نمي‌توانيم وزير 2 را در آن ستون قرار دهيم. بنابراين اين گره به بن‌بست ختم مي‌شود.

همچنين هيچ دو وزيري نمي‌توانند برروي يك قطر قرار بگيرند بنابراين زير شاخه‌هاي گره <2,2> را بررسي نمي‌كنيم.

اگر هنگام ملاقات كردن و بررسي گره مشخص شود كه اين گره احتمالاً منجربه يك جواب نمي‌شود و منجر به بن‌بست مي‌شود آن را غیراميدبخش و در غير اين صورت، آن را اميد بخش گوييم. بنابراين روش پس‌گرد روشي است كه در درخت فضاي حالت جستجوي عمقي انجام مي دهيم و اميدبخش بودن يا نبودن هر گره را بررسي مي­كنيم در صورتي كه گره‌اي اميدبخش نباشد به گره پدر بازگشته و جستجو را با همين روش با ديگر فرزندان ادامه مي‌دهيم. اين عمليات هرس كردن درخت فضاي حالت ناميده مي‌شود.

الگوريتم عمومي براي روش پسگرد به صورت زير مي‌باشد:

Algorithm checknode (v)

{

If (promising (v)) then

     If (there is a solution at v) then

     Write the solution ;

else

For (each child u of v)

Checknode (u) ;

}

اگر گره‌اي اميدبخش بوده و جوابي در آن وجود داشته باشد، آن جواب چاپ مي‌شود و اگر جوابي در يك گره اميدبخش وجود نداشته باشد فرزندان آن گره ملاقات مي­شوند.

الگوريتم پس‌گرد مانند جستجو در عمق است، با اين تفاوت كه فرزندان يك گره فقط هنگامي ملاقات مي‌شوند كه آن گره اميدبخش بوده و جوابي در آن وجود نداشته باشد.

الگوريتم پس‌گرد مذكور به جاي checknode , back track ناميده مي­شود زيرا موقع فراخواني آن، عمل پس‌گرد انجام نمي‌شود و اين عمل زماني رخ مي‌دهد كه گره‌اي اميد بخش نباشد كه در اينصورت كار با فرزندان بعدي گره پدر ادامه مي‌دهيم.

در شكل زير بخشي از درخت فضاي حالت هرس شده توسط روش پس‌گرد براي حل مسأله 4- وزير ارائه شده است، كه فقط گره‌هاي بررسي شده براي رسيدن به اولين جواب نشان داده شده‌اند و گره سايه‌دار شامل اولين حل مي‌باشد. گره‌هاي غیراميدبخش با علامت  مشخص شده‌اند و گره‌هاي اميدبخش علامت  ندارند.

(شكل3)

شكل بالا نشان مي‌دهد الگوريتم پس‌گرد براي رسيدن به اولين جواب، 27 گره را بررسي مي‌كند. در حالي كه بدون استفاده از روش پس‌گرد، جستجوي در عمق درخت فضاي حالت، مستلزم بررسي 155 گره، براي رسيدن به همان جواب خواهد بود.

بررسي‌هاي مذكور در صفحه شطرنج  4  4  در شكل‌هاي وزير نشان داده شده است:

 

 

 

Д

 

 

 

 

Д

 

 

 

 

Д

 

Д

 

 

 

 

Д

Д

Д

 

 

 

 

 

Д

Д

Д

Д

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

                (3)                                                  (2)                                    (1)

 

 

 

 

Д

 

 

 

 

Д

 

 

 

 

Д

Д

 

 

 

 

Д

 

 

 

 

Д

 

 

 

 

 

Д

 

 

 

 

Д

Д

 

 

 

 

 

Д

Д

Д

Д

 

 

 

 

 

 

 

 

 

 

                (6)                                                 (5)                                                   (4)

 

 

 

Д

 

 

 

 

Д

 

 

 

 

 

Д

Д

Д

Д

Д

 

 

 

 

 

 

Д

 

 

 

 

 

 

 

 

 

 

 

 

 

Д

Д

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

(9)                                                 (8)                                                   (7)

 

 

 

Д

 

 

 

 

 

 

 

 

 

Д

 

Д

 

 

 

 

 

 

 

 

 

Д

 

 

 

 

 

 

Д

 

 

 

 

 

 

 

 

 

Д

Д

Д

Д

 

 

 

 

 

 

 

 

 

 

(11)                                                                                                        (10)

پياده سازي مسأله n وزير

تابع اميد بخش بايد بررسي كند كه آيا دو وزير در يك ستون يا در يك قطر واقع شده‌اند يا خير. اگر col(i) معرف ستوني باشد كه وزير سطر i ام در آن قرار مي‌گيرد، در اين صورت براي تعيين اينكه آيا با وزير سطر k ام در يك ستون است يا نه، بايد مقايسه              col(i) = col (k) را انجام دهيم. يعني اگر شرط) col(i) = = col (k) if ( برقرار باشد، غيرمجاز است.

براي بررسي هم قطر بودن، وزيرها، به شكل زير توجه كنيد كه نمونه‌ n = 8 را نشان مي‌دهد در اين شكل، وزير سطر 6 در قطر چپ، وزير سطر 3 را مي‌زند.

Col (6) – col (3) = 4-1 = 3 = 6-3

وزير سطر 6 در قطر راست، وزير سطر 2 را مي‌زند

Col (6) – col (2) = 4-8 = –4 = 2-6

پس وزير در سطر i ام به شرطي وزير در سطر k ام را مي‌زند كه شرط زير برقرار باشد.

If ((col [i] – col [k] = = i – k) OR ((col [i] – col [k] = = k – i))

شرط فوق را با توجه به امكان منفي شدن پاسخ به كمك تابع قدر مطلق بصورت زير مي‌توان نوشت:

If (abs (col [i] – col [k] = = i – k))

8

7

6

5

4

3

2

1

1

Д

2

Д

3

4

5

Д

6

7

8

الگوريتم پس‌گرد براي مسأله n وزير را مي‌توان بصورت زير نوشت :

Void queens (index i)

{

Index  j ;

If (promising (i))

     If (i = = n)

     Cout << col [1] through col [n];

Else

      For (j = i ; 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 ;

}

 

نكاتي مربوط به الگوريتم فوق :

1-   ورودي اين الگوريتم عدد صحيح و مثبت n است.

2-   خروجي اين الگوريتم، همه راه‌هاي ممكن جهت قرار دادن n وزير در صفحه شطرنج n  nاست به گونه‌اي كه هيچ دو وزيري يكديگر را نزنند.

هر خروجي آرايه از اعداد صحيح به نام col است كه انديس‌هاي اين آرايه از 1 تا n بوده و col [i] نمايانگر ستوني است كه وزير سطر i ام در آن قرار مي‌گيرد.

3-   الگوريتم فوق در بالاترين سطح به صورت queens(0) صدا زده مي‌شود و خروجي اين الگوريتم براي 4 = n به صورت زير مي‌باشد

3       1       4       2

2       4       1       3

4- تحليل الگوريتم n وزير

تحليل اين الگوريتم كاري بسيار دشوار است و براي آن بايد تعداد گره‌هاي بررسي شده را برحسب تابعي از n بدست آوريم

تذكر: در بدترين حالت ممكن، تمام گره‌ها بررسي مي‌شوند. كه در اين حالت درخت فضاي حالت در سطح 0 شامل 1 گره ، در سطح شماره 1 شامل n گره، در سطح شماره 2 شامل n2 و بدين‌ترتيب ادامه پيدا مي‌كند.

تعداد كل گره‌ها = 1 + n + n2 + n3 + … + nn =  = q (nn)

هدف در الگوريتم پس‌گرد اين است كه از بررسي كردن بسياري از گره‌ها خودداري كنيم در حالي كه در اين حالت، تمامي گره‌ها بررسي مي‌شود، گويي كه كل درخت فضاي حالت را جستجوي عمقي كرده بدون اينكه از روش پس‌گرد استفاده شود. بنابراين تحليل بالا ارزش چنداني ندارد.

روش انشعاب و تحديد

در اين روش نيز از باز كردن برخي از شاخه­ها خودداري مي‌كنيم. در اين روش با دانستن يك سري اطلاعات در مورد مسأله و شرايط عملي مشخص مي شود كه از اين شاخه نتيجه مطلوبي بدست نمي‌آيد. لذا از باز كردن آن صرف‌نظر مي‌كنيم و نيز مي‌توان با توجه به همين اطلاعات تصميم گرفت كه ابتدا كداميك از شاخه‌هاي درخت را مورد جستجو قرار دهيم به عبارت دقيق‌تر، اين روش مشابه روش پس‌گرد است كه از درخت فضاي حالت براي حل مسائل استفاده مي‌كند و تنها دو تفاوت بين اين دو روش وجود دارد. در روش انشعاب و تحديد محدوديتي براي استفاده از روش خاص براي پيمايش درخت فضاي حالت وجود ندارد و فقط براي مسائل بهينه استفاده مي شود. در يك الگوريتم انشعاب و تحديد، براي هر گره، عددي براي تعيين اميدبخش بودن آن محاسبه مي‌گردد. اين عدد، كرانه براي جوابي است كه در صورت توسعه گره مربوطه مي‌توان به آن رسيد. اگر اين كرانه، بهتر از مقدار بهترين جواب حاصل تاكنون نباشد در اين صورت، گره غیراميدبخش و در غير اينصورت، اميدبخش است.

 

۱۳۹۲-۸-۵ ۰۰:۲۳:۰۶ +۰۳:۳۰آبان ۵ام, ۱۳۹۲|Categories: مهندسی نرم افزار, هوش مصنوعی|بدون ديدگاه

ثبت ديدگاه

پرداخت

1-پرداخت آنلاین
برای پرداخت آنلاین از لینک زیر استفاده کنید
پرداخت آنلاین
2- پرداخت آفلاین
برای پرداخت آفلاین مبلغ مورد نظر را به یکی از شماره کارت
6037997245888723بانک ملی