class LogicTools::SmallestSumTerm
Class for applying branch and bound for extracting from a product of sums the smallest term of the corresponding sum of products.
Attributes:
product
-
the product to extract the term from.
cur_term
-
the current term.
best_term
-
the best term found.
best_cost
-
the best cost.
deadline
-
time before returning the current best solution.
time
-
initial time.
Public Class Methods
new(product, deadline = Float::INFINITY)
click to toggle source
Creates the solver for a product.
# File lib/logic_tools/minimal_column_covers.rb, line 85 def initialize(product, deadline = Float::INFINITY) @product = product @cur_term = [] # @cur_term = HashCounter.new @best_term = nil @best_cost = @cur_cost = Float::INFINITY @deadline = deadline end
Public Instance Methods
bound(term)
click to toggle source
Bounds a partial term
.
# NOTE: may modify term through uniq! (for performance purpose.) NOTE: It is assumed that term is hash-like
# File lib/logic_tools/minimal_column_covers.rb, line 105 def bound(term) # if Time.now - @time >= @deadline and # @best_cost < Float::INFINITY then # # Time over, force a high cost. # return Float::INFINITY # end if (term.size >= @best_cost) then return term.uniq.size else return term.size end # return term.size end
branch(pi)
click to toggle source
Branch in the branch and bound algorithm.
# File lib/logic_tools/minimal_column_covers.rb, line 144 def branch(pi) # # Start the timer if required. # @time = Time.now if (pi == 0) # # Check the deadline. # if Time.now - @time >= @deadline and # @best_cost < Float::INFINITY then # # Time over, end here. # return @best_term # end # Bound the current term. if (self.bound(@cur_term) < @best_cost) # Better bound, can go on with the current solution. if pi == @product.size then # But this is the end, so update the best term. make_best(@cur_term) else # Still a possible solution, recurse. @product[pi].each do |elem| @cur_term.push(elem) # @cur_term.inc(elem) # solve(pi+1) branch(pi+1) @cur_term.pop # @cur_term.dec(elem) end end end return @best_term end
make_best(term)
click to toggle source
Selects a term
for solution.
# File lib/logic_tools/minimal_column_covers.rb, line 95 def make_best(term) # print "make_best\n" @best_term = term.uniq @best_cost = @best_term.size end
solve()
click to toggle source
Solves the problem using branch and bound.
# File lib/logic_tools/minimal_column_covers.rb, line 120 def solve() # Solve the problem throughly. begin if @deadline != Float::INFINITY then Timeout::timeout(@deadline) { self.branch(0) } else self.branch(0) end rescue Timeout::Error # Time out, is there a solution? # print "Timeout!\n" unless @best_term # No, quickly create one including the first element # of each factor. @best_term = @product.map {|fact| fact[0] } @best_term.uniq! end end return @best_term end