Punkte einer Punktwolke verbinden - Suche geeigneten Algorithmus

Hallo zusammen, Ich habe folgendes Problem:

Ich habe eine Punktwolke bestehend aus etwa 2000 Punkten.
Jetzt nehme ich einen der Punkte und ziehe in Gedanken eine Linie, die durch alle Punkte geht und wieder bei meinem Startpunkt endet. Jetzt möchte ich die Linie so ziehen, dass die Linie möglichst kurz ist.

Bis jetzt hab ich mir folgendes überlegt:

Ich habe eine Liste: tagPOINT Punkte[2000];
Jetzt habe ich noch eine Liste: Sortiert[2000];

Hier liegt mein Problem: ich möchte in dem Array Sortiert die Punkte in der Reihenfolge ablegen, in der man sie auf dem kürzesten Weg verbindet. Ich dachte, man könnte das so machen:

1. Startpunkt auswählen
2. Punkt in die Liste Sortiert eintragen.
3. Punkt suchen (unter den verbleibenden Punkten), der (dem neuen Punkt) am nächsten liegt.
4. Punkte in die Liste eintragen, weitermachen mit 3.

Hier hab ich allerdings das Problem, dass mit diesem Algorithmus nicht der küreste Weg gefunden wird. Hat jemand einen besseren Ansatz?

Freue mich über alle Anregungen.

http://de.wikipedia.org/wiki/Problem_des_Handlungsreisenden usw. :hoppschwiiz: :schland: :hoppschwiiz:

Michael E.

Wenn du nicht unbedingt den allerkürzesten Weg brauchst, würde ich dir auf jeden Fall empfehlen, im Abschnitt Heuristiken des Wikipedia-Artikels reinzuschauen, weil sich dadurch die Laufzeit erheblich verkürzt.

Michael E. schrieb:

erheblich

Schön ausgedrückt

Lass ih mal nach ner exakten Lösung bei seinen 2000 Punkten suchen

Vielen Dank erstmal für eure Antworten.
Ich steh aber immer noch auf dem Schlauch

Wenn ich mir das so ansehe, muss ich mir wohl was anderes einfallen lassen.
In meinem Programm soll der Benutzer die Punkte markieren und dann sollen die auch schnell sortiert werden, da man ja selbstverständlich schnell weiterarbeiten will. Gibt es da keinen geeigntetn Algorithmus?

Den Wikipedia-Artikel verstehe ich als Nichtprofessor nicht so wirklich, wäre nett, wenn mir jemand grob die einzelnen Schritte aufschreiben könnte. So in etwa wie ich es in meinem ersten Post gemacht habe.

Vielen Dank schonmal.

Punkteverbinder schrieb:

Vielen Dank erstmal für eure Antworten.
Ich steh aber immer noch auf dem Schlauch

Wenn ich mir das so ansehe, muss ich mir wohl was anderes einfallen lassen.
In meinem Programm soll der Benutzer die Punkte markieren und dann sollen die auch schnell sortiert werden, da man ja selbstverständlich schnell weiterarbeiten will. Gibt es da keinen geeigntetn Algorithmus?

Den Wikipedia-Artikel verstehe ich als Nichtprofessor nicht so wirklich, wäre nett, wenn mir jemand grob die einzelnen Schritte aufschreiben könnte. So in etwa wie ich es in meinem ersten Post gemacht habe.

Vielen Dank schonmal.

Also kurz gesagt:
"Es gibt keinen Algorithmus, der dein Problem in akzeptabler Zeit exakt berechnet"
(zumindest ist diese Annahme in der Wissenschaft weit verbreitet)

Du kannst Heuristiken nehmen, die dir eine gewisse Güte garantieren oder
ohne Garantie in der Regel gute Ergebnisse errechnen.

Eine einfache Heuristik ist es, immer den Punkt mit dem kürzesten Abstand zu dem
zuletzt gewählten Punkt zu nehmen wie du ja in deinem Algo beschrieben hast.

Ich bin jetzt kein Fachmann für TSP, aber er gibt sicherlich zahlreiche
(leicht)kompliziertere Prozeduren um bessere Ergebnisse zu erhalten.

Da gibts z.B. evolutionäre Algorithmen...

CSpille schrieb:

Eine einfache Heuristik ist es, immer den Punkt mit dem kürzesten Abstand zu dem
zuletzt gewählten Punkt zu nehmen wie du ja in deinem Algo beschrieben hast.

Da werden aber einige Punkte nicht berücksichtigt. Wenn ich z.B. 100 Punkte habe, die auf einer Kreisbahn liegen und einen Punkt, der weiter abseits der Kreisbahn liegt, wird er eine Punkt nicht mit verbunden.

Das hat mich aber auf eine Idee gebracht: Wie wäre es, wenn man im ersten Schritt alle Punkte mit der Technik, die ich zu Anfang erwähnte. In den Nachfolgenden Schritten werden dann die verbleibenden Punkte "einsortiert". Was halte ihr von dem Ansatz?

Ich dachte du meintest folgendes:

