I am relatively new to Ruby and am trying to get a handle on making my code more Ruby-esque. At the same time I am experimenting with the branch and bound algorithm to solve a problem that I outline in this blog post. I would also welcome any feedback on the quality of my implementation. The full source code is on my github here, but here is the code for the branch bound class:
require './widget' require './requirements' require 'benchmark' class BranchBoundSearch @best_score=nil @best_combos=[] def initialize(scorer,main_requirement_label,all_possible) @scorer=scorer @main_requirement_label=main_requirement_label @all_possible=all_possible end #Given a widget_array first calculate it's score, and add it as a branch in the #list of branches based on the quality of it's score. Better scores are first. #Branches that do not meet the size requirement are not added to the branches #array. This effectively kills that branch. def add_branch(widget_array,branches) [email protected]_score_hash(widget_array) [email protected]_total_score(score_hash) added=false branches_index=0 if score_hash[@main_requirement_label] >= 0 while not added and branches_index < branches.length do if @scorer.get_better_score(score,branches[branches_index][1]) >= 0 branches.insert(branches_index,[score_hash,score,widget_array]) added=true end branches_index+=1 end if not added branches.push([score_hash,score,widget_array]) end end end #Branch and bound recursive search. Provided an in array which represents the #node which will be branched off of. Roughly, the function first creates a list #of potential branches which are ordered by the quality of their score. #Potential branches are then looped through, if a potential branch is viable the #function is called again with it as the root node. This continues until #exhaustion of all possiblities. def branch_and_bound(in_array) branches=[] @all_possible.each do |widget| branch_array=in_array+[widget] add_branch(branch_array,branches) end branches.each do |branch| score_hash=branch[0] score=branch[1] widget_array=branch[2] [email protected]_better_score(score,@best_score) if score_comparison == 0 @best_combos.push(widget_array) continue_branch_investigation=true elsif score_comparison == 1 @best_combos=[widget_array] @best_score=score continue_branch_investigation=true elsif score > 0 continue_branch_investigation=true end if continue_branch_investigation branch_and_bound(widget_array) end end end def get_best_score() return @best_score,@best_combos end end
I'm also concerned about this specific code block:
best_score_90=nil best_set_90=[] best_score_90_bb=nil best_set_90_bb=[] best_score_400=nil best_set_400=[] best_score_400_bb=nil best_set_400_bb=[] time=Benchmark.bm(7) do |x| x.report("brute[90]:") do scorer=Scorer.new(requirements_90,:size) brute=BruteSearch.new(scorer,:size) possible_combos=brute.enumerate_possible([],all_widgets.dup) best_score_90,best_set_90=brute.get_best_score end x.report("brute[400]:") do scorer=Scorer.new(requirements_400,:size) brute=BruteSearch.new(scorer,:size) possible_combos=brute.enumerate_possible([],all_widgets.dup) best_score_400,best_set_400=brute.get_best_score end x.report("b&b[90]:") do scorer=Scorer.new(requirements_90,:size) bb=BranchBoundSearch.new(scorer,:size,all_widgets) bb.branch_and_bound([]) best_score_90_bb,best_set_90_bb=bb.get_best_score end x.report("b&b[400]:") do scorer=Scorer.new(requirements_400,:size) bb=BranchBoundSearch.new(scorer,:size,all_widgets) bb.branch_and_bound([]) best_score_400_bb,best_set_400_bb=bb.get_best_score end end puts "Best set [90] brute: "+ widget_array_to_s(best_set_90) puts "Score[90] brute: "+best_score_90.to_s
Thanks for the help!
