Comment by GuB-42

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.