RPCFN: Short Circuit (#3)の結果がサッパリだったのでやり直した
ぜんぜんダメだったw
ダイクストラ法のことがぜんぜん理解できてなかったwwwイカンなー
Aldric Giacomoniさんのコードを参考にしてやり直した。ほぼパクリであるとも言う。。
コード
class ShortCircuit INFINITY = 1.0/0 def initialize(circuit, source, dist) @circuit = circuit @source = source @dist = dist @nodes = @circuit.keys @distance = {} @previous = {} @nodes.each do |i| @distance[i] = INFINITY @previous[i] = -1 end @distance[@source] = 0 @searched = false @shortest_path = [] @redundant_registors = [] @lowest_load = 0 end def shortest_path return @shortest_path unless @shortest_path.empty? dijkstra unless @searched paths = [] current = @dist paths << current until [-1,@source].include? current paths << @previous[current] current = @previous[current] end @shortest_path = paths.reverse end def redundant_registors return @redundant_registors unless @redundant_registors.empty? shortest_path if @shortest_path.empty? all_paths = [] @circuit.each do |e| e[1].each do |k,v| all_paths << [e[0], k, v] if e[0] < k end end paths = all_paths.clone paths.each do |source, dist, distance| shortest_path.each_with_index do |e,i| if (source == e && dist == shortest_path[i+1]) || (dist == e && source == shortest_path[i+1]) paths.delete [source,dist,distance] end end end @redundant_registors = paths puts (all_paths - @redundant_registors).map{|source, dist, distance| distance}.inspect @lowest_load = (all_paths - @redundant_registors).map{|source, dist, distance| distance}.inject(0){|sum, distance| sum + distance} @redundant_registors end def lowest_load redundant_registors if @redundant_registors.empty? @lowest_load end def dijkstra unsolved_nodes = @nodes.clone while (unsolved_nodes.size > 0) current_node = nil; unsolved_nodes.each do |min| if (not current_node) or (@distance[min] and @distance[min] < @distance[current_node]) current_node = min end end if (@distance[current_node] == INFINITY) break end unsolved_nodes.delete current_node @circuit[current_node].keys.each do |v| alternative_distance = @distance[current_node] + @circuit[current_node][v] if (alternative_distance < @distance[v]) @distance[v] = alternative_distance @previous[v] = current_node end end end @searched = true end end
テストコード
require 'test/unit' unless defined? $ZENTEST and $ZENTEST require 'lib/short_circuit' class TestShortCircuit < Test::Unit::TestCase def setup @circuit = { 'A' => { 'B' => 50, 'D' => 150 }, 'B' => { 'E' => 250, 'A' =>50, 'C' => 250 }, 'C' => { 'B' => 250, 'E' => 350, 'D' => 50, 'F' => 100 }, 'D' => { 'A' => 150, 'C' => 50, 'F' => 400 }, 'E' => { 'B' => 250, 'C' => 350, 'G' => 200 }, 'F' => { 'G' => 100, 'D' => 400, 'C' => 100 }, 'G' => { 'E' => 200, 'F' => 100 } } @my_circuit = ShortCircuit.new(@circuit, 'A', 'G') end def test_Infinity_is_infinity assert_equal(1.0/0, ShortCircuit::INFINITY) end def test_get_shortest_path assert_equal(["A", "D", "C", "F", "G"], @my_circuit.shortest_path) end def test_get_redundant_resistors expected_redundant_resistors = [ ["A", "B", 50], ["B", "C", 250], ["B", "E", 250], ["C", "E", 350], ["D", "F", 400], ["E", "G", 200] ] assert_equal(expected_redundant_resistors, @my_circuit.redundant_registors) end def test_lowest_load assert_equal(400, @my_circuit.lowest_load) end end
テスト結果
# ruby test/test_short_circuit.rb Loaded suite test/test_short_circuit Started .... Finished in 0.001087 seconds. 4 tests, 4 assertions, 0 failures, 0 errors