Package org.tweetyproject.math.examples
Class TravelingSalesman
- java.lang.Object
-
- java.util.AbstractCollection<E>
-
- java.util.AbstractSet<E>
-
- java.util.HashSet<OptProbElement>
-
- org.tweetyproject.math.opt.problem.GeneralConstraintSatisfactionProblem
-
- org.tweetyproject.math.opt.problem.CombinatoricsProblem
-
- org.tweetyproject.math.examples.TravelingSalesman
-
- All Implemented Interfaces:
java.io.Serializable
,java.lang.Cloneable
,java.lang.Iterable<OptProbElement>
,java.util.Collection<OptProbElement>
,java.util.Set<OptProbElement>
public class TravelingSalesman extends CombinatoricsProblem
implements the traveling salesman problem. Every element has an x- coordinate and a y- coordinate. Every city can be connected to each other and the distance is the cartesian distance bewteen them. Therefore the graph is fully connected.- Author:
- Sebastian Franke
- See Also:
- Serialized Form
-
-
Field Summary
-
Fields inherited from class org.tweetyproject.math.opt.problem.CombinatoricsProblem
elements, MAXIMIZE, MINIMIZE
-
-
Constructor Summary
Constructors Constructor Description TravelingSalesman(java.util.ArrayList<ElementOfCombinatoricsProb> elements)
-
Method Summary
Modifier and Type Method Description java.util.ArrayList<ElementOfCombinatoricsProb>
createRandomNewSolution(java.util.ArrayList<ElementOfCombinatoricsProb> currSol)
create a solution that changes the solution currSol a little bit (i.e.: for TSP: swap 2 cities; for KnapSack: add a random element) for currSol == null: create a random solutiondouble
evaluate(java.util.ArrayList<ElementOfCombinatoricsProb> sol)
evaluates the solutionjava.lang.Double
getHeuristicValue(ElementOfCombinatoricsProb solutionComponent, java.lang.Integer getCurrentIndex, ElementOfCombinatoricsProb initialReference, ElementOfCombinatoricsProb[] sol)
for Ant optimization: give a chance between 0 and 1 for accepting solutionComponent to the solution soldouble[][]
getRepresentation()
for Ant optimization: represent the problem as an adjacence matrixboolean
isValid(java.util.ArrayList<ElementOfCombinatoricsProb> solution)
checks if a given solution is valid under all constraintsdouble
sumOfWeights(java.util.ArrayList<ElementOfCombinatoricsProb> sol)
-
Methods inherited from class org.tweetyproject.math.opt.problem.CombinatoricsProblem
createDifference, formNeighborhood, getGraphrepresentation
-
Methods inherited from class java.util.HashSet
add, clear, clone, contains, isEmpty, iterator, remove, size, spliterator
-
-
-
-
Constructor Detail
-
TravelingSalesman
public TravelingSalesman(java.util.ArrayList<ElementOfCombinatoricsProb> elements)
-
-
Method Detail
-
createRandomNewSolution
public java.util.ArrayList<ElementOfCombinatoricsProb> createRandomNewSolution(java.util.ArrayList<ElementOfCombinatoricsProb> currSol)
Description copied from class:CombinatoricsProblem
create a solution that changes the solution currSol a little bit (i.e.: for TSP: swap 2 cities; for KnapSack: add a random element) for currSol == null: create a random solution- Specified by:
createRandomNewSolution
in classCombinatoricsProblem
- Parameters:
currSol
- the current solution- Returns:
- the solution
-
isValid
public boolean isValid(java.util.ArrayList<ElementOfCombinatoricsProb> solution)
Description copied from class:CombinatoricsProblem
checks if a given solution is valid under all constraints- Specified by:
isValid
in classCombinatoricsProblem
- Parameters:
solution
- some solution- Returns:
- true iff the solution is valid
-
evaluate
public double evaluate(java.util.ArrayList<ElementOfCombinatoricsProb> sol)
Description copied from class:CombinatoricsProblem
evaluates the solution- Specified by:
evaluate
in classCombinatoricsProblem
- Parameters:
sol
- some solution- Returns:
- the target function for sol
-
sumOfWeights
public double sumOfWeights(java.util.ArrayList<ElementOfCombinatoricsProb> sol)
- Specified by:
sumOfWeights
in classCombinatoricsProblem
- Parameters:
sol
- is the solution to be viewd- Returns:
- if the solution sol is valid under the constraints of the problem
-
getHeuristicValue
public java.lang.Double getHeuristicValue(ElementOfCombinatoricsProb solutionComponent, java.lang.Integer getCurrentIndex, ElementOfCombinatoricsProb initialReference, ElementOfCombinatoricsProb[] sol)
Description copied from class:CombinatoricsProblem
for Ant optimization: give a chance between 0 and 1 for accepting solutionComponent to the solution sol- Specified by:
getHeuristicValue
in classCombinatoricsProblem
- Parameters:
solutionComponent
- : Element to be checked *getCurrentIndex
- : the length of the solutioninitialReference
- : default starting point for the solution (the first Element in the solution)sol
- : array representation of a solution (needed for Ant optimization)- Returns:
- the heuristic value
-
getRepresentation
public double[][] getRepresentation()
Description copied from class:CombinatoricsProblem
for Ant optimization: represent the problem as an adjacence matrix- Specified by:
getRepresentation
in classCombinatoricsProblem
-
-