الگوریتم جست وجوی محلی WALKSAT
الگوریتم جست وجوی محلی WALKSAT
الگوریتم WALKSAT خانواده ای از الگوریتم های کارآمد در استنتاج گزاره ای مبتنی بر بازرسی مدل است که به جست وجوی تپه نوردی مربوط میشود و بخشی از "فناوری" منطق گزاره ای می باشد.
الگوریتم های جست وجوی محلی مستقیما میتوانند به مسئله های ارضا شدنی اعمال شوند، به شرطی که تابع ارزیابی مناسبی را انتخاب کنیم. چون هدف یافتن تناسبی است که هر کلاز را ارضا کند، تابع ارزیابی ای که تعداد کلازهای ارضا نشده را میشمارد، این کار را انجام میدهد. در واقع این معیار توسط الگوریتم MIN – CONFLICTS برای CSP ها بکار رفته است. تمام این الگوریتم ها در فضای انتساب های کامل گام برمیدارند و در هر زمان، "مقدار درستی" یک نماد را معکوس میکند. این فضا معمولا شامل چندین مینیمم محلی برای فرار از شکل های گوناگونی از تصادفی سازی های مورد نیاز است. در سالهای اخیر، آزمایش های زیادی برای یافتن توازن خوبی برای "تصادفی سازی" و "حریص بودن" انجام شده است.
یکی از ساده ترین و کارآمدترین الگوریتم ها WALKSAT است که شبه کد آن را نیز در ادامه خواهید دید. در هر تکرار، الگوریتم یک کلاز ارضا نشده را انتخاب میکند و نمادی را از کلاز انتخاب میکند تا تغییر دهد.
بطور تصادفی یکی از روشها را برای انتخاب نماد جهت تغییر برمیگزیند: (1) مرحله "کمترین تناقض" که تعداد کلازهای ارضا نشده در حالت جدید را مینیمم میکند. (2) مرحله "پیمایش تصادفی" که نماد را بطور تصادفی انتخاب میکند.
وقتی WALKSAT مدلی را برمی گرداند، جمله ورودی ارضاپذیری است، اما وقتی failure را برمیگرداند دو علت ممکن وجود دارد : یا جمله ارضانشدنی است یا باید زمان بیشتری به الگوریتم بدهیم. اگر قرار دهیم max_flips = ∞ و p>0 ، آنگاه WALKSAT سرانجام یک مدل را برمیگرداند (در صورت وجود) ، زیرا مراحل پیمایش تصادفی سرانجام منجر به جواب میشوند. اگر max_flips بی نهایت و جمله ارضاناپذیر باشد، آنگاه الگوریتم هرگز خاتمه نمی یابد.
به همین دلیل ، وقتی انتظار داریم جوابی وجود داشته باشد، WALKSAT مفیدتر خواهد بود. از طرف دیگر WALKSAT همیشه نمیتواند ارضاپذیری را تشخیص دهد، که برای تصمیم گیری راجع به ایجاب منطقی ضروری است.
شبه کد الگوریتم WALKSAT
function WALKSAT(clauses, p , max_flips) returns a satisfying or failure
inputs: clauses, a set of clauses in propositional logic
p, the probability of choosing to do a “random walk” move, typically around 0.5
max_flips, number of flips allowed before giving up
model <-- a random assignment of truel false to the symbols in clauses
for i = 1 to max_flips do
if model satisfies clauses then return model
clause <-- a randomly selected clause from clauses that is false in model
with probability p flip the value in model of a randomly selected symbol from clause
else flip whichever symbol in clause maximizes the number of satisfied clauses
return failure
سلام ممنون از توضیح خوبتون..میشه لطفا یه مثال هم ازش بگذارید؟متشکرم