Module org.cicirello.chips_n_salsa
Package org.cicirello.search.ss
Class HeuristicPermutationGenerator
java.lang.Object
org.cicirello.search.ss.HeuristicSolutionGenerator<Permutation>
org.cicirello.search.ss.HeuristicPermutationGenerator
 All Implemented Interfaces:
Splittable<TrackableSearch<Permutation>>
,SimpleMetaheuristic<Permutation>
,TrackableSearch<Permutation>
This class generates solutions to permutation optimization problems using a constructive
heuristic. Unless the heuristic given to it is randomized, this class is completely deterministic
and has no randomized behavior. Thus, executing the
HeuristicSolutionGenerator.optimize()
method multiple times
should produce the same result each time. When using a constructive heuristic, you begin with an
empty solution, in this case an empty permutation, and you then use a constructive heuristic to
choose which element to add to the partial solution, in this case to the partial permutation.
This is repeated until you derive a complete solution (i.e., a complete permutation).
Constructive heuristics are not just for permutations. See the HeuristicSolutionGenerator
class for a more general implementation.
Assuming that the length of the permutation is N, and that the runtime of the heuristic is O(f(N)), the runtime to construct one permutation using a constructive heuristic is O(N^{2} f(N)). If the cost, f(N), to heuristically evaluate one permutation element is simply, O(1), constant time, then the cost to heuristically construct a permutation is simply O(N^{2}).

Constructor Summary
ConstructorDescriptionConstructs an HeuristicPermutationGenerator for generating solutions to an optimization problem using a constructive heuristic.HeuristicPermutationGenerator
(ConstructiveHeuristic<Permutation> heuristic, ProgressTracker<Permutation> tracker) Constructs an HeuristicPermutationGenerator for generating solutions to an optimization problem using a constructive heuristic. 
Method Summary
Modifier and TypeMethodDescriptionsplit()
Generates a functionally identical copy of this object, for use in multithreaded implementations of search algorithms.Methods inherited from class org.cicirello.search.ss.HeuristicSolutionGenerator
getProblem, getProgressTracker, getTotalRunLength, optimize, setProgressTracker

Constructor Details

HeuristicPermutationGenerator
Constructs an HeuristicPermutationGenerator for generating solutions to an optimization problem using a constructive heuristic. A ProgressTracker is created for you. Parameters:
heuristic
 The constructive heuristic. Throws:
NullPointerException
 if heuristic is null

HeuristicPermutationGenerator
public HeuristicPermutationGenerator(ConstructiveHeuristic<Permutation> heuristic, ProgressTracker<Permutation> tracker) Constructs an HeuristicPermutationGenerator for generating solutions to an optimization problem using a constructive heuristic. Parameters:
heuristic
 The constructive heuristic.tracker
 A ProgressTracker Throws:
NullPointerException
 if heuristic or tracker is null


Method Details

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 interfaceSimpleMetaheuristic<Permutation>
 Specified by:
split
in interfaceSplittable<TrackableSearch<Permutation>>
 Overrides:
split
in classHeuristicSolutionGenerator<Permutation>
 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.
