Suche Algorithmus: kürzesten Verbindung von Punkten einer 2D Punktwolke

Suche Algorithmus: kürzesten Verbindung von Punkten einer 2D Punktwolke

Impressum | Werbung

Geizhals » Forum » Programmierung »

Suche Algorithmus: kürzesten Verbindung von Punkten einer 2D Punktwolke (47 Beiträge, 546 Mal gelesen)

Top-100 | Fresh-100

Du bist nicht angemeldet. [ Login/Registrieren ]

Hallo,

Ich suche ein Verfahren, um die kürzeste Verbindung aller Punkte in einer 2D Punktwolke zu berechnen. Dabei können Verzweigungen und Kreuzungen der Verbindungen genutzt werden. Es muss nur ein zusammenhängendes Versorgungsnetz mit möglichst wenig Materialaufwand entstehen.

Hat jemand eine Idee, wie ich an das Problem herangehen könnte? Gibt es Strategien, um DIE optimale Lösung zu finden? Annäherungen reichen leider nicht aus.

Ideal wäre es, wenn jemand Quellen zu Code oder zu theoretischen Gedanken zu ähnlichen Themen zur Verfügung stellen könnte.

Vielen Dank - roddon.

PS: Die Programmiersprache ist dabei übrigens egal.

darf man fragen für was du es brauchst??
____________________________________________________________________
"Lehrt eure Kinder was wir unseren Kindern lehrten! Die Erde ist unsere Mutter.Was die Erde befällt, befällt auch die Söhne dieser Erde. Wenn die Menschen auf die Erde spucken, bespeien sie sich selbst. Die Erde gehört nicht den Menschen, der Mensch gehört der Erde.Alles ist verbunden, wie das Blut, das eine Familie vereint. Alles ist verbunden. Was die Erde befällt, befällt auch die Söhne dieser Erde."

Hallo,

danke schon mal für die ersten Antworten.

Ich versuche einer Freundin bei der Lösung einer Hausaufgabe im Rahmen ihres Mathe-Studiums zu helfen.
Die Punktwolke stellt dabei zum Beispiel zu versorgende Haushalte dar, die miteinander zum Beispiel mit einem Rohrsystem verbunden werden sollen.

roddon.

dann sollte sie die grundlagen allerdings schon kennen..

() ascii ribbon campaign - against html in mail and news
/\ - against microsoft attachments

Graphentheorie... Das ist lange her.

http://de.wikipedia.org/wiki/Algorithmus_von_Kruskal

er schreibt von einer punktwolke.. da hilft graphentheorie nicht viel..

edit: natürlich hilfts, aber zuerst muss er die einzelnen punkte sinnvoll verbinden

() ascii ribbon campaign - against html in mail and news
/\ - against microsoft attachments

09.07.2006, 14:44 Uhr - Editiert von promillo, alte Version: hier

War wohl wieder zu spät gestern.

Edit: Aber streng betrachtet geht es ja darum, aus einer Menge von möglichen Graphen den herauszufinden, dessen Spannbaum minimal ist (wenn man den die Abstände als Gewichtung nimmt).

09.07.2006, 14:46 Uhr - Editiert von Cornflakes Outta Skull Eater, alte Version: hier

ja stimmt eh, vorher muss er seine punkte halt triangulieren..

also irgendwie den gewichteten graphen basteln..

() ascii ribbon campaign - against html in mail and news
/\ - against microsoft attachments

Ich muss jetzt an einen gewissen Hrn. M. in der HTL SPengergasse denken - und kotzen
---
Der Schrecken der Deutschen!

WebLCD Heilmasseur, Massage, Atemtherapie

Hehe... Kenne ich leider/gottseidank nicht.

>Aber streng betrachtet geht es ja darum, aus einer Menge von möglichen Graphen

blöd nur, dass die menge unendlich ist

... (imho)

(oder zumindest extrem groß)

Der Optimallösung kommt man so aber sicher näher. Klar hat man ein Trade-Off zwischen Aufwand und Lösungsqualität.

War auch mein erster Gedanke. Aber so weit ich die Anforderung versteh, reicht der Algorithmus nicht aus. Ihm gehts nicht nur um direkte Verbindungen zwischen den Knoten.

Suche im Forum
Forums-FAQ
Kino 2006
Täglich frische Sudokus

Genau, richtig erkannt

http://de.wikipedia.org/wiki/Delaunay_Triangulation
http://www.gris.uni-tuebingen.de/gris/proj/dt/dt.html

dabei musst du halt eine ds entwerfen die gleich die entsprechende distanz zwischen den punkten speichert, also einen gewichteten graphen erstellt.. und dann brauchst nurmehr den vom mr cornflakes erwähnten algorithmus von kruskal drüberlaufen lassen..

() ascii ribbon campaign - against html in mail and news
/\ - against microsoft attachments

Da ich selbst "nur" Wirtschaftsinformatik studiere, bin ich in den theoretischen Grundlagen nicht sehr fit

Ich bin mir nicht sicher, ob ihr alle auf der richtigen Fährte seid. Es ist eher unwahrscheinlich, dass bei der Lösung des Problems alle Punkte durch Geraden verbunden sind, sondern eher, dass zum Beispiel 3 Punkte miteinander verbunden sind, indem sich 3 Geraden (die von den 3 Punkten ausgehen) im Schwerpunkt der Punkte treffen.
Es gibt also Verzweigungen.

Das nur noch mal zum Verständnis

