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

2006-12-07

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

d:id:ha-tanさんからトラックバックをいただきました。ありがとうございます!

というわけで、この間の続きで副作用のないものを作ってみたよ。手続きの外側にもうひとつ手続きを定義して、そこでaccumulaterを使って結果を蓄積していけばいいんだね。まずはProcオブジェクトを使うものから。

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

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

p route_combination(route_map, :B, :D)

つぎに、メソッド定義のネストを使ったもの。

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

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

p route_combination(route_map, :B, :D)

実行結果だよ。

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

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

せっかく配列で結果が得られるようになったから、ルートに重み付けをして、重み付けに応じて結果をソートして出力するようにしてみるよ。

たとえば、次の図のような重み付けをするとして、

f:id:muscovyduck:20061207220642p:image

次のように、ハッシュで重み付けを表してみるよ。

route_weight = {
  [:A, :B] => 37,
  [:A, :D] => 20,
  [:B, :A] => 23,
  [:B, :C] =>  8,
  [:C, :A] => 14,
  [:C, :D] =>  5,
  [:D, :B] => 32,
  [:D, :C] => 41
}

あとは算出されたルートに対して、それぞれの重み付けを加算してあげればよさそうだね。

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

route_weight = {
  [:A, :B] => 37,
  [:A, :D] => 20,
  [:B, :A] => 23,
  [:B, :C] =>  8,
  [:C, :A] => 14,
  [:C, :D] =>  5,
  [:D, :B] => 32,
  [:D, :C] => 41
}

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

p route_combination(route_map, :B, :D).map{|item|
  total = 0
  (item.size - 1).times{|i|
    total += route_weight[[item[i], item[i+1]]]
  }
  [item, total]
}.sort_by{|item| item[1] }

実行結果だよ。

[[[:B, :C, :D], 13], [[:B, :C, :A, :D], 42], [[:B, :A, :D], 43]]

これで、B地点からD地点には「B→C→D」と行くのが一番早い(重みが13なので、この中では一番少ない)ことがわかるね。

トラックバック - http://rubyist.g.hatena.ne.jp/muscovyduck/20061207