ارائه رويكرد‌هايي دقيق براي حل گونه‌هايي از مسئله‌ي مجموعه رأس بازخورد كمينه

اصفهان : دانشگاه صنعتي اصفهان

مهندسي كامپيوتر

كارشناسي ارشد

مسئله‌ي مجموعه رأس بازخورد كمينه، يك مسئله‌ي NP-سخت است، هدف از حل آن، يافتن حداقل تعداد رأس‌هايي است كه بايد از يك گراف حذف شوند تا گراف حاصل، دور نداشته باشد. مسئله مجموعه رأس بازخورد كمينه در هوش مصنوعي تحت عنوان برش دور نيز شناخته مي‌شود. مسئله مجموعه رأس بازخورد، كاربردهاي فراواني در زمينه‌هاي مختلف دارد. ازجمله، جلو‌گيري و حذف بن‌بست در سيستم‌هاي عامل، طراحي چيپ و تراشه‌هاي VLSI، مسائل ارضاي محدوديت در هوش‌مصنوعي، بيوانفورماتيك و پيش‌بيني ژن‌هاي سرطاني، استنتاج بيزي، درستي‌سنجي برنامه، شبكه‌هاي نوري، طراحي مدارهاي تركيبي. براي حل اين مسئله، رويكردهاي دقيق و غيردقيق زيادي معرفي‌شده است. ازجمله رويكرد‌هاي دقيق، استفاده از برنامه‌ريزي عدد صحيح، الگوريتم شاخه و كران، الگوريتم شاخه و برش، برنامه‌نويسي پويا است. ازجمله رويكرد‌هاي غيردقيق، مي‌توان به جستجوي ممنوعه، جستجوي محلي، جستجوي تصادفي حريصانه، الگوريتم ممتيك اشاره كرد. گونه‌هاي مختلفي از مسئله مجموعه رأس بازخورد كمينه وجود دارد كه برخي از آن‌ها عبارتند از: مجموعه رأس بازخورد زيرمجموعه، مجموعه رأس بازخورد مستقل، مجموعه رأس بازخورد همبند، مجموعه رأس بازخورد متمايز. هدف اين پژوهش، تمركز بر روي گونه‌هاي معيني از اين مسئله و ارائه رويكردهاي دقيق براي حل آن‌هاست. براي دو گونه‌ مجموعه رأس بازخورد مستقل و مجموعه رأس بازخورد همبند، تا آنجا كه اطلاع داريم، تاكنون رويكرد‌ي دقيق ارائه نشده است. به همين دليل، ما در اين پژوهش با بهره‌گيري از دو مدل موجود براي مسئله كلاسيك مجموعه رأس بازخورد، مدل‌هايي فشرده براي مسئله مجموعه رأس بازخورد مستقل و همبند ارائه مي‌دهيم. همچنين، گونه‌ي ديگري از مسئله مجموعه رأس بازخورد را در نظر گرفته كه هدف آن، يافتن كمترين تعداد از رئوس است كه حذف آن‌ها موجب پديد آمدن مؤلفه‌هاي همبندي به اندازه‌هاي كوچك يا بدون دور مي‌شود. دو فرمول برنامه‌ريزي خطي عدد صحيح براي اين گونه جديد ارائه مي‌دهيم. با استفاده از نتايج حاصل از شبيه‌سازي، هردو مدل ارائه‌شده براي هر يك از گونه‌ها را مورد مقايسه قرار مي‌دهيم.

223572

نرم افزار

مهندسي برق و كامپيوتر

دانشگاه صنعتي اصفهان