ディニッツ法

ウィキペディア

ディニッツ法

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2025/03/03 09:50 UTC 版)

ディニッツ法（ディニッツほう、英: Dinic's algorithm, Dinitz's algorithm）とは、1970年にイスラエル（元はソ連）のコンピュータ科学者のイェフィム・ディニッツにより提案されたネットワークフローにおける最大流問題に対する強多項式時間アルゴリズムである。ディニッツ法は計算量 $O(|V|^{2}|E|)$

ブロッキングフローは以下の路から構成される:

1. フロー4を持つ路: $\{s,1,3,t\}$

   ブロッキングフローは以下の路から構成される:

   1. フロー5を持つ路: $\{s,2,4,3,t\}$

      $G_{f}$

      Optimization computes maxima and minima.

非線形（制約付き）

凸最適化

組合せ最適化

メタヒューリスティクス

• 進化的アルゴリズム（進化戦略・遺伝的アルゴリズム）
• 山登り法
• 局所探索法
• 焼きなまし法
• タブーサーチ
• 群知能
• ベイスンホッピング法
• 量子焼きなまし法

• カテゴリ（最適化 • アルゴリズム） • ソフトウェア