حل مسئله یکریختی زیرگراف از دید برنامه ریزی منابع محدود

مسئله یکریختی زیرگراف به دلیل سخت بودن و استفاده بسیار در حیطه های مختلف از جمله مسایل شبکه، پردازش متن و تصویر، نقشه برداری و زیست شناسی، هم از دیدگاه تئوری و هم از دیدگاه کاربردی مورد توجه محققین زیادی قرار گرفته است. در این تحقیق سعی شد با استفاده از برنامه ریزی محدودیت که از روش های قدرتمند مدل سازی و حل مسایل پیچیده بهینه سازی ترکیبی می باشد و بهره گیری از مفاهیم "اهمیت" و "قاطعیت" از حوزه برنامه ریزی منابع، راهکاری مناسب و کارا جهت حل مسئله یکریختی زیرگراف ارایه گردد. در این راستا از میان مدل های برنامه ریزی محدودیت ارایه شده برای مسئله یکریختی زیرگراف،بهترین مدل موجود از نظر کارایی، انتخاب و سیاست های بیشترین اجبار و کمترین تاثیر به ترتیب جهت انتخاب متغیر و مقدار، در اجرای فاز جستجوی آن به کار برده شدند. با مقایسه روش ارایه شده و سایر رو شها، مشخص گشت با بهره گیری از ویژگ یهای اهمیت و قاطعیت، جواب مسئله با پیمایش تعداد کمتری گره در درخت جستجو پیدا می شود.

کلیدواژه ها:

برنامه ریزی محدودیت ، یکریختی زیرگراف ، کاهش دامنه ، فاز جستجو ، اهمیت ، قاطعیت