الگوریتم دورگه

در مبحث ارضای محدودیت، الگوریتم دورگه یک مسئله ارضای محدودیت را با ترکیب دو روش مختلف حل می‌کند، برای مثال شایسته سازی متغیر(در جهت عکس پیمایش کردن، پرش به عقب، و غیره) و استنتاج قیدی(سازگاری قوسی، حذف متغیر، و غیره).
الگوریتم‌های دورگه از خواص خوب روش‌های مختلف با اعمال آنها بر مسایلی که می‌توانند آنها به طور کارآمد حل کنند بهره‌برداری می‌کنند. مثلا جستجو زمانی کارآمد است که مسئله راه حل‌های زیادی داشته باشد، در حالی که استنتاج در اثبات قابلیت رضایتمندی مسایلی که قیدهای زیادی دارند کارآمد است.
استنتاج همبند چرخه‌ای /الگوریتم جستجوی همبند چرخه‌ای
این الگوریتم ترکیبی بر پایه جستجو در مجموعه‌ای از متغیرها و استنتاج بر روی متغیرهای دیگر استوار است. به طور خاص، در جهت عکس پیمایش کردن، یا روش‌های دیگر جستجو روی تعدادی از متغیرها اعمال می‌شود؛ هرگاه یک گمارش جزییسازگار روی این متغیرها یافت شود، استنتاج روی متغیرهای باقی‌مانده اعمال می‌شود تااطمینان حاصل کند که آیا این گمارش جزیی می‌تواند گسترش یابد تا یک راه حل را شکل بدهد.
در بعضی از مسایل الگوریتم‌های کامل و کارآمد وجود دارند. مثلا مسایلی که گراف‌های یگانه و دوگانه آنها درخت‌ها و جنگل‌ها هستند در زمانی که از درجه چندجمله‌ای است می‌توانند حل شوند. این در انتخاب متغیرهایی که با جستجو بررسی شده‌اند موثر است. در واقع زمانی که متغیر بررسی می‌شود، می‌تواند به طور موثر از گراف حذف شود، در حالی که تمام قیود مرتبط با مقدارش را محدود می‌کند. به طور متناوب، یک متغیر بررسی شده می‌تواند با تعدادی متغیر مجزا جایگزین شود، یکی برای هر قید، همگی دارای دامنه‌ای با مقدار یکسان.
این الگوریتم ترکیبی کارآمد است اگر، متغیرها طوری انتخاب شوند که دو برابر کردن یا حذف کردن آنها مسئله را به نوعی تبدیل کند که به راحتی با استنتاج قابل حل باشد. خصوصا اگر این متغیرها به شکل یک چرخه همبند از گراف مسئله باشند، استنتاج کارآمد است زیرا باید مسئله‌ای را حل کند که گراف آن درخت است، یا به طور معمول‌تر، جنگل است. چنین الگوریتمی به شکل زیر است:
find a cycle cutset of the graph of the problem
run search on the variables of the cutset
when a consistent partial assignment to all variables are found,
replace each variable of the cutset with a new variable for each constraint;
set the domains of these new variables to the value of the old variable in the partial assignment
solve the problem using inference
یک چرخه همبند از گراف مسئله را پیدا کن
عملیات جستجو را بر روی متغیرهای همبندی اجرا کن
زمانی که یک واگذاری جزیی سازگار بر همه متغیرها یافت شد،
هر متغیر همبندی را با یک متغیر جدید برای هر قید جایگزین کن؛
دامنه این متغیرهای جدید را مقدار متغیر قبلی در واگذاری جزیی قرار بده
مسئله را با استفاده از استنتاج حل کن
بازدهی این الگوریتم به دو عامل متضاد بستگی دارد. از یک طرف، هر چه همبندی کوچکتر باشد، زیرمسئله‌ای که با جستجو قرار است حل شود کوچکتر است؛ از آنجا که استنتاج روی درخت‌ها کارآمد است، جستجو بخشی است که بیشترین تاثیر را در بازدهی دارد. از طرف دیگر، پیدا کردن یک همبندی با کمترین سایز مسئله دشواری است. در نتیجه، یک چرخه همبدی کوچک به جای کوچکترین آن استفاده می‌شود.
راه دیگر کاهش دادن زمان اجرای جستجو این است که بار مسیولیت بیشتری در بخش استنتاج قرار داده شود. خصوصا، استنتاج می‌تواند به طور نسبی کارآمد باشد حتی اگر گراف مسئله یک جنگل نباشد بلکه، گرافی کوچکتراز آن با عرض القایی باشد. این با انجام جستجو روی مجموعه‌ای از متغیرهایی که چرخه همبندی نیستند، ولی زمانی که حذف می‌شوند برای گراف پهنای عرضی با کران ب اجاد می‌کنند، استخراج می‌شود. به چنین دسته متغیرهایی یک ب-همبندی از مسئله گفته می‌شود.
عرض استنتاجی یا القایی گراف بعد از این که مجموعه‌ای از متغیرها حذف شدند عرض استنتاجی تعدیل شده نامیده می‌شود. در نتیجه عرض استنتاجی تعدیل شده متناسب با یک ب-همبندی همیشه ب است. عموما پیدا کردن یک ب- همبندی با کمترین سایز سخت است. به هر حال، یک ب-همبندی با سایز غیر مینیمم در یک ترتیب ثابت از متغیرها به راحتی یافت می‌شود. به خصوص، چنین همبندیی، یک گراف با عرضی که کران آن ب است و متناسب با ترتیب مخصوص متغیرهاست، از خود به جا می‌گذارد.
الگوریتم پیدا کردن چنین همبندیی با تقلید از روند پیدا کردن گراف القایی یک مسئله با توجه به ترتیب در نظر گرفته شده متغیرهای آن، ادامه می‌یابد (این روش از آخرین گره به ترتیب تا اولین گره ادامه پیدا می‌کند، در حالی که بین هر جفت از گره‌های پدر آن گره‌ها که به هم متصل نیستند، یک یال اضافه می‌کند). هر گاه این روند گره‌ای با بیش از ب تا پدر یافت یا آن را ساخت، آن گره از گراف حذف شده و به همبندی اضافه می‌شود. گراف بدست آمده هیچ گره‌ای که پهنای آن بیشتر از ب باشد (تعداد پدرهای آن بیشتر از ب باشد) ندارد، و درنتیجه مجموعه گره‌های حذف شده یک ب-همبندی است.
یک راه چاره برای استفاده از این الگوریتم این است که اجازه دهیم جستجو متغیرها را بررسی کند، ولی در هر قدم اطمینان حاصل کند که آیا گراف باقی‌مانده یک جنگل است، و اگر این چنین است استنتاج را بر روی آن اجرا کند. در واقع، به جای پیدا کردن مجموعه‌ای از متغیرها در ابتدای کار و استفاده کردن از آنها فقط در طول جستجو، الگوریتم به عنوان یک جستجوی عادی شروع به کار می‌کند؛ در هر مرحله، اگر متغیرهای واگذار شده یک ب-همبندی از مسئله تشکیل دادند، استنتاج برای بررسی رضایتمندی اجرا می‌شود. این امکان‌پذیر است زیرا بررسی این که آیا مجموعه گره‌های داده شده یک ب-همبندی برای یک ب ثابت است، مسئله‌ای از درجه چندجمله‌ای است.
الگوریتم ترکیبی درخت تجزیه
یک الگوریتم ترکیبی جستجویی/استنتاجی دیگر بر پایه درخت تجزیه کار می‌کند. عموما، یک مسئله ارضای محدودیت می‌تواند با ایجاد یک درخت تجزیه و سپس استفاده از یک الگوریتم تخصصی حل شود.
چنین الگوریتمی‌اول بر پایه توزیع قیدها بر روی گره‌ها و سپس حل کردن زیر مسئله در هر گره بستگی دارد. این توزیع ایجاد قیدهای جدیدی که تاثیرات قیدهای یک گره بر گره اضافه شده را نشان می‌دهد، را شامل می‌شود. دقیقتر، اگر دو گره به هم متصل باشند، متغیرهای یکدیگر را به اشتراک می‌گذارند. ارزیابی‌های مجاز این متغیرها با توجه به قیدهای گره اول به ما می‌گوید که چگونه گره اول بر متغیرهای گره دوم اثر می‌گذارد. این الگوریتم با ایجاد قیدهای مورد قبول این ارزیابی‌ها و جا دادن این قیدها در گره دوم کار می‌کند.
زمانی که قیدها از برگها تا ریشه منتشر شدند، تمام گره‌ها همه قیدهایی که با آنها متناسب است را دربردارند. در نتیجه مسئله در هر گره قابل حل است.
دسترسی به الگوریتم دورگه با استفاده از حذف متغیر برای ایجاد قیدهای جدیدی که در بین گره‌ها توزیع می‌شود، و یک الگوریتم جستجو (مانند بازگشت به مراتب عقب، پرش به عقب، جستجوی محلی) روی هر گره منفرد، امکان‌پذیر است.