روش عقبگرد ... Operations Research

روش عقبگرد یک الگوریتم عمومی است

 

 

 

روش عقبگرد یک الگوریتم عمومی است برای پیدا کردن همه یا تعدادی از راه حل‌های بعضی از مسائل محاسباتی که راه‌ها را جستجو می‌کند و راه‌هایی را که به جواب منجر نمی‌شود را ترک می‌کند. عمل پیمایش وارونه فقط برای مسأله‌هایی کاربرد دارد که می‌توانند بخشی از مسئله را حل کنند و به سرعت بتوانند امکان رسیدن به جواب معتبر را امتحان کنند.این روش زمانی که قابل اجرا باشد معمولا بسیار سریع تر از روش جستجوی کامل است زیرا می‌تواند تعداد زیادی از زیر مسأله‌ها را با یک امتحان حذف کند.
فهرست مندرجات


    * ۱ توضیح روش
    * ۲ شبه کد
    * ۳ تحلیل
    * ۴ منابع
    * ۵ جستار‌های وابسته

 

الگوریتم پیمایش وارونه مجموعه‌ای از زیر مسئله‌ها را می‌شمارد که می‌توانند از طریق راه‌های مختلف کامل شوند و همهٔ راه حل‌های مسئله داده شده را بدهند.کامل شدن به صورت مرحله‌ای و قدم به قدم انجام می‌گیرد. زیر مسأله‌ها گره‌های یک درخت هستند.فرزند‌های هر گره زیر مسئله‌هایی هستند که یک قدم کامل تر هستند.برگ‌ها زیر مسئله‌هایی هستند که دیگر نمی‌توانند افزایش یابند. الگوریتم پیمایش وارونه این درخت را به صورت بازگشتی با شروع از ریشه به صورت جستوجوی اول عمق جستوجو می‌کند.در هر گره c این الگوریتم امتحان می‌کند که آیا c می‌تواند به صورت یک جواب معتبر کامل شود.اگر نتواند زیر درخت به ریشه c قطع می‌شود.در غیر این صورت امتحان می‌کند که آیا c خودش یک جواب معتبر است.اگر بود آن را به کاربر بر می‌گرداند.سپس به صورت بازگشتی زیر درخت‌های c را پیمایش می‌کند.

 

برای بکار بردن پیمایش وارونه برای دستهٔ خاصی از مسئله‌ها.P را برابر یک نمونه از مسئله که باید حل بشود در نظر می‌گیریم.و ۶ تابع که p را به صورت یک پارامتر می‌گیرند.

   1. (root(P:زیر مسئله ریشه را بر می‌گرداند.
   2. (reject(P,c:اگر c به جواب نرسد درست بر می‌گرداند.
   3. (accept(P,c:اگر c جوابی برای P باشد درست برمی گرداند.
   4. (first(P,c:اولین فرزند c را بر می‌گرداند.
   5. (next(P,s:برادر بعدی s را بر می‌گرداند.
   6. (output(P,c:این تابع c را که جوابی برای P است چاپ می‌کند.

ابتدا ((bt(root(P را صدا می‌زنیم.

‎

 

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)

 

تابع reject باید boolean باشد و زمانی درست برگرداند که مطمئن باشد c به جواب نمی‌رسد.یک درست دادن اشتباه ممکن است باعث شود که bt به برخی از جواب‌ها نرسد.در عین حال کارایی پیمایش وارونه به درست برگرداندن reject برای زیر مسئله‌های نزدیک ریشه بستگی دارد.اگر همواره غلت برگرداند الگوریتم تبدیل به جستوجوی کامل می‌شود. توابع first و next فرزندان زیرمسئله c را پیمایش می‌کند.اگر فرزند مورد نظر نبود این دو تابع باید null برگردانند.

 

    * Gilles Brassard, Paul Bratley (۱۹۹۵). Fundamentals of Algorithmics. Prentice-Hall.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

لطفاً نظرات و پیشنهادات خود را

 

با مدیریت سایت از طریق پست الکترونیکی؛

 

Email: mahdiyarahmadi@gmail.com

 

در میان گذارید.


+ نوشته شده در  ۱۳۸۸/۰۴/۱۳ساعت 17:21  توسط مهدي ياراحمدي خراساني  |