عنوان : ( یک الگوریتم حریصانه دوگان محوربرای حل مسئله افراز متوازن گراف )
نویسندگان: فریبا باستانی , زهرا جوانشیر , رضا قنبری , خاطره قربانی مقدم ,
Full Textچکیده
مسئله افراز متوازن گراف با هدف کمینه سازی وزن یال های برشی، یکی از مسائل NP-hardبنیادی در بهینه سازی ترکیبیاتی با کاربردهای گسترده است. در این پژوهش، یک الگوریتم حریصانه جدید برای مسئله افراز دو بخشی گراف ارائه می شود که توسط جواب مسئله دوگان هدایت می گردد. ایده اصلی الگوریتم، تخصیص یک امتیاز به هر رأس بر اساس مقادیر متغیرهای دوگان مربوط به یال های مجاور آن است. در هر تکرار، رأسی با بیشترین امتیاز به طور حریصانه انتخاب و به یکی از دو بخش افراز اضافه می شود. عملکرد الگوریتم پیشنهادی بر روی نمونه های تصادفی ارزیابی شده و نتایج با یک روش انتخاب تصادفی مقایسه می شود. نتایج تجربی نشان می دهد برای نمونه های بزرگ، استفاده از الگوریتم هدایت شده با دوگان در مقایسه با انتخاب کاملا تصادفی کیفیت افراز را بهبود می بخشد. این الگوریتم یک روش تقریبی ساده و مؤثر برای مسئله افراز متوازن گراف ارائه می دهد
کلمات کلیدی
, افراز گراف, الگوریتم حریصانه, برنامه ریزی خطی دوگان
@inproceedings{paperid:1107017,
author = {باستانی, فریبا and جوانشیر, زهرا and قنبری, رضا and قربانی مقدم, خاطره},
title = {یک الگوریتم حریصانه دوگان محوربرای حل مسئله افراز متوازن گراف},
booktitle = {پنجمین همایش ملی و اولین همایش بین المللی محاسبات نرم علوم مهندسی در صنعت و جامعه},
year = {2026},
location = {ایرانشهر, ايران},
keywords = {افراز گراف، الگوریتم حریصانه، برنامه ریزی خطی دوگان},
}
%0 Conference Proceedings
%T یک الگوریتم حریصانه دوگان محوربرای حل مسئله افراز متوازن گراف
%A باستانی, فریبا
%A جوانشیر, زهرا
%A قنبری, رضا
%A قربانی مقدم, خاطره
%J پنجمین همایش ملی و اولین همایش بین المللی محاسبات نرم علوم مهندسی در صنعت و جامعه
%D 2026
