Class PermutationToBitVectorProblem
 java.lang.Object

 org.cicirello.search.problems.PermutationToBitVectorProblem

 All Implemented Interfaces:
Splittable<Initializer<BitVector>>
,Initializer<BitVector>
 Direct Known Subclasses:
PermutationToBitVectorProblem.DoubleCost
,PermutationToBitVectorProblem.IntegerCost
public class PermutationToBitVectorProblem extends Object implements Initializer<BitVector>
This class implements a mapping between Permutation problems and BitVector problems, enabling using
BitVector
search operators to solve problems defined over the space ofPermutation
objects. It can also be used as anInitializer
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
andPermutationToBitVectorProblem.IntegerCost
, that handle the transformations from Permutation optimization problems with costs of type double and int, respectively (i.e., classesOptimizationProblem
andIntegerCostOptimizationProblem
).


Nested Class Summary
Nested Classes Modifier and Type Class Description static class
PermutationToBitVectorProblem.DoubleCost
This class implements a mapping between Permutation problems and BitVector problems, where cost values are of type double.static class
PermutationToBitVectorProblem.IntegerCost
This class implements a mapping between Permutation problems and BitVector problems, where cost values are of type int.

Constructor Summary
Constructors Constructor Description PermutationToBitVectorProblem(int permutationLength)
Initializes the PermutationToBitVectorProblem mapping for a specific permutation length.

Method Summary
All Methods Instance Methods Concrete Methods Modifier and Type Method Description BitVector
createCandidateSolution()
Creates one candidate solution to a problem.PermutationToBitVectorProblem
split()
Generates a functionally identical copy of this object, for use in multithreaded implementations of search algorithms.int
supportedBitVectorLength()
Computes the length of BitVectors supported by this instance.Permutation
toPermutation(BitVector bits)
Converts a BitVector to a Permutation.



Constructor Detail

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 Detail

createCandidateSolution
public final BitVector 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
public PermutationToBitVectorProblem 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
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. 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

