Last active
November 20, 2017 07:49
-
-
Save krone/d8f224c3e37fb0c419106bdb33b718f8 to your computer and use it in GitHub Desktop.
Stochastic Dynamic Programming
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| 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 |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment