Download Heuristic Algorithms for NP

92
1
2
3
4
5
6
7
8
9
10
API Manual
public class WeightedH a mi l t on C yc l e <V > extends problems . NPCProblem {
private Graph <V , Double > g ;
public WeightedHa m il t o nC y cl e <V >( Graph <V , Double > g ) {
this .g = g ;
}
public int size () { return g . vertices + g . getNoEdges () ; //
estimate of objects size
}
}
E.2
New Transformations
Creating a transformation requires two new methods, which are both placed in
the class that should be transformed. The first method should transform an
instance and the second should detransform a solution from the transformed
instance.
The method which transforms an instance may not take any arguments and the
name of the method should have the prefix ”transformTo“ and it must return
the transformed instance.
The detransform method takes as argument a solution from the transformed
instance and it must return a detransformed solution. Furthermore the detransform method must have the prefix ”detransform“ and the rest of the method
name must match that of the transformation method.
Here is a simple example of a transformation, which transforms an instance of
WeightedHamiltonCycle to TravellingSalesman.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
public class WeightedH a mi l t on C yc l e <V > extends problems . NPCProblem {
...
public TravelingSal es m an <V > t r a n s f o r m T o T S () {
return new TravelingSa le s ma n <V >( g . copy () ) ;
}
public int [] d e t r a n s f o r m T S ( int [] sol ) {
int [] whc = new int [ sol . length ];
for ( int i =0; i < sol . length ; i ++)
whc [ i ]= sol [ i ];
return whc ;
}
...
}