いっときほどほどに流行ったおねえさんの動画の栞をいただきました．知り合いが関係者です． ぽぽぽぽーんとか選挙とかと同種の流行り方だったと思うのですが*1、大ブームに至らなかったのは、キャラクターの固有名称も不思議な歌も無かったからかなと推測し…

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

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

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

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

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

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