این الگوریتم جستجوی رو به جلو برای حل مسائل ارضای محدودیت ( 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} محدودیت C{i, j} میان 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ناسازگار است.
زمانی که مقدار احتمالی vliرا برای مقدار کنونی Vi در نظر می گیریم کافی است که به دنبال صفر در آرایهٔ Domainliبگردیم، هر مقدار دیگری ضمانت شده است که با تمام انتخاب های قبلی سازگار است.
این نوشته برگرفته از سایت ویکی پدیا می باشد، اگر نادرست یا توهین آمیز است، لطفا گزارش دهید: گزارش تخلفجستجوی عقب گرد الگوریتمی است برای حل مسائل ارضای محدودیت ( Constraint satisfaction problems ( CPs ) ) که در حدود کمتر از یک قرن شناخته شده اند اما هنوز از گزینه مناسب دور است.
برخی از الگوریتم های بهبودیافته جستجوی عقب گرد شامل ( backjumping ( BJ و ( backmarking ( BM که بهتر از جست جوی عقب گرد عمل می کنند. هم چنین راه حل ساده تری برای جست جوی عقب گرد وجود دارد، جستجوی رو به جلو ( Forward Checking ( FC ) ) .
مسائل ارضای محدودیت ( CPs ) دودویی شامل مجموعه متناهی از مقادیر است که هر کدام دارای دامنه محدود از مقادیر پتانسیل و مجموعه ای از محدودیت های دو به دو میان مقادیر.
هدف اختصاص دادن ارزش به هر مقدار است به طوری که محدودیت ها را نیز در نظر بگیرد. بسته به نوع برنامه ممکن است همهٔ انواع اختصاص دادن های محدودیت ها پیدا شود یا فقط یکی پیدا شود.
مسئله ارضای محدودیت دودویی P، شامل:
• مجموعه متناهی از N مقدار، V1, …, VN
• برای هر مقدار Vi دامنه محدود از مقادیر ki، Di={ v1i, …, vki}
• برای هر جفت از مقادیر {Vi, Vj} محدودیت C{i, j} میان 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ناسازگار است.
زمانی که مقدار احتمالی vliرا برای مقدار کنونی Vi در نظر می گیریم کافی است که به دنبال صفر در آرایهٔ Domainliبگردیم، هر مقدار دیگری ضمانت شده است که با تمام انتخاب های قبلی سازگار است.
wiki: جستجوی رو به جلو