CMP.3:4.3 - Construct the dependency graph and an evaluation order
For each distinct subproblem, identify which other results are needed to obtain its answer. Draw an arrow from a prerequisite to its consumer. Count distinct states and the work needed to combine each state’s prerequisites and alternatives; the number of states alone does not establish the total cost.
If dependencies are acyclic, two standard constructions are available:
| Construction | How it obtains results | Useful condition |
|---|---|---|
| Memoized evaluation | On a call, return a completed stored answer if present; otherwise obtain prerequisites, compute the result and store it. | Only part of the possible graph is expected to be reached. |
| Ordered table evaluation | Obtain a topological order, in which prerequisites precede their consumers, and compute states in that order. | The needed state region and dependency order are known and regular access helps. |
These methods can be combined by regions. Independent ready states can also be evaluated concurrently, provided the sharing and combination operations preserve the result.
A directed cycle prevents this simple ordering. Determine whether it is an erroneous recursive dependency, a finite-horizon problem missing its horizon coordinate, or a genuine fixed-point problem. For a genuine cycle, provide the iteration, ordering or other solving method and its result conditions. Adding memoization alone does not solve mutually dependent equations.