- Direct Known Subclasses:
public class PermutationToBitVectorProblem extends Object implements Initializer<BitVector>
This class implements a mapping between Permutation problems and BitVector problems, enabling using
BitVectorsearch operators to solve problems defined over the space of
Permutationobjects. It can also be used as an
Initializerof 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 N-1 that works as follows. Consider a list of integers L initially containing the N integers in sorted order: L = [0, 1, 2, ..., N-1]. 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 N-1 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 N-1 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, 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 = .
- The next 3 bits, 110, is 6 in decimal, and 6 mod 5 = 1. L=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=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=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, so we remove the 0 from L and add it to the end of P. This leads to L = , 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.IntegerCost, that handle the transformations from Permutation optimization problems with costs of type double and int, respectively (i.e., classes
Nested Class Summary
Nested Classes Modifier and Type Class Description
PermutationToBitVectorProblem.DoubleCostThis class implements a mapping between Permutation problems and BitVector problems, where cost values are of type double.
PermutationToBitVectorProblem.IntegerCostThis class implements a mapping between Permutation problems and BitVector problems, where cost values are of type int.
Constructors Constructor Description
PermutationToBitVectorProblem(int permutationLength)Initializes the PermutationToBitVectorProblem mapping for a specific permutation length.
All Methods Instance Methods Concrete Methods Modifier and Type Method Description
createCandidateSolution()Creates one candidate solution to a problem.
split()Generates a functionally identical copy of this object, for use in multithreaded implementations of search algorithms.
supportedBitVectorLength()Computes the length of BitVectors supported by this instance.
toPermutation(BitVector bits)Converts a BitVector to a Permutation.
public PermutationToBitVectorProblem(int permutationLength)Initializes the PermutationToBitVectorProblem mapping for a specific permutation length.
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.
IllegalArgumentException- if permutationLength is less than 1.
public final BitVector createCandidateSolution()Description copied from interface:
InitializerCreates one candidate solution to a problem.
public PermutationToBitVectorProblem split()Description copied from interface:
SplittableGenerates 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 the
Copyableinterface. 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.
public final Permutation toPermutation(BitVector bits)Converts a BitVector to a Permutation. Assumes that the length of the BitVector bits is supportedBitVectorLength(), and behavior is undefined otherwise.
bits- The BitVector
- A Permutation derived from the BitVector
public final int supportedBitVectorLength()Computes the length of BitVectors supported by this instance.
- the length of BitVectors supported by this instance