Stochastic Dynamic Programming

stochastic_dp.rb

require 'ostruct'
require 'benchmark'

def cost(config, perm) 
  last_letter = perm.pop
  current = config[last_letter].time

  # TODO: Further perf improvements can be made by
  # keeping a memoized table of costs for *parts* of the permutation
  # e.g. Take two perms -> ABCDE and FABCDE, FABCDE = F(ABCDE),
  # thus if we had previously memoized ABCDE we could reuse it.
  perm.reverse.each do |key|
    val = config[key]
    current = val.time + ((1 - val.prob) * (current))
  end
  
  return current
end


def brute_force(minions)
  perms = minions.keys.permutation.map(&:join)
  
  min = 1000000000
  current = ''
  perms.each do |perm|
    cost = cost(minions, perm.split(''))
    
    if cost < min
      min = cost
      current = perm
    end
  end
  
  current.split('')
end



def stochastic_dp(minions)
  previous_best = []
  candidate_best = []

  minions.each do |key, minion|
    min = 1000000000
    
    (previous_best.size + 1).times do |i|
      candidate = previous_best.clone
      candidate = candidate.insert(i, key)
      current_cost = cost(minions, candidate.clone)
      
      if current_cost < min
        min = current_cost
        candidate_best = candidate
      end
    end

    previous_best = candidate_best
  end

  previous_best
end


minions = {
  'A' => OpenStruct.new(time: 45, prob: 0.3),
  'B' => OpenStruct.new(time: 5, prob: 0.81),
  'C' => OpenStruct.new(time: 7, prob: 0.32),
  'D' => OpenStruct.new(time: 11, prob: 0.12),
  'E' => OpenStruct.new(time: 26, prob: 0.86),
  'F' => OpenStruct.new(time: 2, prob: 0.35),
  'G' => OpenStruct.new(time: 42, prob: 0.74),
  'H' => OpenStruct.new(time: 23, prob: 0.64),
  'H' => OpenStruct.new(time: 44, prob: 0.323),
  'I' => OpenStruct.new(time: 85, prob: 0.987),
}


Benchmark.bm do |x|
  x.report { puts "Brutes: #{brute_force(minions)}" }
  x.report { puts "SDP: #{stochastic_dp(minions)}" }
end