「最小木問題」の版間の差分
ナビゲーションに移動
検索に移動
| 2行目: | 2行目: | ||
各枝に重みの与えられた(無向)グラフにおいて, そのグラフ上に存在する全張木(全域木)の中で枝の重みの総和が最小になるものを見出す組合せ最適化問題. それ自身も多くの応用例をもつが, より複雑な問題の子問題として利用されることも多い. クラスカル法やプリム法といった貪欲アルゴリズムにより多項式時間で解くことが可能である. | 各枝に重みの与えられた(無向)グラフにおいて, そのグラフ上に存在する全張木(全域木)の中で枝の重みの総和が最小になるものを見出す組合せ最適化問題. それ自身も多くの応用例をもつが, より複雑な問題の子問題として利用されることも多い. クラスカル法やプリム法といった貪欲アルゴリズムにより多項式時間で解くことが可能である. | ||
| + | |||
| + | 詳しくは[[《最小木問題》|基礎編：最小木問題]]を参照. | ||
2007年8月8日 (水) 20:52時点における版
【さいしょうきもんだい (minimum spanning tree problem)】
各枝に重みの与えられた(無向)グラフにおいて, そのグラフ上に存在する全張木(全域木)の中で枝の重みの総和が最小になるものを見出す組合せ最適化問題. それ自身も多くの応用例をもつが, より複雑な問題の子問題として利用されることも多い. クラスカル法やプリム法といった貪欲アルゴリズムにより多項式時間で解くことが可能である.
詳しくは基礎編：最小木問題を参照.