Travelling Salesman und die kürzeste Strecke |
| 30.11.2009, 20:37 | Hustinettenbör | Auf diesen Beitrag antworten » |
| Travelling Salesman und die kürzeste Strecke Ich baue gerade einen Algorithmus der mir diese Strecke mit einem evolutionären Verfahren optimiert. Für mich stellt sich jetzt die Frage bezüglich des Abbruchkriteriums. Ich möchte eine gewisse Güte des Weges haben. Die Güte zu bestimmen ist aber genau das Problem. Ich kenne den besten Weg ja nicht. Ich setze eine bestimmte Anzahl n Punkte zufällig auf ein Feld mit 300 x 400 Einheiten. Auf diesem Feld werden alle Punkte auf kürzest möglicher Strecke miteinander verbunden. Kann man hiervon statistisch die Durchschnittlich kürzeste Länge bestimmen? Ich würd mein Abbruchkriterium gerne davon abhängig machen, komme aber leider - ich bin nur Hobbyinformatiker 
- nicht weiter.Hat jemand eine Idee, wie man hier ansetzen könnte? Oder Alternative Ansätze für ein Abbruchkriterium? (Eine Sture Anzahl an Generationen kommt nicht in Frage) LG |
||
| 03.12.2009, 20:31 | Abakus | Auf diesen Beitrag antworten » |
| RE: Travelling Salesman und die kürzeste Strecke Hallo! Was sagst du zu sowas: Christofides-Heuristik (Wiki) In der Richtung wäre dann weiter zu suchen. Grüße Abakus
|
||
| 05.12.2009, 20:46 | Hustinettenbör | Auf diesen Beitrag antworten » |
Danke, genau nach sowas hab ich gesucht ! |
||
| 06.12.2009, 10:31 | Mystic | Auf diesen Beitrag antworten » |
Alternativ könnte man auch ein Branch and Bound Verfahren für das TSP solange anwenden, bis sich die untere Schranke für die optimale Weglänge (gegeben durch den aktuell besten Bound) und die obere Schranke (gegeben durch die aktuell beste vollständige Lösung) genügend angenähert haben... |
||
|
|
Verwandte Themen
| Die Beliebtesten » |
|
| Die Größten » |
| Die Neuesten » |
|
