حل مسئله مجموعه مستقل d-فاصله با رویکرد combopt zero

مسئله‌ی مجموعه مستقل بیشینه یک مسئله‌ی بهینه‌سازی ترکیبیاتی np-سخت است. کاربردهای فراوانی برای این مسائل در دنیای واقعی وجود دارد. یکی از تعمیم‌های این مسئله، مسئله مجموعه مستقل d-فاصله بیشینه است. این مسئله نیز مانند مسئله‌ی مجموعه مستقل بیشینه یک مسئله np-سخت است. به همین دلیل تاکنون رویکردی چندجمله‌ای برای این حل مسئله یافت نشده‌است. رویکرد‌های دقیق موجود برای مسئله مجموعه مستقل d-فاصله بیشینه دارای پیچیدگی زمانی بدترین حالت نمایی هستند. رویکرد‌های غیردقیق و اکتشافی جوابی ریزبهینه را بر می‌گردانند. در سال‌های اخیر که رویکرد‌های یادگیری تقویتی روایج پیدا کرده است، یک الگوریتم با نتایج امیدوارکننده به نام combopt zero برای حل برخی از مسائل بهینه‌سازی ترکیبیاتی ارائه شده‌است. در این مقاله ما با پیاده سازی مسئله در چارچوب فرآیند تصمیم‌گیری مارکوف، از این الگوریتم برای حل مسئله مجموعه مستقل d-فاصله بیشینه استفاده کرده‌ایم. نتایج حاصل از شبیه‌سازی را با حل دقیق مقایسه کردیم و نتایج امیدوارکننده بودند. برای بدست آوردن جواب‌های دقیق، از رویکرد برنامه‌ریزی خطی عدد صحیح، استفاده شده‌است.