الگوریتم جست وجوی محلی در CSPها
الگوریتم جست وجوی محلی در CSPها
الگوریتم های جست وجوی محلی در حل بسیاری از CSPها به کار میروند. این الگوریتم ها از فرموله کردن "حالت کامل" استفاده میکنند، بطوریکه حالت شروع، مقداری را به هر متغیر نسبت میدهد و جست وجو هر بار مقدار یک متغیر را تغییر میدهد. مثلا در مسئله هشت وزیر، حالت شروع ممکن است یک پیکربندی تصادفی از هشت وزیر در هشت ستون باشد، و هر مرحله یک وزیر را به موقعیت جدیدی در آن ستون حرکت میدهد. معمولا حدس اولیه، چندین محدودیت را نقض میکند. امتیاز جست وجوی محلی، حذف محدودیت های نقض شده است.
در انتخاب مقدار جدید برای متغیر، بدیهی ترین ابتکار، انتخاب مقداری است که کمترین تعداد تناقض ها را با متغیرهای دیگر داشته باشد. این ابتکار به نام کمترین تناقض ها خوانده میشود. این الگوریتم را در ادامه خواهیم دید.
روش کمترین تناقض ها برای بسیاری از CSP ها بطور کارآمد عمل میکند. در مسئله n وزیر اگر محل اولیه وزیرها را در نظر بگیرید، زمان اجرای روش کمترین تناقض ها، مستقل از اندازه مسئله است. این روش، حتی مسئله یک میلیون وزیر را بطور میانگین در 50 مرحله حل میکند (پس از انتساب اولیه). این مشاهده قابل توجه به تحقیقات زیادی در دهه 1990 بر روی جست وجوی محلی و توزیع بین مسئله های آسان و سخت شد. بعبارت ساده تر مسئله n وزیر به راحتی به روش کمترین تناقض ها حل میشود، زیرا جوابها بطور متراکم در سراسر فضای حالت توزیع شده اند. روش کمترین تناقض ها برای مسئله های سخت نیز به خوبی کار میکند. برای مثال، برای زمانبندی مشاهدات "تلسکوپ فضایی هابل" به کار رفت، بطوریکه زمان لازم برای برنامه ریزی را از سه هفته به 10 دقیقه کاهش داد.
تمام تکنیکهای جست وجوی محلی کاندیدای به کار گیری در CSP ها هستند و اثبات شده است که بعضی از آنها کارآمد هستند. دورنمای CSP تحت ابتکارات تناقض ها، مجموعه ای از فلات ها است. میلیونها انتساب به متغیرها وجود دارند که فقط یک تناقض با جواب فاصله دارند. جست وجوی فلاتها (اجازه ی حرکتهای جنبی به حالت دیگری با همان امتیاز)، به جست وجوی محلی کمک میکند تا راهش را پیدا کند. این نگرانی در مورد فلاتها میتواند با جست وجوی تابو حل شود، بطوریکه لیست کوچکی از حالتهایی که اخیرا بازدید شده اند نگهداری شود و اجازه ندهیم الگوریتم به پان حالتها برگردد. الگوریتم simulated annealing نیز میتواند برای فرار از فلات به کار رود.
تکنیک های دیگری به نام وزن دادن به محدودیت ها میتواند به جست وجو کمک کند تا بر محدودیت های مهم متمرکز شود. برای هر محدودیت یک وزن عددی تعیین میشود که در آغاز برای هر محدودیت برابر 1 است. در هر مرحله از جست وجو ، الگوریتم جفت "متغیر/ مقدار" را انتخاب میکند و آن را تغییر میدهد تا از بین تمام محدودیت های نقض شده، کل وزن آن کمترین است. سپس وزنها تنظیم میشوند. برای این کار وزن هر محدودیتی که توسط انتساب فعلی نقض شد، اضافه میشود. این کار دو فایده دارد: توپوگرافی را به فلات اضافه میکند، بطوریکه تضمین میکند از حالت فعلی بهبود یابد، و با مرور زمان، وزن محدودیت هایی را که حل آنها دشوار است، اضافه میکند.
امتیاز دیگر جست وجوی محلی این است که میتواند در صورت تغییر مسئله، تنظیمات آنلاین را انجام دهد. این موضوع در مسئله های زمانبندی مهم است. علاقه مند هستیم زمانبندی را با کمترین تغییر ترمیم کنیم. برای این کار میتوان از الگوریتم جست وجوی محلی و با شروع از زمانبندی فعلی استفاده کرد. جست وجوی عقبگرد با مجموعه جدیدی از محدودیتها، معمولا به زمان زیادی نیاز دارد و ممکن است با انجام تغییرات زیادی در حالت فعلی، جوابی را بیابد.
شبه کد الگوریتم جست وجوی محلی در CSPها
function MIN-CONFLICTS (csp, max_steps) returns a solution or failure
inputs : csp, a constraint satisfaction problem
max_steps, the number of steps allowed before giving up
current <-- an initial complete assignment for csp
for i = 1 to max_steps do
if current is a solution for csp then return current
var <-- a randomly chosen con flicted variable from csp.VARIABLES
value <-- the value v for var that minimizes CONFLICTS (var, v, current, csp)
set var = value in current
return failure
