الگوریتم دورگه
 | این مقاله نیازمند ویکیسازی است. لطفاً با توجه به راهنمای ویرایش و شیوهنامه، محتوای آن را بهبود بخشید. |
الگوریتم دورگه یک مسئله ارضای محدودیت را با ترکیب دو روش مختلف حل می‌کند، برای مثال شایسته سازی متغیر(در جهت عکس پیمایش کردن، پرش به عقب، و غیره) و استنتاج قیدی(سازگاری قوسی، حذف متغیر، و غیره).
الگوریتم‌های دورگه از خواص خوب روش‌های مختلف با اعمال آن‌ها بر مسایلی که می‌توانند آن‌ها به‌طور کارآمد حل کنند بهره‌برداری می‌کنند. مثلاً جستجو زمانی کارآمد است که مسئله راه حل‌های زیادی داشته باشد، در حالی که استنتاج در اثبات قابلیت رضایتمندی مسایلی که قیدهای زیادی دارند کارآمد است.
استنتاج همبند چرخه ای /الگوریتم جستجوی همبند چرخه ای[ویرایش]
این الگوریتم ترکیبی بر پایهٔ جستجو در مجموعه ای از متغیرها و استنتاج بر روی متغیرهای دیگر استوار است. به‌طور خاص، در جهت عکس پیمایش کردن، یا روش‌های دیگر جستجو روی تعدادی از متغیرها اعمال می‌شود؛ هرگاه یک گمارش جزئیسازگار روی این متغیرها یافت شود، استنتاج روی متغیرهای باقی‌مانده اعمال می‌شود تااطمینان حاصل کند که آیا این گمارش جزئی می‌تواند گسترش یابد تا یک راه حل را شکل بدهد.
در بعضی از مسایل الگوریتم‌های کامل و کارآمد وجود دارند. مثلاً مسایلی که گراف‌های یگانه و دوگانه آن‌ها درخت‌ها و جنگل‌ها هستند در زمانی که از درجهٔ چندجمله‌ای است می‌توانند حل شوند. این در انتخاب متغیرهایی که با جستجو بررسی شده‌اند مؤثر است. در واقع زمانی که متغیر بررسی می‌شود، می‌تواند به‌طور مؤثر از گراف حذف شود، در حالی که تمام قیود مرتبط با مقدارش را محدود می‌کند. به‌طور متناوب، یک متغیر بررسی شده می‌تواند با تعدادی متغیر مجزا جایگزین شود، یکی برای هر قید، همگی دارای دامنه ای با مقدار یکسان.
این الگوریتم ترکیبی کارآمد است اگر، متغیرها طوری انتخاب شوند که دو برابر کردن یا حذف کردن آن‌ها مسئله را به نوعی تبدیل کند که به راحتی با استنتاج قابل حل باشد. خصوصاً اگر این متغیرها به شکل یک چرخهٔ همبند از گراف مسئله باشند، استنتاج کارآمد است زیرا باید مسئله ای را حل کند که گراف آن درخت است، یا به‌طور معمول تر، جنگل است. چنین الگوریتمی به شکل زیر است:
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
یک چرخهٔ همبند از گراف مسئله را پیدا کن عملیات جستجو را بر روی متغیرهای همبندی اجرا کن زمانی که یک واگذاری جزئی سازگار بر همه متغیرها یافت شد، هر متغیر همبندی را با یک متغیر جدید برای هر قید جایگزین کن؛ دامنه این متغیرهای جدید را مقدار متغیر قبلی در واگذاری جزئی قرار بده مسئله را با استفاده از استنتاج حل کن
بازدهی این الگوریتم به دو عامل متضاد بستگی دارد. از یک طرف، هر چه همبندی کوچکتر باشد، زیرمسئله ای که با جستجو قرار است حل شود کوچکتر است؛ از آنجا که استنتاج روی درخت‌ها کارآمد است، جستجو بخشی است که بیشترین تأثیر را در بازدهی دارد. از طرف دیگر، پیدا کردن یک همبندی با کمترین سایز مسئلهٔ دشواری است. در نتیجه، یک چرخهٔ همبدی کوچک به جای کوچکترین آن استفاده می‌شود.
راه دیگر کاهش دادن زمان اجرای جستجو این است که بار مسیولیت بیشتری در بخش استنتاج قرار داده شود. خصوصاً، استنتاج می‌تواند به‌طور نسبی کارآمد باشد حتی اگر گراف مسئله یک جنگل نباشد بلکه، گرافی کوچکتراز آن با عرض القایی باشد. این با انجام جستجو روی مجموعه ای از متغیرهایی که چرخهٔ همبندی نیستند، ولی زمانی که حذف می‌شوند برای گراف پهنای عرضی با کران ب اجاد می‌کنند، استخراج می‌شود. به چنین دسته متغیرهایی یک ب-همبندی از مسئله گفته می‌شود.
عرض استنتاجی یا القایی گراف بعد از این که مجموعه ای از متغیرها حذف شدند عرض استنتاجی تعدیل شده نامیده می‌شود. در نتیجه عرض استنتاجی تعدیل شده متناسب با یک ب-همبندی همیشه ب است. عموماً پیدا کردن یک ب- همبندی با کمترین سایز سخت است. به هر حال، یک ب-همبندی با سایز غیر مینیمم در یک ترتیب ثابت از متغیرها به راحتی یافت می‌شود. به خصوص، چنین همبندیی، یک گراف با عرضی که کران آن ب است و متناسب با ترتیب مخصوص متغیرهاست، از خود به جا می‌گذارد.
الگوریتم پیدا کردن چنین همبندیی با تقلید از روند پیدا کردن گراف القایی یک مسئله با توجه به ترتیب در نظر گرفته شده متغیرهای آن، ادامه می‌یابد (این روش از آخرین گره به ترتیب تا اولین گره ادامه پیدا می‌کند، در حالی که بین هر جفت از گره‌های پدر آن گره‌ها که به هم متصل نیستند، یک یال اضافه می‌کند). هر گاه این روند گره ای با بیش از ب تا پدر یافت یا آن را ساخت، آن گره از گراف حذف شده و به همبندی اضافه می‌شود. گراف بدست آمده هیچ گره ای که پهنای آن بیشتر از ب باشد (تعداد پدرهای آن بیشتر از ب باشد) ندارد، و در نتیجه مجموعه گره‌های حذف شده یک ب-همبندی است.
یک راه چاره برای استفاده از این الگوریتم این است که اجازه دهیم جستجو متغیرها را بررسی کند، ولی در هر قدم اطمینان حاصل کند که آیا گراف باقی‌مانده یک جنگل است، و اگر این چنین است استنتاج را بر روی آن اجرا کند. در واقع، به جای پیدا کردن مجموعه ای از متغیرها در ابتدای کار و استفاده کردن از آن‌ها فقط در طول جستجو، الگوریتم به عنوان یک جستجوی عادی شروع به کار می‌کند؛ در هر مرحله، اگر متغیرهای واگذار شده یک ب-همبندی از مسئله تشکیل دادند، استنتاج برای بررسی رضایتمندی اجرا می‌شود. این امکان‌پذیر است زیرا بررسی این که آیا مجموعه گره‌های داده شده یک ب-همبندی برای یک ب ثابت است، مسئله ای از درجه چندجمله‌ای است.
الگوریتم ترکیبی درخت تجزیه[ویرایش]
یک الگوریتم ترکیبی جستجویی/استنتاجی دیگر بر پایه درخت تجزیه کار می‌کند. عموماً، یک مسئلهٔ ارضای محدودیت می‌تواند با ایجاد یک درخت تجزیه و سپس استفاده از یک الگوریتم تخصصی حل شود.
چنین الگوریتمی‌اول بر پایه توزیع قیدها بر روی گره‌ها و سپس حل کردن زیر مسئله در هر گره بستگی دارد. این توزیع ایجاد قیدهای جدیدی که تأثیرات قیدهای یک گره بر گره اضافه شده را نشان می‌دهد، را شامل می‌شود. دقیقتر، اگر دو گره به هم متصل باشند، متغیرهای یکدیگر را به اشتراک می‌گذارند. ارزیابی‌های مجاز این متغیرها با توجه به قیدهای گره اول به ما می‌گوید که چگونه گره اول بر متغیرهای گره دوم اثر می‌گذارد. این الگوریتم با ایجاد قیدهای مورد قبول این ارزیابی‌ها و جا دادن این قیدها در گره دوم کار می‌کند.
زمانی که قیدها از برگها تا ریشه منتشر شدند، تمام گره‌ها همه قیدهایی که با آن‌ها متناسب است را دربردارند. در نتیجه مسئله در هر گره قابل حل است.
دسترسی به الگوریتم دورگه با استفاده از حذف متغیر برای ایجاد قیدهای جدیدی که در بین گره‌ها توزیع می‌شود، و یک الگوریتم جستجو (مانند بازگشت به مراتب عقب، پرش به عقب، جستجوی محلی) روی هر گره منفرد، امکان‌پذیر است.
منابع[ویرایش]
- صفحهٔ انگلیسی این متن
- Dechter, Rina (2003). Constraint Processing. Morgan Kaufmann. ISBN 1-55860-890-7