یک الگوریتم کارآمد برای حل مسئله کمترین هزینه جریان با شرایط زائد مکمل
سال انتشار: 1399
نوع سند: مقاله کنفرانسی
زبان: فارسی
مشاهده: 281
فایل این مقاله در 8 صفحه با فرمت PDF قابل دریافت می باشد
- صدور گواهی نمایه سازی
- من نویسنده این مقاله هستم
استخراج به نرم افزارهای پژوهشی:
شناسه ملی سند علمی:
ISFCONF01_008
تاریخ نمایه سازی: 25 خرداد 1400
چکیده مقاله:
این مقاله، الگوریتمی را برای حل مسئله کمترین هزینه جریان (MCF) با یک رویکرد دوگان ارائه می دهد. این الگوریتم، قضیه فرجه مکمل را در هر تکرار حفظ میکند و با به روزرسانی پتانسیل گره بطور تکراری، یک مسیر افزایشی را پیدا می کند. بنابراین، می توان جریان را در شبکه اصلی افزایش داد. بر خلاف الگوریتم های متداول دیگر، الگوریتم ارائه شده نه یک شبکه باقیمانده را پیدا می کند و نه کوتاه ترین مسیر را. علاوه بر این، الگوریتم ما اطلاعات مربوط به پتانسیل گره را در هر تکرار حفظ می کند و ما برای گسترش شبکه قابل قبول، پتانسیل گره را با تکرارهای محدودی به روز می کنیم. اعتبار الگوریتم ما مشخص است. آزمایشات عددی نشان میدهند که الگوریتم ما یک الگوریتم کارآمد برای مسئله کمترین هزینه جریان (MCF) و به ویژه برای شبکه ای با یک بازه کوچک از هزینه در واحد جریان است.
کلیدواژه ها:
نویسندگان
امین اسکندری
دانشکده فنی و حرفه ای سما، واحد شیراز، شیراز، ایران