Hallo, ich sitze gerade an dem Salesman Problem ( Problem des Handlungsreisenden) an einem Bruteforce Algotithmus.
Mein Problem ist, dass ich auf dem Schlauch stehe, wie ich Wege wie A-B-C-D-A und A-D-C-B-A im Vorfeld ausgrenze (ungerichteter Graph).
Mein Code:
Die Funktion compare gibt einfach nur einen positiven Wert aus, wenn Stadt 1 > Stadt2 und einen negativen wenn andersherum.
Vielen Dank schonmal für eure Antworten.
Lg MrXeth
Mein Problem ist, dass ich auf dem Schlauch stehe, wie ich Wege wie A-B-C-D-A und A-D-C-B-A im Vorfeld ausgrenze (ungerichteter Graph).
Mein Code:
Java:
private City[] cities;
@Override
public City[] getOrder(City[] cities) {
this.cities = cities;
City[] weg = new City[cities.length + 1];
City[] übrStädte = this.cities.clone();
weg[0] = cities[0];
übrStädte[0] = null;
City[] comp1, comp2;
comp1 = rekursion(cities.length - 1, 1, übrStädte.clone(),1 , weg.clone());
for(int i = 1; i < cities.length - 1; i++) {
comp2 = rekursion(cities.length - 1, i+1, übrStädte.clone(), 1, weg.clone());
if(compare(comp1, comp2) > 0) {
comp1 = comp2;
}
}
return comp1;
}
private City[] rekursion(int tiefe, int nimmNr, City[] übrStädte,int index, City[] weg) {
if(tiefe == 0) {
weg[weg.length-1] = cities[0];
for (int i = 0; i < weg.length; i++) {
System.out.println(weg[i].getName());
}
System.out.println();
return weg;
}
tiefe--;
City[] comp1, comp2;
for(int i = 0, j = 0; i < übrStädte.length && j < nimmNr; i++) {
if(übrStädte[i] != null) {
j++;
if(j == nimmNr ) {
weg[index] = übrStädte[i];
übrStädte[i] = null;
index++;
}
}
}
comp1 = rekursion(tiefe, 1, übrStädte.clone(), index, weg.clone());
for(int i = 1; i < tiefe; i++) {
comp2 = rekursion(tiefe, i + 1, übrStädte.clone(), index, weg.clone());
if(compare(comp1, comp2) > 0) {
comp1 = comp2;
}
}
return comp1;
}Die Funktion compare gibt einfach nur einen positiven Wert aus, wenn Stadt 1 > Stadt2 und einen negativen wenn andersherum.
Vielen Dank schonmal für eure Antworten.
Lg MrXeth
