Hallo,
ich habe ein Problem mit meinen Funktionen, die den kürzesten Weg durch ein Netz von Nodes finden sollen. Der Abstand von einem Node zu einem Nachbarn ist immer identisch, also es zählen nur die Anzahl der Schritte bzw. die Anzahl der Nodes im Pfad.
Ein Node besitzt ein Set von Nodes, das seine direkten Nachbarn enthält.
Die Funktion, die nur die kürzeste Strecke zwischen Start- und End-Node bestimmt funktioniert ohne Probleme:
Die funktion wird mit dem Start-Node aufgerufen.
Das Problem ist die Funktion, bei der Wegpunkte angegeben sind, die passiert werden müssen.
Dabei muß für ein passieren der Node nicht betreten werden. Ein Node soll auch als passiert gelten, wenn er direkt neben der Route liegt, also ein Nachbar eines Elementes der Route ist.
So habe ich es probiert:
Die maximale Länge habe ich auf ((Anzahl aller existierenden Nodes) - 2) * 2 begrenzt.
Das Problem ist, daß er manchmal einfach nicht fertig wird mit der Berechnung, er probiert ja alle möglichen Routen durch, um vllt. doch noch eine kürzere zu finden.
Mein Test-Netz hat 44 Knoten, wenn ich da zB 6 Wegpunkte angebe hat er das Ergebnis schon nach ein paar Sekunden. Wenn ich im sage, er soll alle 44 Knoten passieren, war er nach 20 Minuten noch nicht fertig. Das ist nicht akzeptabel, da es später mit ca. 1000 Nodes insgesammt und 0-1000 Wegpunkten funktionieren muss.
Ich brauche drigend eine Lösung dafür...
Vielen Dank
Laurin
ich habe ein Problem mit meinen Funktionen, die den kürzesten Weg durch ein Netz von Nodes finden sollen. Der Abstand von einem Node zu einem Nachbarn ist immer identisch, also es zählen nur die Anzahl der Schritte bzw. die Anzahl der Nodes im Pfad.
Ein Node besitzt ein Set von Nodes, das seine direkten Nachbarn enthält.
Die Funktion, die nur die kürzeste Strecke zwischen Start- und End-Node bestimmt funktioniert ohne Probleme:
Java:
private void followPath(Node pos) {
testRoute.add(pos);
// Wenn Route schon länger als die kürzeste Route ist
if (testRoute.size() >= shortestRoute.size() && shortestRoute.size() > 0) {
testRoute.removeLast();
return;
}
// Wenn der End-Node erreicht wurde und die Route die bis jetzt kürzeste ist.
if (pos.equals(endNode)) {
if (testRoute.size() < shortestRoute.size() || shortestRoute.size() == 0) {
shortestRoute = new LinkedList<Node>(testRoute);
}
testRoute.removeLast();
return;
}
// Gehe in alle Nachbarn, die noch nicht auf der Route liegen
for (Node neighbor : pos.getNeighbors()) {
if (!testRoute.contains(neighbor)) {
followPath(neighbor);
}
}
testRoute.removeLast();
return;
}Die funktion wird mit dem Start-Node aufgerufen.
Das Problem ist die Funktion, bei der Wegpunkte angegeben sind, die passiert werden müssen.
Dabei muß für ein passieren der Node nicht betreten werden. Ein Node soll auch als passiert gelten, wenn er direkt neben der Route liegt, also ein Nachbar eines Elementes der Route ist.
So habe ich es probiert:
Java:
private void followPathInclude(Node pos) {
testRoute.add(pos);
// In newlyPassed werden die Nodes gespeichert, die bei betreten des neuen Nodes passiert
// werden und die vorher noch nicht passiert waren. Beim "Zurückziehen" vom Pfad werden diese
//dann aufgeräumt.
HashSet<Node> newlyPassed = new HashSet<Node>();
if (include.contains(pos) && !passed.contains(pos)) {
newlyPassed.add(pos);
passed.add(pos);
}
for (Node neighbor : pos.getNeighbors()) {
if (include.contains(neighbor) && !passed.contains(neighbor)) {
newlyPassed.add(neighbor);
passed.add(neighbor);
}
}
// Nötige Abbruchbedingung, da die Bedingung, daß ein Node nur einmal im Pfad auftauchen darf
// wegfallen muß
if (testRoute.size() > this.maxLength) {
testRoute.removeLast();
passed.removeAll(newlyPassed);
return;
}
// Wenn Route schon länger als die kürzeste Route ist
if (testRoute.size() >= shortestRoute.size() && shortestRoute.size() > 0) {
testRoute.removeLast();
passed.removeAll(newlyPassed);
return;
}
// Wenn der End-Node erreicht wurde, die Route die bis jetzt kürzeste ist und alle zu passierenden
// Nodes (Set include) passiert wurden (Set passed)
if (pos.equals(endNode)) {
if (passed.containsAll(include)) {
if (testRoute.size() < shortestRoute.size() || shortestRoute.size() == 0) {
shortestRoute = new LinkedList<Node>(testRoute);
testRoute.removeLast();
passed.removeAll(newlyPassed);
return;
}
}
}
// Diesmal müssen alle Nodes begangen werden, da Mehrfachvorkommen im Pfad nötig sein kann
for (Node neighbor : pos.getNeighbors()) {
followPathInclude(neighbor);
}
testRoute.removeLast();
passed.removeAll(newlyPassed);
return;
}Die maximale Länge habe ich auf ((Anzahl aller existierenden Nodes) - 2) * 2 begrenzt.
Das Problem ist, daß er manchmal einfach nicht fertig wird mit der Berechnung, er probiert ja alle möglichen Routen durch, um vllt. doch noch eine kürzere zu finden.
Mein Test-Netz hat 44 Knoten, wenn ich da zB 6 Wegpunkte angebe hat er das Ergebnis schon nach ein paar Sekunden. Wenn ich im sage, er soll alle 44 Knoten passieren, war er nach 20 Minuten noch nicht fertig. Das ist nicht akzeptabel, da es später mit ca. 1000 Nodes insgesammt und 0-1000 Wegpunkten funktionieren muss.
Ich brauche drigend eine Lösung dafür...
Vielen Dank
Laurin
