How to retrieve policy after Dynamic Programming?

Question

I'm working on a simple resource allocation problem, that I'm solving using backward DP. The full code is at: https://codereview.stackexchange.com/questions/123641/allocating-a-resource

It works fine, but I'm a bit puzzled on how to retrieve the optimal policy once the optimisation is done. I use a memoization decorator but I'm clueless as to how to get the optimal policy out of it at the end. (The policy would be a series of 1,0 as describing when to allocate and when not to.)

def memoize(f):
 cache = {}
 def memoizedFunction(*args):
 if args not in cache:
 cache[args] = f(*args)
 return cache[args]
 memoizedFunction.cache = cache
 return memoizedFunction

In an alternative effort I use:

def record(D,key,item):
 """Records the value of item in the dictionary d with k"""
 if key in D.keys():
 D[key].append(item)
 else:
 D[key] = [item]
 return D

And in the DP:

 if v == no_pump:
 pos = 0
 else:
 pos = 1
 record(X,i+1,pos)

My hunch is that if I can create a new dictionary (X) for each policy, and record the optimum value up to its execution, it could work. But I don't know how to do that. Also it seams quite inefficient.

To clarify: Forwards methods, or converting it into a graph aren't suitable as the whole problem will be converted into a stochastic control problem later.

Answer 1

Right now the function you memoize simply returns the score the best solution. Change is so that it returns a tuple of the first step of the best solution and the score. Something like:

@memoize
def score(...)
 _, zero_score = score(...)
 _, one_score = score(...)
 if zero_score < one_score:
 return 0, zero_score
 else:
 return 1, one_score

Now, to find out the next step, you simply have to call score and it will tell you the next step and the score.

Answer 2

Move your memoizedFunction.cache dictionary out of the function memoize function so it is at a global level. Then you will be able to query it after the optimization has run.