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>
public final class HeuristicPermutationGenerator extends HeuristicSolutionGenerator<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(N2 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(N2).
-
-
Constructor Summary
Constructors Constructor Description HeuristicPermutationGenerator(ConstructiveHeuristic<Permutation> heuristic)
Constructs 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
All Methods Instance Methods Concrete Methods Modifier and Type Method Description HeuristicPermutationGenerator
split()
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 Detail
-
HeuristicPermutationGenerator
public HeuristicPermutationGenerator(ConstructiveHeuristic<Permutation> heuristic)
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 Detail
-
split
public HeuristicPermutationGenerator 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.
-
-