1. Erstelle eine Menge M mit allen Punkten.
2. Erstelle eine Liste L mit behandelten Punkten
3. Entferne ein belibiges aus der Menge M und füge es zu L hinzu
4. Suche Element e in M mit geringstem Abstand zum letzten Element der Liste L
5. Entferne e aus M
6. Füge e an Ende von L hinzu
7. Falls M noch nicht leer, fahre mir 4 fort

Laufzeit: O(n^2)
Qualitätsgarantie: kein Plan ^^

Ja, so hab ich mir das auch vorgestellt, nur kann es dann passieren, dass Punkte übrig bleiben, da es immer noch andere Punkte gibt, die dem letzten Punkt am nächsten sind. Und irgendwann liegt wieder der Startpunkt am nächsten. Also wollte ich noch einen weiteren Durchlauf machen, in dem dann die verbleibenden Punkte einsortiert werden. Dazu dachte ich, nehme ich den Punkt, suche die Punkte, die am nächsten dran sind und füge den Punkt zwischen den beiden gefundenen Punkten in der neuen Liste ein. Die Laufzeit dürfte dann ein wenig größer sein als n².
Ich denke, ich probier das erst mal aus. Wenn noch Fragen sind, kann ich mich ja nochmal melden.

Punkteverbinder schrieb:

Ja, so hab ich mir das auch vorgestellt, nur kann es dann passieren, dass Punkte übrig bleiben, da es immer noch andere Punkte gibt, die dem letzten Punkt am nächsten sind. Und irgendwann liegt wieder der Startpunkt am nächsten. Also wollte ich noch einen weiteren Durchlauf machen, in dem dann die verbleibenden Punkte einsortiert werden. Dazu dachte ich, nehme ich den Punkt, suche die Punkte, die am nächsten dran sind und füge den Punkt zwischen den beiden gefundenen Punkten in der neuen Liste ein. Die Laufzeit dürfte dann ein wenig größer sein als n².
Ich denke, ich probier das erst mal aus. Wenn noch Fragen sind, kann ich mich ja nochmal melden.

Punkteverbinder schrieb:

5. Entferne e aus M

Folglich sinkt die Größe deiner Menge pro Durchlauf definitiv um 1
und der Algorithmus terminiert, wenn die Menge leer ist.

Punkte, die einmal berücksichtigt wurden, sind nicht mehr in der Menge.

EDIT:

Punkteverbinder schrieb:

Die Laufzeit dürfte dann ein wenig größer sein als n².

btw: Die Laufzeit sollte dann auch O(n^2) sein.

drakon

Bei 4. müsstest du am Anfang und am Ende schauen.

Greedy funktioniert hier ja nicht, daher kann das sehr schlecht werden.
(hab kurz in Wikipedia nachgeschaut; kann beliebig schlecht werden ;))

Ich würde wahrscheinlich in die Richtung des MST-Heuristik gehen:
http://de.wikipedia.org/wiki/Minimum-Spanning-Tree-Heuristik

O(n^2 * logn) ist nicht so viel schlechter, als die anderen, aber Vergleichsweise recht optimal (Faktor 2).

Gute Idee...

Kann er machen, nachdem er die ganz einfache Variante hingekriegt hat
Hast du eigentlich die Schweizer Fahne :hoppschwiiz: durchgesetzt?
:hoppschwiiz: :hoppschwiiz: :hoppschwiiz:

Das Ergebnis der MST-Heuristik kann er dann noch mit nem EA optimieren

Ich bin auch schon auf MST gestoßen, stelle mir das aber gar nicht so einfach vor, bei 2000 Punkten den MST zu finden.

Punkteverbinder schrieb:

Ich bin auch schon auf MST gestoßen, stelle mir das aber gar nicht so einfach vor, bei 2000 Punkten den MST zu finden.

Der Algorithmus ändert sich ja nicht mit der Anzahl der Knoten

Dann hast du sicherlich auch schon folgendes gelesen:
http://de.wikipedia.org/wiki/Minimaler_Spannbaum

Der Algorithmus von Kruskal ist noch ziemlich einfach, in den Prim müßte ich mich
erstmal wieder reindenken.

drakon

@CSpille
Nein. Marc++us hat die nach dem heroischen Sieg der Schweiz eingeführt.(siehe hier).

@Punkteverbinder
Das geht relativ effizient und einfach. Der Knackpunkt an der Sache ist eigentlich nur einen geeigneten Heap zur Hand zu haben. Um das garantiert effizient zu machen brauchst du nämlich einen Fibonacci Heap, welcher nicht unbedingt einfach zu implementieren ist. Es gibt irgendwo sogar ein halbfertige boost Implementierung, aber die ist afaik Fehlerhaft.

Siehe hier für das finden des MST
Prim:
http://en.wikipedia.org/wiki/Prim's_algorithm
und
Kruskal
http://en.wikipedia.org/wiki/Kruskal's_algorithm

Das (ohne einen Fib Heap) zu implementieren ist keine grosse Sache. Wo du das dann noch optimieren musst findest du eh besser direkt heraus, weil der Fib Heap halt eine hauptsächlich theoretische Betrachtung ist. In wiefern du das für dein Problem wirklich brauchst weiss ich jetzt nicht.