【Ruby】【アルゴリズム】グラフ構造。最短経路を求める。ダイクストラ法(うそものVer)。
宣言通り、1週間で終わりました↓
- 作者: 紀平拓男,春日伸弥
- 出版社/メーカー: ソフトバンククリエイティブ
- 発売日: 2011/03/30
- メディア: 単行本
- 購入: 15人 クリック: 255回
- この商品を含むブログ (31件) を見る
っていってもこの本、少し調べていたらずいぶん酷評されていた。。
今の若い者には,このくらい軽くて中身の薄い本じゃないと売れないのかもしれない.ライトな娯楽小説ならまだ分かるけど,ライトな専門書って一体なんなんだよ.ライトな専門家を目指すためのライト解説書?それって要するに素人だよね?
http://d.hatena.ne.jp/JavaBlack/20110923/p1#20110923fn1
ぐは。。。
まあそうなんだろうけどね。
でもなあ。
自分は数学科出身なんだけれど、その空気を思い出すなあ。
学部で出たのも、この空気に馴染めなかったからだと思う。
でもいいんだ。
凡人は凡人の務めを果たすのみ。
先ばっかり見て諦めてたら、つまんないもんね。
ポイント
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}
だんだんアルゴリズムが分かってきたぞ。