جستجوی رو به جلو

این الگوریتم جستجوی رو به جلو برای حل مسائل ارضای محدودیت (constraint satisfaction) متداول است و پیشنهاد موفقی است برای چپ جستجوی عقب‌گرد(backtracing).

 معرفی 
جستجوی عقب‌گرد الگوریتمی است برای حل مسائل ارضای محدودیت (Constraint satisfaction problems(CPs)) که در حدود کمتر از یک قرن شناخته شده‌اند اما هنوز از گزینه مناسب دور است.

برخی از الگوریتم‌های بهبودیافته جستجوی عقب‌گرد شامل (backjumping (BJ و (backmarking(BM که بهتر از جست جوی عقب‌گرد عمل می‌کنند. هم چنین راه حل ساده‌تری برای جست جوی عقب‌گرد وجود دارد، جستجوی رو به جلو (Forward Checking(FC)).

 مقدمات 
مسائل ارضای محدودیت (CPs) دودویی شامل مجموعه متناهی از مقادیر است که هر کدام دارای دامنه محدود از مقادیر پتانسیل و مجموعه‌ای از محدودیت‌های دو به دو میان مقادیر.

هدف اختصاص دادن ارزش به هر مقدار است به طوری که محدودیت‌ها را نیز در نظر بگیرد. بسته به نوع برنامه ممکن است همهٔ انواع اختصاص دادن‌های محدودیت‌ها پیدا شود یا فقط یکی پیدا شود.

 تعریف 
مسئله ارضای محدودیت دودویی P، شامل:
 مجموعه متناهی از N مقدار، V1,…,VN
 برای هر مقدار Vi دامنه محدود از مقادیر ki، Di={ v1i,…,vki}
 برای هر جفت از مقادیر {Vi,Vj} محدودیت  میان Di وDj که زیرمجموعه‌ای از Di× Dj می‌باشد.

اگر (vli , vmj) ∈C{i,j} باشد به این معناست که vli → Vi , vmj → Vj

راه حل برای مسئله P اختصاص دادن{vs11 → V1,…,vsii → Vi,…,vsNN → VN} به طوری که برای هر i و j رابطه مقابل سازگار باشد. {vsii → Vi , vsjj → Vj}.

فرض کنید ما یک رابطهٔ سازگار برای i-1 تای اول مقادیر پیدا کردیم که بدین معناست در تمام جفت مقایسه تنها این i-1 مقدار در نظر گرفته می‌شوند. در این نقطه V1 تا Vi-1 را مقادیر گذشته (past variables) وVi را مقدار کنونی (current variable) و مابقی را مقادیر آینده (future variables) می‌نامیم.

داده ساختار استفاده شده در الگوریتم جستجوی رو به جلو (FC) آرایه دو بعدی Domain می‌باشد.
Domainmj صفر می‌باشد اگر و فقط اگر این رابطه vmj → Vjبا تمامی روابط مقادیر گذشته سازگار باشد، در غیر این صورت شامل اندیس اولین (به معنای کمترین) مقدار اختصاص داده شده‌ای است که این رابطه vmj → Vjناسازگار است.
شبه کد الگوریتم جستجوی رو به جلو
چپ

شبه کد تابع Check-Forward
چپ

شبه کد فرایند Restore
چپ

زمانی که مقدار احتمالی vliرا برای مقدار کنونی Vi در نظر می‌گیریم کافی است که به دنبال صفر در آرایهٔ Domainliبگردیم، هر مقدار دیگری ضمانت شده است که با تمام انتخاب‌های قبلی سازگار است.

زمانی که موفق شدیم مقداری را به مقدار کنونی اختصاص دهیم باید این مقدار را در مقابل تمامی مقادیر آیندهٔ اختصاص داده نشده چک کنیم و در صورت لزوم آرایهٔ Domain را به روز کنیم.

شبه کد داده شده فقط شامل قسمت‌های مهم می‌باشد در جزئیات بیشتر بعد از مقداردهی اولیه FC(1) صدا زده می‌شود و تمامی راه حل‌های موجود چاپ می‌شود.

واگذاری‌های (assignments) جزئی کنونی در مقادیر s1 ,.. , sN ذخیره می‌شود، اختصاص به si زمانی رد می‌شود که dwo(domain wipe-out) درست باشد به این معنا که ما برخی مقادیر آینده با انتخاب ما ناسازگار است. هم چنین درست بودن dwo به این معناست که راه حلی در این زیردرخت در نظر گرفته شده وجود ندارد.

پس از اینکه درنظرگرفتن انتخاب‌ها برای si تمام شد باید تغییراتی که در آرایهٔ Domain اعمال کردیم قبل از ادامه دادن برگردانیم.

 منابع 

 R. M. Haralick and G. L. Elliott. Increasing tree search efficiency for constraint satisfaction problems. Artificial Intelligence, 14:263–313, 1980.

رده:الگوریتم‌های جستجو
رده:برنامه‌نویسی ارضای محدودیت