بخشی از متن فایل word بهينه سازي در شبکه هاي حداکثر جريان هرزوج گره :
سال انتشار : 1396
نام کنفرانس یا همایش : سومين کنفرانس بين المللي مهندسي صنايع و سيستمها (ICISE 2017)
تعداد صفحات :9
چکیده مقاله:
شبکه های حداکثر جریان از مباحث مشهور، بنیادی و پرطرف دار در جریان های شبکه بوده و کاربردهای فراوانی در حوزه های مختلف دارند. برای حل اینگونه شبکه ها، روش ها و الگوریتم های زیادی با رویکردهای متفاوت جریان دارد. در این مقاله، الگوریتم دقیق جدیدی با نام مستطیل آبشاری، با رویکرد افزودن مسیر بر پایه جبرماتریسی و با پیچیدگی زمانی بدترین حالت ((O(n(3 ارایه می شود، بطوریکه مقدار حداکثر جریان و مسیر را از هرزوج گره محاسبه می کند. اساس این الگوریتم، انجام حداقل n-2 محاسبات ریاضی در قالب مستطیل هایی هستند که در یک راس مشترکند. الگوریتم مستطیل های آبشاری، بجهت وابسته کردن محاسبات ماتریس مسیر به ماتریس جریان بسیار سریع و از طرفی دیگر بجهت انجام محاسبات مستطیلی بسیار جذاب است. در پایان، با ارایه یک مثال نمونه الگوریتم مستطیل های آبشاری گام به گام پیاده سازی شده است.