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