We have already seen where a good initial guess will give a very substantial performance increase in one case, but what about the general case. I wrote three different initial guessers, one that greedily picks the lowest cost for each task, one that tries to distribute the tasks evenly across the three processors and one that randomly places the tasks on the three processors. The initial guess that is used is the lowest cost that any one of these guess gives.
This plot shows the running times for various length input sizes
comparing using a good initial guess and not using a guess at all.
The vertical position of the boxes ( 
) are the number nodes
examined by the program without an initial guess and the pluses (+)
are the number examined by the program with a good guess. It is not
apparent from this plot that there is any performance gain from the
initial guess. In fact this plot is a good argument that there is no
speedup associated with the initial guess in the general case.