Hallo, vielleicht kennt sich jemand ja mit dem Problem hier aus ^^
Problem ist, dass bei meiner MST- Heuristik immer das gleiche Ergebnis herauskommt, wie bei meiner Nearest-Neighbour Heuristik, also ich habe erstere implementiert. Gegebenenfalls könnte der "Fehler" sein, dass ich am Ende wieder den ersten Knoten hinzufüge, wie beim Nearest-Neighbour verfahren.
Mein Code:
Danke für eure Hilfe!
Problem ist, dass bei meiner MST- Heuristik immer das gleiche Ergebnis herauskommt, wie bei meiner Nearest-Neighbour Heuristik, also ich habe erstere implementiert. Gegebenenfalls könnte der "Fehler" sein, dass ich am Ende wieder den ersten Knoten hinzufüge, wie beim Nearest-Neighbour verfahren.
Mein Code:
Java:
package travelingSalesmanProblem;
import java.util.ArrayList;
import java.util.List;
import map.City;
/**
* class representing the MST Heuristic
*
* @author MrXeth
* @version 1.0
*/
public class MSTHeuristic extends Method {
/*
* (non-Javadoc)
*
* @see travelingSalesmanProblem.Method#getOrder(java.util.List)
*/
@Override
public List<City> getOrder(List<City> cities) {
cities = new MinTree(cities).getCities();
List<City> way = new ArrayList<City>();
// unmarks all cities, because now they are in the right order
for (City c : cities) {
c.marked = false;
}
// recursion for creating an euler circle
recursion(cities.get(0), way);
way.add(cities.get(0));
// setting to the begin: neighbours are just for the MinTree necessary
/*for (City c : cities) {
c.remNeighbours();
}*/
return way;
}
/**
* recursion for creating a way of the cities
*
* @param par city to add
* @param way list to add city
*/
private void recursion(City par, List<City> way) {
// marks city
par.marked = true;
// adds city to way
way.add(par);
List<City> parNeighbours = par.getNeighbours();
// go through neighbours and add them at the next call -> the neighbours are
// already sorted by the mintree after their importance
for (City c : parNeighbours) {
// if the city is not in the way
if (!c.marked) {
recursion(c, way);
}
}
}
}
Java:
package travelingSalesmanProblem;
import java.util.List;
import map.City;
// Prim Algorithmus, da es viel E^E Kanten gibt
/**
* class for creating a minimal tree by the prim algorithm
*
* @author MrXeth
* @version 1.0
*
*/
public class MinTree {
private List<City> cities;
// with which city the city at the n-pos has the shortest way - example:
// parent[0] = 1
// -> city at position 0 's best connection partner is 1
private int[] parent;
// connection values
private double[] queue;
/**
* constructor
*
* @param cities cities to build a min tree
*/
public MinTree(List<City> cities) {
this.cities = cities;
queue = new double[cities.size()];
parent = new int[cities.size()];
buildTree();
}
/**
* adds city to the mintree
*
* @param par parent of city / node before
*/
private void addCity(int par) {
int unmarked = calcMinDist(par);
int minS = searchShortestPath();
// add and mark
City conPar = cities.get(parent[minS]);
City conChild = cities.get(minS);
queue[minS] = Double.MAX_VALUE;
// connect both nodes and mark child
conPar.connect(conChild);
conChild.marked = true;
// because marked, unmarked can be reduced
unmarked--;
// until all nodes are in the graph
if (unmarked > 0) {
addCity(minS);
}
}
private void buildTree() {
// prepare and set everything on the worst - case
for (int i = 0; i < cities.size(); i++) {
queue[i] = Double.MAX_VALUE;
parent[i] = -1;
cities.get(i).marked = false;
}
addCity(0);
}
/**
* updates the queue- and the parent array for the parent city in the parameters
*
* @param par current city
* @return number of unmarked cities
*/
private int calcMinDist(int par) {
// city for making a connection
City c = cities.get(par);
// city is a part of the minimal tree now
c.marked = true;
// how many nodes have to be added ( in the next step counted)
int unmarked = 0;
// minimal distance
double min;
City temp;
for (int i = 0; i < cities.size(); i++) {
// for preventing distance 0
if (i != par) {
temp = cities.get(i);
// if temp is not in the graph
if (!temp.marked) {
// count unmarked cities
unmarked++;
// calc distance
min = c.dist(temp);
// tests, if the distance is smaller than the value before ( at the beginning
// yes, because unlimited)
// saves for every city the optimal distance, if it is not already in the graph
// -> if city is not in the graph, it looks, if the distance to the current node
// is smaller than the distance before
if (min < queue[i]) {
// saving the current node ( par ) as the parent node
parent[i] = par;
// write in the queue the minimal distance
queue[i] = min;
}
}
}
}
return unmarked;
}
/**
* returns the ready mintree
*
* @return ready mintree
*/
public List<City> getCities() {
return cities;
}
/**
* searches the city with the shortest way
*
* @return index of the city
*/
private int searchShortestPath() {
double minP = Double.MAX_VALUE;
// index of the city
int minS = -1;
for (int i = 0; i < cities.size(); i++) {
if (queue[i] < minP) {
minS = i;
minP = queue[i];
}
}
return minS;
}
}
Java:
package travelingSalesmanProblem;
import java.util.LinkedList;
import java.util.List;
import map.City;
/**
* Class for finding a way to visit the cities via the Nearest Neighbour
* Heuristic
*
* @author MrXeth
* @version 1.0
*
*/
public class NearestNeighbourHeuristic extends Method {
/*
* (non-Javadoc)
*
* @see salesmanProblem.Method#getOrder(java.util.List)
*/
@Override
public List<City> getOrder(List<City> cities) {
if (cities.size() > 0) {
List<City> way = new LinkedList<City>();
double temp, dist;
way.add(cities.get(0));
for (int i = 1; i < cities.size(); i++) {
dist = Double.POSITIVE_INFINITY; // worst case
for (int j = 1; j < cities.size(); j++) {
if (!way.contains(cities.get(j))) { // tests if the city has already been visited
temp = way.get(i - 1).dist(cities.get(j)); // ggf compare funktion
if (temp < dist) { // swap if other city is closer
try {
way.set(i, cities.get(j));
} catch (IndexOutOfBoundsException e) {
way.add(cities.get(j));
}
dist = temp;
}
}
}
}
way.add(cities.get(0));
return way;
}
return null;
}
}Danke für eure Hilfe!
ich denke, dass ich am Ende einen schlechten Algorithmus zum verwerten des Spannbaumes genutzt habe.