09.07.2006, 15:07 Uhr - Editiert von roddon, alte Version: hier

das versteh ich nicht.. könntest du die angabe im wortlaut posten?

() ascii ribbon campaign - against html in mail and news
/\ - against microsoft attachments

also in der Informatik ist dass ein "Klassiker" und wird als "Travelling Salesman" Problem bezeichnet...

tipps mal in Google ein und du erhälst 400k Treffer dieser Art:

http://www.inf.fh-flensburg.de/lang/algorithmen/np/tsp/problem.htm

F.Z.

ich weiss nicht, weshalb alle anderen Poster da so rumeiern... wenn jemand Informatik oder dergleichen studiert hat, dann sollt er es auf jeden Fall unter dieser Bezeichnung kennen... ?!?!

09.07.2006, 18:25 Uhr - Editiert von Zappa F., alte Version: hier

Travelling Salesman ist aber ganz andere Baustelle.

Suche im Forum
Forums-FAQ
Kino 2006
Täglich frische Sudokus

Warum?

"die kürzeste Verbindung aller Punkte in einer 2D Punktwolke"

Wenn ich mir das ansehe, ist es das TSP.

Weil ihn nicht der kürzeste Pfad durch den Graphen interessiert sondern so was wie der minimale Spannbaum.

Suche im Forum
Forums-FAQ
Kino 2006
Täglich frische Sudokus

also dass glaube ich nicht...

Für mich ist das eindeutig Spanning Tree, allerdings mit dem Zusatz, dass Kanten auch verzweigen können. Ich denke mal, dass man da wohl nur annäherungsweise Lösungen bekommen kann.

Suche im Forum
Forums-FAQ
Kino 2006
Täglich frische Sudokus

Kruskal wurde bereits erwähnt, alternativ kannst du auch nach Prim-Jarnik suchen. Beide Algorithmen haben die Komplexität von O((n+m) log n). (n... Anzahl der Knoten, m... Anzahl der Kanten)

gendanke1: (falls die angabe von dir richtig ist)

ich würd bei den 2 punkten die am engsten zusammenliegen beginnen... (soweit der einfache teil

diese mit einer linie verbinden
dann den punkt suchen der am nächsten bei dieser linie liegt
und diesen dazuhängen , zur linie
dann den punkt der am nächsten bei diesen 2 linien liegt
dann den punkt der am nächsten bei diesen 3 linien liegt
usw.

(diese lösung skaliert zwar ganz fürchterlich

schlecht, imho müsste die lösung aber "optimal" sein ?????)

10.07.2006, 08:51 Uhr - Editiert von adhoc, alte Version: hier

Wenn ich Deinen Ansatz richtig verstanden habe, muss diese Lösung nicht optimal sein. Und zwar genau dann nicht mehr, wenn ein Folgepunkt zwar zunächst näher schient, die Punkte in der nächsten Ebene aber weiter weg sind, als die Punkte eines Alternativpunktes zum zuerst erwähnten Folgepunkt.

Genau aus diesem Grund sollte man auch alle Möglichkeiten evaluieren, wenn man eine optimale Lösung will.

möglich (kanns mir aber z.Z. nicht bildlich vorstellen)

kanst so einen von dir beschriebenen fall aufzeichnen...

(z.b. mit M$-paint

Man könnte Deinen Ansatz doch wie folgt modifizieren:
Solange noch nicht alle Punkte verbunden sind, verbinde jene Punkte mit dem niedrigsten Abstand.

Erzeugt das redundante Strecken? Wie könnte man das abfangen?

Die Lösung ist sicher nicht optimal. Probiers einfach mit 3 Punkten aus!

Suche im Forum
Forums-FAQ
Kino 2006
Täglich frische Sudokus

oha,

stimmt...

bei (einfachsten) gleichseitigen dreieck, scheint die kürzeste version über den "mittlepunkt" des dreiecks zu führen...

..

Genetische Algorithmen könnten evt. helfen, siehe z.B. http://www.ads.tuwien.ac.at/raidl/TravSale/ga.html

Damit wird er aber nicht die optimale Lösung finden, sondern nur eine annähernd optimale Lösung.

Suche im Forum
Forums-FAQ
Kino 2006
Täglich frische Sudokus

Er könnte schon die optimale Lösung finden, aber wahrscheinlich braucht das zuviel Zeit.

Hört sich nach dem in der Mathematik und Informatik sehr beliebten Problem des Handlungsreisenden an (NP-vollständig).

Lösungsansatz geht mittels "nächster Nachbar".

Klassiker .. Lösung gibts im Sedgewick

Bashing:

Wer den Sedgewick nicht zu Hause hat, ist kein Informatiker.

---

Lieber ein Betriebssystem, dass nach einem Raubtier benannt ist, als eines, dass nach einem Rindviech benannt ist und sich auch so verhält.

13.07.2006, 00:03 Uhr - Editiert von Nemealion, alte Version: hier

Dabei können Verzweigungen und Kreuzungen
der Verbindungen genutzt werden.

Heisst das es gibt es nur einen Pfad der sich überschneiden darf, oder kann es auch fully meshed sein ?

lg Amo

ich *PIEP* auf die sig. alles was mir gfallt is sowieso zu groß ...

Dieses Forum ist eine frei zugängliche Diskussionsplattform.
Der Betreiber übernimmt keine Verantwortung für den Inhalt der Beiträge und behält sich das Recht vor, Beiträge mit rechtswidrigem oder anstößigem Inhalt zu löschen.
Datenschutzerklärung