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