Punkte einer Punktwolke verbinden - Suche geeigneten Algorithmus



  • 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.



  • 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.



  • @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.


Anmelden zum Antworten