なんとな~くしあわせ?の日記

JavaとかAWSの設定とかをメモする技術ブログ

AOJ - ALDS1_12_A (プリム法) を解いてみた

AOJ - ALDS1_12は、重み付きのグラフアルゴリズムです。

最小全域木| アルゴリズムとデータ構造 | Aizu Online Judge

問題設定

最小全域木というのは、

  • 重みがある経路前提
  • 閉路がない

グラフにおいて、すべてのノードを一度回るのに最も少ないコストを見つけるための方法です。詳しいところはWikipediaをよめばよろし → 全域木 - Wikipedia

すべてのノードを回るとは言っても、一筆書きは求められていません。一度訪問したノードからは再出発できます。

グラフをGraphvizでビジュアル化する

文章だとわからんので、グラフをGraphvizでビジュアル化してみました。

AOJ ALDS1_12_Aのグラフを図示

最小全域木って要は下みたいな地図をすべて訪問する最小時間を求める!みたいな問題なんですね、そう考えるとめっちゃ有用性感じるでしょ?

例えば丸の中に数字があるところが営業先で、丸と線をつなぐ数値が移動時間だと考えるとイメージが具体的になる。 営業マンはできるだけ多くの得意先を最小の時間で回る経路を知りたい。スタート地点は①。

f:id:panzer-jagdironscrap1:20171029134300p:plain

実際、この経路を目でたどるのは簡単*1

f:id:panzer-jagdironscrap1:20171029134732p:plain

アルゴリズム

疑似コード

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 → ノードの番号(1〜)
    • :c → 訪問状況を3値(=3色)で
    • :d → ノード間の距離の記録
    • :p → 一つ前に探索したノードの記録
INF  = 999999999
Node = Struct.new(:u, :d, :c, :p)

*1:経路のノードが膨大になると無理になってくるが