Module org.cicirello.chips_n_salsa
Package org.cicirello.search.problems

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 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 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]=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).

  • 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

      public final BitVector createCandidateSolution()
      Description copied from interface: Initializer
      Creates one candidate solution to a problem.
      Specified by:
      createCandidateSolution in interface Initializer<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 the Copyable 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 interface Splittable<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