情報科学と人工知能のノート

初等的な知識から最新論文の解説まで色々集めていきます.備忘録兼用.

最小シュタイナー木問題

Chu-Liu/Edmonds のアルゴリズム

有向最小全域木問題を解くアルゴリズム.1965 年に Chu と Liu が提案し、それとは独立に Edmonds が 1967 年に提案したらしいです. 定義 入力:グラフ 、コスト関数 、根 . 解: を根とした有向全域木.すなわち から全ての頂点への経路が存在する有向木 …

最小全域木問題

最小木問題、あるいはカタカナ英語で最小スパニング木問題、最小スパニングツリー問題とも. 例 ある電力会社が全国に電気を送り届けるべく、日本中に電線を張り巡らせようと考えています.発電所と接続されていない家が無いようにもれなく電線を張り巡らせ…