Download Heuristic Algorithms for NP

6.5 Implemented solutions
33
Dijkstras algorithm the edges have to be of a type, XComparable (extended
version of Comparable interface), which knows how it can be added to other
XComparable objects.
Demanding that Dijkstra only runs on graphs with edges implementing this
interface makes it extremely simple and dynamic to define how Dijkstra should
calculate the weight of a path.
Of the mentioned solution above I have implemented the following:
• It is possible to find the shortest route between two problems assuming
all transformations have the same weight e.g. breadth first search.
• One can give an approximate exponent for each transformation and the
weight of taking two transformations with O(na ) and O(nb ) is calculated
to be c = ab. This does not take account of padding, however one can
adjust the exponent to simulate the padding of the transformation.
• The last solution implemented finds an empirical value for the exponent
like described above. In order to solve the problem when an instance
contains multiple input sizes, it is demanded that each instance knows
how to calculate one input size based on all of its contents e.g. a graph
problem can calculate its input size as n = V + E and this value for n is
then used as mentioned.
To store the empirical data a function have been made, which saves the entire
transformation graph in a XML-document, which has to be loaded before the
Dijkstra algorithm is used.
I have not implemented support of parallel transformations, since no such transformations are currently available in the transformation graph.
Furthermore the running time of the heuristic algorithms are not part of any
of the calculations, because it is assumed that the user knows what heuristic
algorithm he wants to use and he knows what NPC problems it is available at.
This has been done because in the authors opinion it is more important, that
the heuristic solution is close to the optimal rather than it is found quickly.
Finally it should be mentioned that even though it has been implemented the
automatic solving does not correctly simulate the behavior of the transformations in its current form. The reason for this is that little time has been spent on
finding the best approximate exponent for the asymptotic running time and the
estimate of the input size used for the empirical data is in most cases a bit too