مسئله بیشینه جریان (Maximum Flow Problem)، در ریاضیات (Mathematics)
انواع روش های بهینه سازی (Optimization Methods) را در آموزش زیر شرح دادیم :
مسئله بیشینه جریان (Maximum Flow Problem) :
📌 معرفی
مسئله بیشینه جریان (Maximum Flow) به دنبال بیشینه کردن مقدار جریان قابل ارسال از یک گره مبدأ (Source) به یک گره مقصد (Sink) با در نظر گرفتن ظرفیت محدود یال ها است.
🔧 الگوریتم های اصلی
الگوریتم فورد-فالکرسون (Ford-Fulkerson): روش افزایشی با استفاده از مسیرهای افزایشی (Augmenting Paths).
الگوریتم ادموندز-کارپ (Edmonds-Karp): پیاده سازی فورد-فالکرسون با BFS که پیچیدگی
\[ O(VE^2) \]دارد.
الگوریتم دینیک (Dinic): با استفاده از سطوح (Layered Network) و پیچیدگی
\[ O(V^2 E) \].
الگوریتم پوش-ری لبل (Push-Relabel): کارآمد برای گراف های بزرگ، پیچیدگی
\[ O(V^3) \].
📐 فرمول بندی ریاضی
\[ \max \quad v \] \[ \text{s.t.} \quad \sum_{j} f_{ij} - \sum_{j} f_{ji} = \begin{cases} v & i = s \\ -v & i = t \\ 0 & \text{otherwise} \end{cases} \] \[ \quad 0 \leq f_{ij} \leq u_{ij} \quad \forall (i,j) \] نویسنده علیرضا گلمکانی
شماره کلید 8788
گزینه ها 
نظرات 0 0 0