バリケンのRuby日記 RSSフィード

2006-12-05

[] ルート探索(1)  ルート探索(1) - バリケンのRuby日記 を含むブックマーク はてなブックマーク -  ルート探索(1) - バリケンのRuby日記  ルート探索(1) - バリケンのRuby日記 のブックマークコメント

ある有向グラフがあったときに、スタート地点とゴール地点を与えると、ありうるルート全てをリストアップするようなスクリプトを書いてみるよ。

有向グラフは、ハッシュで与えることにするよ。たとえばA地点からはB地点とD地点へのルートがある場合、

route_map = {
  :A => [:B, :D]
}

と書くことにするよ。ここでは、前提とする有向グラフを次のように定義するよ。

route_map = {
  :A => [:B, :D],
  :B => [:A, :C],
  :C => [:A, :D],
  :D => [:B, :C]
}

図にすると、次のようになるよ。

f:id:muscovyduck:20061206062438p:image

そして、この「ハッシュで表されたルートマップ」と「スタート地点」「ゴール地点」とを引数として与えると、ありうるルートをすべて出力するようなメソッドを実装してみるよ。

route_map = {
  :A => [:B, :D],
  :B => [:A, :C],
  :C => [:A, :D],
  :D => [:B, :C]
}

def route_combination (map, start, goal, queue=[])
  queue1 = queue.clone.push(start)
  map[start].each{|dist|
    if queue1.include?(dist)
      next
    elsif dist != goal
      route_combination(map, dist, goal, queue1)
    else
      p queue1.clone.push(goal)
    end
  }
end

route_combination(route_map, :B, :D)

実行結果だよ。ここでは試しにB地点からD地点までのルートを出力するようにしてみたよ。

[:B, :A, :D]
[:B, :C, :A, :D]
[:B, :C, :D]

うーん、でもroute_combinationメソッドの定義の中でpメソッドのような副作用のあるメソッドを使っているのが気持ち悪いね。副作用で出力しないで「ありうるルートすべてを配列で返す」ようにしてから別途出力するようにすればいいんだけど、どうすればいいかな?