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

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

معرفی

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

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

مقدمات

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

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

تعریف

مسئله ارضای محدودیت دودویی P، شامل:

• مجموعه متناهی از N مقدار، V₁,…,V_N
• برای هر مقدار V_i دامنه محدود از مقادیر k_i، D_i={ v₁ⁱ,…,v_kⁱ}
• برای هر جفت از مقادیر {V_i,V_j} محدودیت C_{i,j} میان D_i وD_j که زیرمجموعه‌ای از D_i× D_j می‌باشد.

اگر (v_lⁱ , v_m^j) ∈C_{i,j} باشد به این معناست که v_lⁱ → V_i , v_m^j → V_j

راه حل برای مسئله P اختصاص دادن{_vs1¹ → V₁,…,v_siⁱ → V_i,…,_vsN^N → V_N} به طوری که برای هر i و j رابطه مقابل سازگار باشد. {_vsiⁱ → V_i , v_sj^j → V_j}.

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

داده ساختار استفاده شده در الگوریتم جستجوی رو به جلو (FC) آرایه دو بعدی Domain می‌باشد. Domain_m^j صفر می‌باشد اگر و فقط اگر این رابطه v_m^j → V_jبا تمامی روابط مقادیر گذشته سازگار باشد، در غیر این صورت شامل اندیس اولین (به معنای کمترین) مقدار اختصاص داده شده‌ای است که این رابطه v_m^j → V_jناسازگار است.

شبه کد الگوریتم جستجوی رو به جلو

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

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

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

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

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

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

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

منابع

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