KMC活動ブログ

京大マイコンクラブの活動の様子を紹介します!!

組み合わせ最適化読書会 第5回

KMC2回生のid:ir5です.
組み合わせ最適化の7.2,7.3節を担当しました.


7.1節では「ある1点から任意の点への最短パスを求める問題」を扱ったのですが,7.2節では「任意の2点間の最短パスを求める問題」について扱いました.
扱った手法としては,実行可能ポテンシャルを使ったO(mn+n^2logn)のアルゴリズムと,Floyd-Warshall法についてやりました.
実行可能ポテンシャルを使う方法では,まずBellman-Ford法で実行可能ポテンシャルを求め,そこから簡約コストを用いてDijkstra法をn回行うことで,元のコストとある定数分だけことなる最短パスの長さを求めることができます.
Floyd-Warshall法はO(n^3)のアルゴリズムで,他の方法と比べると少々遅いですが,実装がかなり楽なので自分で使う分には役に立ちます.


7.3節では1辺あたりの平均コストが最小となるような閉路を求める問題を扱いました.
少々トリッキーな感じでなかなか面白かったです.
応用はあまりしらなかったのですが,最小費用流の一部アルゴリズムや,施設配置問題などで使われるそうです.


次回は最大流問題の章に入る予定です.