الگوریتم دورگه
استنتاج همبند چرخه ای /الگوریتم جستجوی همبند چرخه ای

این الگوریتم ترکیبی بر پایهٔ جستجو در مجموعه ای از متغیرها و استنتاج بر روی متغیرهای دیگر استوار است. به‌طور خاص، در جهت عکس پیمایش کردن، یا روش‌های دیگر جستجو روی تعدادی از متغیرها اعمال می‌شود؛ هرگاه یک گمارش جزئیسازگار روی این متغیرها یافت شود، استنتاج روی متغیرهای باقی‌مانده اعمال می‌شود تااطمینان حاصل کند که آیا این گمارش جزئی می‌تواند گسترش یابد تا یک راه حل را شکل بدهد.
در بعضی از مسایل الگوریتم‌های کامل و کارآمد وجود دارند. مثلاً مسایلی که گراف‌های یگانه و دوگانه آن‌ها درخت‌ها و جنگل‌ها هستند در زمانی که از درجهٔ چندجمله‌ای است می‌توانند حل شوند. این در انتخاب متغیرهایی که با جستجو بررسی شده‌اند مؤثر است. در واقع زمانی که متغیر بررسی می‌شود، می‌تواند به‌طور مؤثر از گراف حذف شود، در حالی که تمام قیود مرتبط با مقدارش را محدود می‌کند. به‌طور متناوب، یک متغیر بررسی شده می‌تواند با تعدادی متغیر مجزا جایگزین شود، یکی برای هر قید، همگی دارای دامنه ای با مقدار یکسان.
این الگوریتم ترکیبی کارآمد است اگر، متغیرها طوری انتخاب شوند که دو برابر کردن یا حذف کردن آن‌ها مسئله را به نوعی تبدیل کند که به راحتی با استنتاج قابل حل باشد. خصوصاً اگر این متغیرها به شکل یک چرخهٔ همبند از گراف مسئله باشند، استنتاج کارآمد است زیرا باید مسئله ای را حل کند که گراف آن درخت است، یا به‌طور معمول تر، جنگل است. چنین الگوریتمی به شکل زیر است:
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
یک چرخهٔ همبند از گراف مسئله را پیدا کن
 عملیات جستجو را بر روی متغیرهای همبندی اجرا کن
 زمانی که یک واگذاری جزئی سازگار بر همه متغیرها یافت شد،
 هر متغیر همبندی را با یک متغیر جدید برای هر قید جایگزین کن؛
 دامنه این متغیرهای جدید را مقدار متغیر قبلی در واگذاری جزئی قرار بده
 مسئله را با استفاده از استنتاج حل کن
بازدهی این الگوریتم به دو عامل متضاد بستگی دارد. از یک طرف، هر چه همبندی کوچکتر باشد، زیرمسئله ای که با جستجو قرار است حل شود کوچکتر است؛ از آنجا که استنتاج روی درخت‌ها کارآمد است، جستجو بخشی است که بیشترین تأثیر را در بازدهی دارد. از طرف دیگر، پیدا کردن یک همبندی با کمترین سایز مسئلهٔ دشواری است. در نتیجه، یک چرخهٔ همبدی کوچک به جای کوچکترین آن استفاده می‌شود.
راه دیگر کاهش دادن زمان اجرای جستجو این است که بار مسیولیت بیشتری در بخش استنتاج قرار داده شود. خصوصاً، استنتاج می‌تواند به‌طور نسبی کارآمد باشد حتی اگر گراف مسئله یک جنگل نباشد بلکه، گرافی کوچکتراز آن با عرض القایی باشد. این با انجام جستجو روی مجموعه ای از متغیرهایی که چرخهٔ همبندی نیستند، ولی زمانی که حذف می‌شوند برای گراف پهنای عرضی با کران ب اجاد می‌کنند، استخراج می‌شود. به چنین دسته متغیرهایی یک ب-همبندی از مسئله گفته می‌شود.
عرض استنتاجی یا القایی گراف بعد از این که مجموعه ای از متغیرها حذف شدند عرض استنتاجی تعدیل شده نامیده می‌شود. در نتیجه عرض استنتاجی تعدیل شده متناسب با یک ب-همبندی همیشه ب است. عموماً پیدا کردن یک ب- همبندی با کمترین سایز سخت است. به هر حال، یک ب-همبندی با سایز غیر مینیمم در یک ترتیب ثابت از متغیرها به راحتی یافت می‌شود. به خصوص، چنین همبندیی، یک گراف با عرضی که کران آن ب است و متناسب با ترتیب مخصوص متغیرهاست، از خود به جا می‌گذارد.
الگوریتم پیدا کردن چنین همبندیی با تقلید از روند پیدا کردن گراف القایی یک مسئله با توجه به ترتیب در نظر گرفته شده متغیرهای آن، ادامه می‌یابد (این روش از آخرین گره به ترتیب تا اولین گره ادامه پیدا می‌کند، در حالی که بین هر جفت از گره‌های پدر آن گره‌ها که به هم متصل نیستند، یک یال اضافه می‌کند). هر گاه این روند گره ای با بیش از ب تا پدر یافت یا آن را ساخت، آن گره از گراف حذف شده و به همبندی اضافه می‌شود. گراف بدست آمده هیچ گره ای که پهنای آن بیشتر از ب باشد (تعداد پدرهای آن بیشتر از ب باشد) ندارد، و در نتیجه مجموعه گره‌های حذف شده یک ب-همبندی است.
یک راه چاره برای استفاده از این الگوریتم این است که اجازه دهیم جستجو متغیرها را بررسی کند، ولی در هر قدم اطمینان حاصل کند که آیا گراف باقی‌مانده یک جنگل است، و اگر این چنین است استنتاج را بر روی آن اجرا کند. در واقع، به جای پیدا کردن مجموعه ای از متغیرها در ابتدای کار و استفاده کردن از آن‌ها فقط در طول جستجو، الگوریتم به عنوان یک جستجوی عادی شروع به کار می‌کند؛ در هر مرحله، اگر متغیرهای واگذار شده یک ب-همبندی از مسئله تشکیل دادند، استنتاج برای بررسی رضایتمندی اجرا می‌شود. این امکان‌پذیر است زیرا بررسی این که آیا مجموعه گره‌های داده شده یک ب-همبندی برای یک ب ثابت است، مسئله ای از درجه چندجمله‌ای است.