せかいや

いまいるここを、おもしろく http://sekai-in-the-box.appspot.com/

【Ruby】【アルゴリズム】グラフ構造。最短経路を求める。ダイクストラ法(うそものVer)。

宣言通り、1週間で終わりました

プログラミングの宝箱 アルゴリズムとデータ構造 第2版

プログラミングの宝箱 アルゴリズムとデータ構造 第2版


 
っていってもこの本、少し調べていたらずいぶん酷評されていた。。

今の若い者には,このくらい軽くて中身の薄い本じゃないと売れないのかもしれない.ライトな娯楽小説ならまだ分かるけど,ライトな専門書って一体なんなんだよ.ライトな専門家を目指すためのライト解説書?それって要するに素人だよね?

http://d.hatena.ne.jp/JavaBlack/20110923/p1#20110923fn1

ぐは。。。
まあそうなんだろうけどね。
でもなあ。

自分は数学科出身なんだけれど、その空気を思い出すなあ。
学部で出たのも、この空気に馴染めなかったからだと思う。


でもいいんだ。
凡人は凡人の務めを果たすのみ。
先ばっかり見て諦めてたら、つまんないもんね。

 
 

最短経路問題とは

路線図があって、A駅からB駅まで行く最短の方法を見つける

1時間半で完成。
完成後、リファクタリング(クラスメソッド化)に30分くらいかかった。


 

ポイント

Ruby独特の、
「メソッドで最後に評価された式の値が返り値になる」が特に再帰を書くときに混乱してしまう。

というか、最初のころ再帰コードが上手くかけなかったのは、この癖に引きずられていたからだと思う。
もう大丈夫。

def self._min(timeinfo, goal)
  return timeinfo if timeinfo[goal].decision == 1 ←帰り値を返して終了
  ok = 0
  timeinfo.each{ |info| ok += info.decision }
  return if ok >= timeinfo.length   ←処理条件を満たしているから以下の処理をしない
 ・・・                   (と言う意味でreturn nil)

 

コード

(注)このコードはダイクストラ法ではありません。
ダイクストラ法は「任意の未確定ノードのうち最小コストを選択する」アルゴリズム(※1)ですが、
このコードは隣接ノードを再帰的に追うアルゴリズムです。
本来は無限ループ内で上記の(※1)を実行し、未確定ノードがなくなった時点でループを抜けます。

正しいダイクストラ法はこちらを参照下さい↓
http://sekai.hateblo.jp/entry/2013/10/08/211955

このコードを残す意味は、、、自己不満足以外の何者でもないです。
ごめんなさい。。
(10月9日追記)
 

class TimeInfo
  attr_accessor :time, :decision, :parent_idx
  def initialize(time, decision, parent_idx)
    @time = time
    @decision = decision
    @parent_idx = parent_idx
  end
end

class Tokyu
  @@stations = ["yokohama","musashikosugi","shinagawa","shibuya","shinbashi","tameikesannou", "saihate1", "saihate2"]
  @@adjacency = [
    [0,12,28,0,0,0,0,0],
    [12,0,10,13,0,0,0,0],
    [28,10,0,11,7,0,0,0],
    [0,13,11,0,0,9,0,0],
    [0,0,7,0,0,4,0,0],
    [0,0,0,9,4,0,0,0],
    [0,0,0,0,0,0,0,90],
    [0,0,0,0,0,0,90,0],
  ]
  #路線状態表示用
  def self.debug
    @@stations.each_with_index do |station, idx|
      p station
        @@adjacency[idx].each_with_index do |time, jdx|
          p "->#{@@stations[jdx]} : #{time}" if time != 0
        end
      p "--------"
    end
  end

  #結果表示用
  def self.show(result)
    timeinfo = result[:timeinfo]
    goal = result[:goal]
    p timeinfo[goal].time
    tmp = timeinfo[goal]
    while tmp.parent_idx != -1
      p " <- #{@@stations[tmp.parent_idx]} <-"
      tmp = timeinfo[tmp.parent_idx]
    end
  end

  #隣り合う駅を取得
  def self.next_trains_idx(idx)
    result = []
    @@adjacency[idx].each_with_index do |time, jdx|
      result << jdx if time != 0
    end
    result
  end
  def self.min_way(start_station, end_station)
    start = @@stations.index(start_station) ; goal = @@stations.index(end_station)
    timeinfo = []
    @@stations.length.times do |i|
      timeinfo << TimeInfo.new(-1, 0, -1)
    end
    timeinfo[start] =  TimeInfo.new(0, 1, -1)
    tmp = _min(timeinfo, goal)
    raise "tadoritukenai" if tmp[goal].time == -1
    result = {}
    result[:timeinfo] = tmp
    result[:goal] = goal
    result
  end

  def self._min(timeinfo, goal)
    return timeinfo if timeinfo[goal].decision == 1
    ok = 0
    timeinfo.each{|info| ok += info.decision}
    return if ok >= timeinfo.length
    timeinfo.each_with_index do |obj, i|
      if obj.decision == 1
        next_trains_idx(i).each do |j|
          if timeinfo[j].decision == 0
            if (timeinfo[j].time == -1 || timeinfo[j].time > timeinfo[i].time + @@adjacency[i][j])
              timeinfo[j].time =timeinfo[i].time + @@adjacency[i][j]
              timeinfo[j].parent_idx = i
            end
            next_trains_idx(j).each do |k|
              if timeinfo[k].decision == 0
                if (timeinfo[k].time == -1 || timeinfo[k].time > timeinfo[j].time + @@adjacency[j][k])
                  timeinfo[k].time =timeinfo[j].time + @@adjacency[j][k]
                  timeinfo[k].parent_idx = j
                end
              end
            end
            #自分から延びる全ての辺を処理すれば確定となる
            timeinfo[j].decision = 1
            _min(timeinfo, goal)
          end
        end
      end
    end
    timeinfo
  end
end

#路線図の状態
#Tokyu.debug

#1番目の駅に隣り合う駅を取得
#p Tokyu.next_trains_idx(1)

answer = Tokyu.min_way("shibuya","yokohama")
Tokyu.show(answer)

#参考
p answer

■実行結果

25
" <- musashikosugi <-"
" <- shibuya <-"
{:timeinfo=>[#<TimeInfo:0x2df3780 @time=25, @decision=1, @parent_idx=1>, #<TimeInfo:0x2df3768 @time=13, @decision=1, @parent_idx=3>, #<TimeInfo:0x2df3750 @time=23, @decision=1, @parent_idx=1>, #<TimeInfo:0x2df36c0 @time=0, @decision=1, @parent_idx=-1>, #<TimeInfo:0x2df3720 @time=30, @decision=1, @parent_idx=2>, #<TimeInfo:0x2df3708 @time=9, @decision=1, @parent_idx=3>, #<TimeInfo:0x2df36f0 @time=-1, @decision=0, @parent_idx=-1>, #<TimeInfo:0x2df36d8 @time=-1, @decision=0, @parent_idx=-1>], :goal=>0}


だんだんアルゴリズムが分かってきたぞ。