AtCoder - AtCoder Beginner Contest 012 (バスと避けられない運命) を解いてみた
解法
Rubyによる解答 TLE
アルゴリズムは正しそうですが11個のテストケースでTLEしてしまいました。
Submission #1725365 - AtCoder Beginner Contest 012 | AtCoder
D言語による解答 AC!
しかしそんなことでは諦めない。もちろん俺らは抵抗するで？拳で*1
Submission #1728053 - AtCoder Beginner Contest 012 | AtCoder
AOJ - ALDS1_12_B (ダイクストラ法) を解いてみた
AOJ - ALDS1_12は、重み付きのグラフアルゴリズムです。
最短経路 ダイクストラ法 | アルゴリズムとデータ構造 | Aizu Online Judge
この問題が解けるとAtCoderの以下の問題も解けます
問題設定
最短経路問題というのは、２つのノード間を結ぶ経路の中で重みが最小の経路を求める最適化問題のことらしい。
詳しいところはWikipediaをよめばよろし → 最短経路問題 - Wikipedia
一筆書きは求められていません。一度訪問したノードからは再出発できます。
最短経路問題の分類とアルゴリズムの使いどころ
今回はWikipediaの記述が役に立っています。最短経路問題は条件ごとに複数のアルゴリズムが適用されるみたいです。
Wikipediaの記述を整理すると…
[最短経路問題] │ ├── [ 2頂点対最短経路問題 ] (単一始点と同じロジックで対応できる) │ ├── [ 単一始点最短経路問題（SSSP） ] │ ├── [ 辺の重みなし有向グラフ ] → 幅優先探索 │ ├── [ 辺の重みが非負値の有向グラフ ] → ダイクストラ法 │ └── [ 辺の重みが任意の実数の有向グラフ ] → ベルマン-フォード法 │ └── [ 全点対最短経路問題 ] └── ワーシャル-フロイド法
チラチラ数学の論文っぽい参照が散見されますが、競プロのために論文は読まんでいいはず…。とにもかくにも、最短経路を求めるときに辺の重みがマイナスじゃなけりゃダイクストラ法を使えばいいのです。あと、もう一つダイクストラ法には制約があって、有向グラフ（辺が一方通行）のものしか適用できないようです。
AOJの問題の注意
アルゴリズム
疑似コード
Wikipediaの疑似コードを見ると、ソースの内容が前回のプリム法と似ていることに気付くかもしれません。プリム法ではノードの距離の比較の際、隣接行列の値と現在の距離だけを比較していましたが、ダイクストラ法は隣接行列の値と現在もっているノードの距離と現在の距離を比較します。
再びヨークカレッジ ペンシルバニア校/York College of Pennsylvaniaのレジェメを見る。
Lecture 22: Single Source Shortest Paths - Dijkstra's Algorithm
DIJKSTRA(G,w,s) INITIALIZE-SINGLE-SOURCE(G,s) S = ∅ Q = G.V while Q ≠ ∅ u = EXTRACT-MIN(Q) S = S ∪ {u} for each vertex v ∈ G.Adj[u] RELAX(u,v,w) # ↑ ここの関数は単に分割されとるだけ # 一番下のRELAX関数をここにコピペするとプリム法とほぼ同じ INITIALIZE-SINGLE-SOURCE(G,s) for each vertex v ∈ G.V v.d = ∞ v.pi = NIL s.d = 0 RELAX(u,v,w) if v.d > u.d + w(u,v) v.d = u.d + w(u,v) v.pi = u
*1:統一してくれ…
AOJ - ALDS1_12_A (プリム法) を解いてみた
AOJ - ALDS1_12は、重み付きのグラフアルゴリズムです。
最小全域木| アルゴリズムとデータ構造 | Aizu Online Judge
問題設定
最小全域木というのは、
- 重みがある経路前提
- 閉路がない
グラフにおいて、すべてのノードを一度回るのに最も少ないコストを見つけるための方法です。詳しいところはWikipediaをよめばよろし → 全域木 - Wikipedia
すべてのノードを回るとは言っても、一筆書きは求められていません。一度訪問したノードからは再出発できます。
アルゴリズム
疑似コード
Wikipediaの疑似コードは数学寄りで分かりにくかったです。
それに引き換え、再び参照したサイト from ヨークカレッジ ペンシルバニア校/York College of Pennsylvaniaはいい感じです。また疑似コードを拝借します。
PRIM(G,w,r)
for each u ∈ G.V
u.key = ∞
u.pi = NIL
r.key = 0
Q = G.V
while Q ≠ ∅
u = EXTRACT-MIN(Q)
for each v ∈ G.Adj[u]
if v ∈ Q and w(u,v) < v.key
v.pi = u
v.key = w(u,v)
Lecture 20: Minimum Spanning Trees - Prim's Algorithm
ただ、どちらも求めた最小距離をどうやって合計するかが書かれていない。
コードの工夫など
- INFの表現
到達できないノード、もしくは未発見のノードへの距離は無限とあらわすのが一般的なようで、とりあえず大きい数に置いておいた
- ノードが含む要素
- :u → ノードの番号（１〜）
- :c → 訪問状況を３値（＝３色）で
- :d → ノード間の距離の記録
- :p → 一つ前に探索したノードの記録
INF = 999999999 Node = Struct.new(:u, :d, :c, :p)
*1:経路のノードが膨大になると無理になってくるが
