Algorithm for finding optimal branch points I'm developing software to run variations on a base process flow (see #1, below). A user specifies in a text file what steps in the process to modify. Because each step takes a long time to run, I'd like to minimize the amount of duplicate processing required. For example, if variations occur at step B, I could run step A one for all results before "branching" at step B (see #2 below). Similarly, I could branch again at step D if additional variations on step D are indicated (see #3 below).

1) Base Process:

input --&gt; A --&gt; B --&gt; C --&gt; D --&gt; E --&gt; result


2) Modification of Step B:

input --&gt; A --&gt; B1 --&gt; C --&gt; D --&gt; E --&gt; result1
                B2 --&gt; C --&gt; D --&gt; E --&gt; result2


3) Modification of Steps B and D:

input --&gt; A --&gt; B1 --&gt; C --&gt; D1 --&gt; E --&gt; result1
                             D2 --&gt; E --&gt; result2
                B2 --&gt; C --&gt; D1 --&gt; E --&gt; result3
                             D2 --&gt; E --&gt; result4


Is there a simple algorithm to determine the the common process steps and the branch points as in #3 given a base flow as in #1 and a list of steps to change, e.g.

Variation  StepB  StepD
   1         1      1
   2         1      2
   3         2      1
   4         2      2


The above example is simple but there could be hundreds of variations modifying dozens of different steps in actual usage.
If whatever happens after $B$ depends on that, you can't "reuse" any runs after a modified $B$. So the tree-like scheduling is really the best that can be done.

If the later steps are independent of (some) of the previous steps, things get more interesting... but that presumes you have a completely reliable way of determining that. The simplest way to get the most efficient runs without too much extra work in this case would be just to store away the results of all runs, and instead of running any of them first check if the result is already stored (memoisation). Might need to supplement with some logic to clean up (delete results that won't be used ever again, or use some heuristic to delete them).