الگوریتم جست وجوی عقبگرد در CSPها
الگوریتم جست وجوی عقبگرد در CSPها
مسئله های سودوکو طراحی شدند تا از طریق استنتاج روی محدودیت ها حل شوند. اما بسیاری از CSPهای دیگر نمیتوانند تنها با استنتاج حل شوند. مثلا وقتی نیاز به جست وجو باشد، استنتاج کارایی ندارد.
میتوانستیم جست وجوی با "عمق محدود استاندارد" را اجرا کنیم. هر حالت بعنوان یک انتساب جزیی است و هر فعالیت با انتساب var = value به این انتساب، مشخص میشود. اما برای CSP با n متغیر و با دامنه به اندازه d سریعا متوجه مشکلاتی میشویم. ضریب انشعاب بالا برابر با nd است، زیرا هر مقدار d میتواند به هر n متغیر نسبت داده شود. در سطح بعدی ضریب انشعاب (n-1)d است و برای n سطح همین طور ادامه دارد. در ختی با n! . dn برگ ایجاد میکنیم، گرچه فقط dn "انتساب کامل" وجود دارد.
در این روش فرموله کردن مسئله، یکی از خواص مهم مشترک تمام CSPها به نام جابه جایی پذیری را نادیده گرفتیم. مسئله در صورتی جابه جایی پذیر است که ترتیب اجرای هر مجموعه ای از فعالیت ها تاثیری در نتیجه نهایی نداشته باشد. CSPها جابه جا پذیر هستند، زیرا هنگام انتساب مقادیر به متغیرها، صرفنظر از ترتیب آنها به انتساب جزیی یکسانی میرسیم. بنابراین فقط لازم است یک متغیر در هر گره در درخت جست وجو را در نظر بگیریم.
اصطلاح جست وجوی عقبگرد، برای جست وجوی عمقی ای به کار میرود که هر بار مقادیری را برای یک متغیر انتخاب میکند و وقتی مقدار معتبری برای انتساب به متغیر وجود نداشته باشد، به عقب برمیگردد (عقبگرد میکند). شبه کد الگوریتم جست وجوی عقبگرد را در ادامه خواهید دید. در این الگوریتم به طور مکرر یک متغیر بدون مقدار را انتخاب میکند و سپس تمام مقادیر موجود در دامنه ی آن متغیر را به نوبت بررسی میکند تا جوابی را پیدا کند. وقتی یک ناسازگاری پیدا شود، تابع BACKTRACK خطایی را برمیگرداند، و موجب میشود فراخوانی قبلی، مقدار دیگری را بررسی کند. چون نمایش CSP ها استاندارد شده است، لازم نیست برای BACKTRACKING-SEARCH یک تابع فعالیت، مدل گذار (تغییر حالت)، آزمون هدف یا حالت شروع خاص مسئله ایجاد شود. این الگوریتم فقط یک نمایش از حالت را نگه میدارد و به جای ایجاد نمایش جدید، آن نمایش را تغییر میدهد.
شبه کد الگوریتم جست وجوی عقبگرد در CSPها
function BACKTRACKING-SEARCH (csp) returns a solution, or failure
return BACHTRACK ( {} , csp)
function BACHTRACK ( assignment , csp) returns a solution, or failure
if assignment is complete then return assignment
var <-- SELECT- UNASSIGNED- VARIABLE (csp)
for each value in ORDER-DOMAIN-VALUES (var , assignment, csp) do
if values is consistent with assignment then
add { var = values } to assignment
inferences <-- INFERENCE ( csp, var, value )
if inferences ≠ failure then
add inferences to assignment
result <-- BACKTRACK (assignment, csp)
if result ≠ failure then return result
remove { var = values } and inferences from assignment
return failure
