Comment by jakewins
3 years ago
I think you would enjoy applying dynamic programming to this problem!
I have a simple example, starting from a “generate all possible combinations” python function, here: https://tech.davis-hansson.com/p/price-wars.html
Or the Dijkstra's algorithm, which is a form of dynamic programming.
To solve the superoptimization problem, imagine every possible memory state as a node in a graph, and each instruction as an edge between two states, the superoptimized program is the shortest path between the starting state and the end state.
You can even use A* which is very similar to Dijkstra's algorithm, but with a sense of direction, materialized by a heuristic function that estimates how close we are to the goal. Here, a simple heuristic could be the number of memory locations that are different to the goal divided by two, that because each instruction changes at most two memory locations.
Of course, dynamic programming is a space-time trade-off, so memory consumption is something to consider.
Why did you use the term dynamic programming programming when referring to the memorization part? The term of art, dynamic programming, is at play here but refers to the initial design of breaking up the problem into recursive sub-problems.
Oh! I'd always imagined it was the combination of the recursive breakdown and the memoization together, but you're right it seems the DP part is just the recursive bit. Thanks for pointing this out.