Class PermutationToBitVectorProblem
 All Implemented Interfaces:
Splittable<Initializer<BitVector>>
,Initializer<BitVector>
 Direct Known Subclasses:
PermutationToBitVectorProblem.DoubleCost
,PermutationToBitVectorProblem.IntegerCost
BitVector
search operators to solve problems defined over the space of
Permutation
objects. It can also be used as an Initializer
of
BitVectors by search algorithms to ensure that the search is using BitVectors of the appropriate
length to represent permutations of the desired length for the problem you are solving. In fact,
to ensure that your search is using the correct bit length, you should use this as your
Initializer.
The mapping uses a classic transformation from vector of bits to a permutation of the N
integers from 0 to N1 that works as follows. Consider a list of integers L initially containing
the N integers in sorted order: L = [0, 1, 2, ..., N1]. The list L is circular, such that any
integer is an index into L. For example, if L is of length 5, indexes 0, 5, 10, etc all refer to
the element in position 0. Likewise, indexes 1, 6, 11, etc all refer to the element in position
1, and so forth. The bit vector must be length: (N  1) ceiling(lg N). Each contiguous group of
ceiling(lg N) bits is treated as an index into L. There are N1 such indexes available based on
the bit vector length. Each such index is used to select an element from L, add it to the next
available position of an initially empty permutation P, and remove it from L. After N1 such
operations, there will be one element left in L, which is then added to the end. The toPermutation(BitVector)
method implements this transformation.
Here is an example. Consider a very small permutation length N = 6. For this length permutation, the bit vector must be (6  1) ceiling(lg 6) = 5 * 3 = 15 bits in length. Let's consider the transformation from the bit vector 111110001010100.
 L is initially L = [0, 1, 2, 3, 4, 5], and P is initially P = [].
 The first 3 bits, 111, is 7 in decimal, and 7 mod 6 = 1. L[1]=1, so we remove the 1 from L and add it to the end of P. This leads to L = [0, 2, 3, 4, 5], and P is P = [1].
 The next 3 bits, 110, is 6 in decimal, and 6 mod 5 = 1. L[1]=2, so we remove the 2 from L and add it to the end of P. This leads to L = [0, 3, 4, 5], and P is P = [1, 2].
 The next 3 bits, 001, is 1 in decimal, and 1 mod 4 = 1. L[1]=3, so we remove the 3 from L and add it to the end of P. This leads to L = [0, 4, 5], and P is P = [1, 2, 3].
 The next 3 bits, 010, is 2 in decimal, and 2 mod 3 = 2. L[2]=5, so we remove the 5 from L and add it to the end of P. This leads to L = [0, 4], and P is P = [1, 2, 3, 5].
 The last 3 bits, 100, is 4 in decimal, and 4 mod 2 = 0. L[0]=0, so we remove the 0 from L and add it to the end of P. This leads to L = [4], and P is P = [1, 2, 3, 5, 0].
 Reached the end of the bit vector, and there is only one element left in L, the 4, which we simply add to the end of P to arrive at P = [1, 2, 3, 5, 0, 4].
This class has two nested subclasses, PermutationToBitVectorProblem.DoubleCost
and PermutationToBitVectorProblem.IntegerCost
, that handle
the transformations from Permutation optimization problems with costs of type double and int,
respectively (i.e., classes OptimizationProblem
and IntegerCostOptimizationProblem
).

Nested Class Summary
Modifier and TypeClassDescriptionstatic final class
This class implements a mapping between Permutation problems and BitVector problems, where cost values are of type double.static final class
This class implements a mapping between Permutation problems and BitVector problems, where cost values are of type int. 
Constructor Summary
ConstructorDescriptionPermutationToBitVectorProblem
(int permutationLength) Initializes the PermutationToBitVectorProblem mapping for a specific permutation length. 
Method Summary
Modifier and TypeMethodDescriptionfinal BitVector
Creates one candidate solution to a problem.split()
Generates a functionally identical copy of this object, for use in multithreaded implementations of search algorithms.final int
Computes the length of BitVectors supported by this instance.final Permutation
toPermutation
(BitVector bits) Converts a BitVector to a Permutation.

Constructor Details

PermutationToBitVectorProblem
public PermutationToBitVectorProblem(int permutationLength) Initializes the PermutationToBitVectorProblem mapping for a specific permutation length. Parameters:
permutationLength
 The length of the permutations under optimization, in number of elements. This is NOT the length of the BitVectors. For example, if the problem is the Traveling Salesperson, and if the instance has 100 cities, then you would pass 100 for this parameter. Throws:
IllegalArgumentException
 if permutationLength is less than 1.


Method Details

createCandidateSolution
Description copied from interface:Initializer
Creates one candidate solution to a problem. Specified by:
createCandidateSolution
in interfaceInitializer<BitVector>
 Returns:
 a candidate solution to a problem instance.

split
Description copied from interface:Splittable
Generates a functionally identical copy of this object, for use in multithreaded implementations of search algorithms. The state of the object that is returned may or may not be identical to that of the original. Thus, this is a distinct concept from the functionality of theCopyable
interface. Classes that implement this interface must ensure that the object returned performs the same functionality, and that it does not share any state data that would be either unsafe or inefficient for concurrent access by multiple threads. The split method is allowed to simply return the this reference, provided that it is both safe and efficient for multiple threads to share a single copy of the Splittable object. The intention is to provide a multithreaded search with the capability to provide spawned threads with their own distinct search operators. Such multithreaded algorithms can call the split method for each thread it spawns to generate a functionally identical copy of the operator, but with independent state. Specified by:
split
in interfaceSplittable<Initializer<BitVector>>
 Returns:
 A functionally identical copy of the object, or a reference to this if it is both safe and efficient for multiple threads to share a single instance of this Splittable object.

toPermutation
Converts a BitVector to a Permutation. Assumes that the length of the BitVector bits is supportedBitVectorLength(), and behavior is undefined otherwise. Parameters:
bits
 The BitVector Returns:
 A Permutation derived from the BitVector

supportedBitVectorLength
public final int supportedBitVectorLength()Computes the length of BitVectors supported by this instance. Returns:
 the length of BitVectors supported by this instance
