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

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

グラフ理論

Minty 1960 の定理 3.1

Korte と Vygen の「組み合わせ最適化」を読んでいたら、突然以下のような補題が出てきました(以下は第二版 23 ページからの引用). 補題 2.6 (Minty [1960]) を有向グラフとし, とする. は黒で彩色され,残りの各辺は赤,黒あるいは緑のいずれかで彩色…

深さ優先探索

深さ優先探索はグラフを探索するためのアルゴリズムです*1.注意書きの通り、細かいことを言うと面倒なのですが、以下ではグラフ上の二頂点間の連結性を判定するアルゴリズムだと思って説明を進めましょう. 定義 入力:グラフ 、始点 、終点 . 出力: と …

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

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

最小全域木問題

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

ベルマン-フォード法

最短経路問題を解くアルゴリズム.ベルマンとフォードが共著の論文で一つのアルゴリズムを提案したわけじゃないようなのですが、なんでベルマン-フォード法って呼ぶのでしょうね?*1 定義 入力:グラフ 、コスト関数 、始点 、終点 . 解:始点から終点への…

ダイクストラ法

グラフ上の最短経路問題を解くアルゴリズム.エドガー・ダイクストラが 1959 年出版の論文で提案. 入出力 入力:グラフ 、コスト関数 、始点 、終点 . 解:始点から終点への経路.すなわち、次を満たす頂点の列 (ただし ). 、 、 任意の について . 解…

グラフ理論における最短経路問題

あるいは最短経路探索問題. 定義 入力:グラフ 、コスト関数 、始点 、終点 . 解:始点から終点への経路.すなわち、次を満たす頂点と辺の列 (ただし ). 、 、 任意の について . 解のコスト:経路に含まれる各辺のコストの和. 出力:コスト最小の解.…