The spanning problem with symmetric
lengths can be readily optimized by a greedy algorithm. One
method is called *Prim's
Algorithm *described elsewhere on this site. For the
minimal spanning tree, the greedy approach constructs a solution
by starting from the root node and adding the arc with the smallest
length to obtain a tree with two nodes. The algorithm then proceeds
by finding the arc with the smallest length that extends the
current tree to one additional node. The process continues until
*n*-1 arcs are selected and all nodes are connected.
The maximal spanning tree is constructed in a similar fashion,
but the arc with the greatest length is added at each step.
The add-in implements this method when *Greedy *is selected
from the *Search* dialog. The results for the example
are below. There is no point using using an improvement step,
since the greedy approach finds the optimal solution. There
are 58 evaluations required for the greedy approach. To find
the node to add to the tree in each step, the program evaluates
every possible addition. Although *Prim's *algorithm
can be performed with many fewer computations we use the method
of evaluating the worksheet as the principal tool for making
decisions. This makes the greedy approach used here applicable
to the other tree problems that may not be so simple. The results
below show the feasible solutions generated by the greedy approach.
The solutions that do not form a complete tree are not feasible
and are not shown.
For the asymmetric case and for all other spanning
tree problems the search dialog allows random searches and improvements.
For tree problems we only allow one kind of improvement.
Given a tree, we investigate each nontree arc, say arc (*i*,
*j*) . We form a new graph by adding this arc and deleting
the arc formerly entering node *j*. If the new arc does
not form a cycle, we evaluate the resultant tree. If the objective
is improved, we make the revised tree the incumbent solution
and continue the process. The improvement step is continued
until a complete pass through the nontree arcs results in no
improvement.
It is not necessary to include a data table with
the combinatorial form. Without the form the user must compute
the evaluation measure on the worksheet and put a link to the
measure in objective value cell of the form. The add-in generates
tree solutions and selects the optimum. |