الگوریتم عقبگرد هوشمند در CSPها

الگوریتم عقبگرد هوشمند در CSPها

الگوریتم جست وجوی عقبگرد در (CSP ها) مسائل ارضای محدودیت ،(BACKTRACKING - SEARCH) سیاست ساده ای دارد که مشخص میکند، وقتی شاخه ای،( مسیری) از درخت جست وجو با شکست مواجه شد، چه کاری باید انجام شود. در این روش، الگوریتم به متغیر قبلی برمیگردد و مقدار دیگری را برای آن تست میکند. این روش، عقبگرد به ترتیب زمانی نام دارد، زیرا آخرین تصمیم بازبینی میشود (در مقدار آخرین متغیر بازبینی میکند.)

روش هوشمندتر در عقبگرد این است که آنقدر به عقب برگردیم تا به متغیری برسیم که مسئله را حل کند، یعنی به متغیری برسیم که مسئولیتش این است که یکی از مقادیر ممکن دامنه را غیرممکن سازد. برای این کار مجموعه ای از انتسابها را نگهداری میکنیم که با مقدار تناقض دارد. روش پرش به عقب، به آخرین انتساب در مجموعه ی تناقض برمیگردد.

این روش با تغییر در BACKTRACK به آسانی پیاده سازی میشود، بطوریکه مجموعه ی تناقض را جمع آوری میکند تا بررسی لازم برای مقدار معتبری که باید به متغیر نسبت داده شود، صورت گیرد. اگر هیچ مقدار معتبری پیدا نشود، الگوریتم باید آخرین عنصر مجموعه تناقض را به همراه نشانه شکست برگرداند.

توجه داشته باشید که بررسی پیشرو میتواند "مجموعه تناقض" را بدون کار اضافی تولید کند بطوریکه هر وقت بررسی پیشرو براساس انتساب X=x ، مقداری را از دامنه Y حذف میکند، باید X=x را به مجموعه تناقض Y اضافه کند. اگر آخرین مقدار از دامنه Y حذف شود، آنگاه انتسابهای موجود در مجموعه تناقض Y، به مجموعه تناقض X اضافه میشوند. سپس وقتی به Y میرسیم، فورا میدانیم که در صورت نیاز به کجا باید برگردیم.

"پرش به عقب" وقتی انجام میشود که هر مقدار موجود در یک دامنه با انتساب فعلی برخورد داشته باشد، اما بررسی پیشرو این رویداد را تشخیص میدهد و از رسیدن هر جست وجو به این گره جلوگیری میکند! در حقیقت میتوان نشان داد که هر انشعابی که توسط پرش به عقب هرس شد، توسط بررسی پیشرو نیز هرس خواهد شد. ایده ی پرش به عقب در صورتی خوب است که برای جبران شکست صورت گیرد. پرش به عقب وقتی متوجه شکست میشود که دامنه متغیر خالی شود، در این صورت باید از مجموعه ی تناقضی به نام پرش به عقب و در جهت تناقض، استفاده کند.

بطور خلاصه فرض کنید X_j متغیر فعلی و conf(X_j)مجموعه تناقض آن باشد. اگر هر مقدار ممکن برای X_j با شکست مواجه شد، به جدیدترین متغیر X_i پرش کنید . قرار دهید:

Conf(X_j) <-- conf(X_i) U conf(X_j) – { X_i }

هر وقت به تناقض برسیم، پرش به عقب میتواند به ما بگوید که چقدر به عقب برگردیم، و در نتیجه وقت را صرف تغییر متغیرهایی نمیکنیم که مشکل را حل نمیکنند. علاوه براین نمیخواهیم دوباره با این مشکل مواجه شویم. وقتی جست وجو به تناقض میررسد، میدانیم که زیرمجموعه ای از "مجموعه تناقض" مسئول این مشکل است. روش یادگیری محدودیت ها یک مجموعه مینیمم را از مجموعه تناقض پیدا میکند که موجب تولید مشکل میگردد. این مجموعه از متغیرها، همراه با مقادیر متناظر آنها، نامطلوب نامیده میشود. سپس نامطلوب را ثبت میکنیم. برای این کار محدودیت های جدیدی به CSP اضافه میکنیم یا نامطلوبها را به طور جداگانه نگهداری میکنیم.