Hallo,
ich stehe vor einer Aufgabe um die kürzeste Strecke zwischen Punkt 1 und
Punkt 10 zu berechnen.
Gegeben eine Startkoordinate x,y.
Weitere 10 Koordinaten.
Da die Punkte mit einer Toleranz von nur z.B. 4 cm genau getroffen
werden müssen suche ich eine Berechnung der kürzesten Strecke.
Also ist um jeden Punkt ein Kreis mit 8cm Durchmesser und gesucht wird
jeweils die Koordinate die am Kreis tangiert.
Hat jemand Tipps bzw. Quellen so einer Berechnung?
Viele Grüße
Josef schrieb:> Da die Punkte mit einer Toleranz von nur z.B. 4 cm genau getroffen> werden müssen suche ich eine Berechnung der kürzesten Strecke.> Also ist um jeden Punkt ein Kreis mit 8cm Durchmesser und gesucht wird> jeweils die Koordinate die am Kreis tangiert.
wieso tangiert.
Die kürzeste Strecke zwischen 2 Punkten ist eine Gerade.
Und wenn du um die Punkte einen Kreis hast, dann ändert das nicht viel.
Denn die Gerade ist innerhalb des Kreises ja ein Radiusvektor und der
steht immer senkrecht zum Umfang. D.h. die Distanz zu diesem Punkt kann
maximal um +- Radius von der rechnerischen Distanz zu diesem Punkt
abweichen, wenn der korrekte Punkt innerhalb eines Fehlerkreises rund um
den idealen Punkt liegt.
Einfach mal aufzeichnen, dann wirds klarer.
Ausser natürlich, ich habe deine Aufgabe missverstanden.
Das Problem klingt irgendwie sehr KOMPLEX.
Wenn ich das richig verstanden habe sind es ja neun Wegstrecken. Ist die
Reihenfolge zwischen den Punkten festgelegt oder soll diese auch in
Hinblick auf die kürzeste Strecke optimiert werden? Könntest Du mal eine
kleine Graphik beifügen, die Dein Problem etwas näher verdeutlicht.
Derzeit würde es meiner Meinung nach auf das Problem des
Handlungsreisenden (gerne mal den Wiki-Artikel lesen) hinauslaufen. Wenn
Du da wirklich die kürzeste Entfernung berechnen willst, wirst Du nicht
um das berechnen fast aller Möglichkeiten herumkommen.
Gruß Magelan
Karl Heinz Buchegger schrieb:> Ausser natürlich, ich habe deine Aufgabe missverstanden.
das hast Du, er will die Punkte nicht exakt anfahren, es reicht wenn er
in 4cm Abstand vorbeifährt
Bernd schrieb:> Karl Heinz Buchegger schrieb:>> Ausser natürlich, ich habe deine Aufgabe missverstanden.>> das hast Du, er will die Punkte nicht exakt anfahren, es reicht wenn er> in 4cm Abstand vorbeifährt
Ah.
Jetzt hab ichs.
Er will eine Sequenz von 10 Punkten nacheinander abfahren und sucht die
Distanz, wenn er nicht genau den Punkt anfahrten muss sondern auch zb 4
cm vorher schon umdrehen und zum nächsten Punkt fahren kann.
Jau. Das ist wirklich komplex.
Walleby schrieb:> da würde ich mit Vektoren rechnen. Der Abstand von Punkten ist ja> relativ simpel.
das schon, aber das klingt nach verschärftem Travelling salesman Problem
Bernd schrieb:> Karl Heinz Buchegger schrieb:>> Ausser natürlich, ich habe deine Aufgabe missverstanden.>> das hast Du, er will die Punkte nicht exakt anfahren, es reicht wenn er> in 4cm Abstand vorbeifährt
Er sucht also im Grunde genommen folgenden Algorithmus:
1) Die Kreismittelpunkte werden miteinander verbunden und zwar so, dass
die Verbindung der Mittelpunkte Kreis1->Kreis2, Kreis2->Kreis3,
Kreis3->Kreis4... die optimale kürzeste Distanz bilden. Unter dem
Begriff des "Handelsreisenden" wird das Problem über den
Ameisenalgorithmus (MMAS = Min Max Ant System) gelöst.
2) Nun ist die Reihenfolge der Kreise bekannt. Es werden die Geraden
zwischen den Mittelpunkten gebildet.
3) Es werden die Schnittpunkte der Sekanten gebildet.
4) Die Reihenfolge der Kreise bestimmt die Reihenfolge, mit welcher die
Sekantenschnittpunkte abgefahren werden müssen.
Et voilàt: Du hast die kürzeste Strecke.
Martin Schwaikert schrieb:> Er sucht also im Grunde genommen folgenden Algorithmus:>> 2) Nun ist die Reihenfolge der Kreise bekannt. Es werden die Geraden> zwischen den Mittelpunkten gebildet.
Nur dass sich durch die Möglichkeit auf nur 4cm genau treffen zu müssen
unter umständen eine andere Route als die beim klassischen TSP als ideal
erweisen kann. Damit ist dein Algorithmus maximal zum Auffinden einer
Startlösung für irgendeine Heuristik zu gebrauchen.
Josef schrieb:> anbei eine Skizze, gesucht die rote Strecke.
Die Strecken durch Punkt 6 (hin und wieder weg) sind hier definitiv
falsch. Das geht kürzer, wenn man nicht durch den Mittelpunkt fährt,
sondern eine Gerade zieht, die dann irgendwo durch den Kreis des Punktes
6 führt.
Wenn ich mir die Zeichnung ansehe, glaube ich, dass auch schon die
ersten beiden Geraden vom Startpunkt aus suboptimal sind.
Ich würde folgenden Algorithmus verwenden:
1. Ziehe Geraden von Mittelpunkt zu Mittelpunkt
2. Berechne die Winkelhalbierenden der Geraden
Der Punkt für die minimale Wegstrecke liegt dann auf dieser
Winkelhalbierenden. Im allgemeinen ist das der Schnittpunkt der
Winkelhalbierenden mit dem Kreis. Aber nicht immer, wie man an Punkt 6
sieht. Hier liegt der gesuchte Punkt irgendwo auf der
Winkelhalbierenden, da der Öffnungswinkel der beiden Geraden sehr groß
ist. Aber das ist nur noch ein simples Minimax-Problem und leicht mit
Trigonometrie zu lösen.
Wie ich auf Winkelhalbierende komme? Einfach aus Symmetrieüberlegungen.
Die gezeichnete rote Linie ist garantiert nicht optimal. Da sind viel zu
viele Asymmetrien drin.
Ich würde es so lösen:
- Gerade von P1 zu P3
- Abstand der Geraden zu P2 ermitteln (Senkrechte auf der Geraden durch
P2)
- Wenn der Abstand <4cm, dann diesen Punkt als neuen P2 speichern
- Wenn der Abstand >4cm ist, dann ist P2 der Schnittpunkt vom Kreis (P2)
und der Senkrechten.
Und dann das selbe mit P2 zu P4 usw.
Ist zwar noch nicht perfekt, aber nahe am Maximum.
Gerade wenn mehr als 3 Punkte in reihe sitzen (wie bei P6 im Beispiel)
kann es zu Abweichungen kommen.
@Josef
Ist die Skizze, die Du hier eingestellt hast nur ein Beispiel? Ändern
sich die Positionen der Punkte von Lauf zu Lauf oder sind diese im
Vorfeld festgelegt? Wie auch immer... die kürzeste Strecke zu berechnen
ist ein NP-vollständiges Problem (Stichwort "Problem des
Handlungsreisenden" o. englisch "Traveling Salesman Problem"). D. h. die
Laufzeit des Algorithums ist min. exponentiell, wenn Du die optimale
Strecke mit Sicherheit finden willst.
Das gilt bereits schon dafür in welcher Reihenfolge Du die Puntke
anfahren sollst um am Ende die kürzeste Strecke zu erhalten. Die Sache
mit dem Radius um alle Punkte macht die Sache dann noch ein Stück
komplexer.
Gruß
Christoph
@Josef
Sehe gerade, dass Du geschrieben hast, dass die Reihenfolge bekannt ist.
Dann sieht das Problem schon etwas anders aus... sehr interessant :)
Gruß
Christoph
> die Reihenfolge ist bekannt
Lösung also kindereinfach und schon beschrieben.
> Wie ich auf Winkelhalbierende komme
Aus völlig richtigen Überlegungen.
> dass auch schon die ersten beiden Geraden vom Startpunkt> aus suboptimal sind.
Unsauber gezeichnet.
Insgesamt klingt das aber sehr nach primitiver Hausaufgabe,
bei der er seine eigenen Gehirnwindungen aktivieren soll,
wenn er welche hat.
Meine Idee um den optimalen Weg zu finden:
Gedanklich steckt in jedem Kreis ein Pinn, der innerhalb des Kreises
ohne Widerstand bewegt werden kann. Start und Ziel erhalten auch je
einen Pinn, die aber fest sind. Die Pinne werden in der vorgegebenen
Reihenfolge mit einem "Gummi" (unter Spannung) miteinander verbunden.
Das Gummi zieht sich nun zusammen und die Pinne sollten dann innerhalb
der Kreise die Position einnehmen, die optimal für die kürzeste Strecke
ist. Das Gummi zeigt unter der geringsten Spannung die kürzeste Strecke
an.
Jetzt muss man das nur in Code giessen ;)
Gruß
Christoph
Der Kreis kann durch eine Funktion beschrieben werden... wenn man jetzt
davon ausgeht dass man jeden Punkt im Kreis durch eine Funktion
berechnen kann mit 2 Variablen(Winkel+Länge) kann man die gesamt Strecke
mit 10*2 also 20 Variablen ausdrücken, und diese Funktion muss man dann
einfach möglichst klein kriegen
MaWin schrieb:> Handlungsreisender
Travelling actor's problem ;) Was tu ich nur, wo fahr ich hin!
Die Idee mit den Pins ist schon mal nicht schlecht und entspricht doch
Franks Idee...
Frank M. schrieb:> Ich würde folgenden Algorithmus verwenden:>> 1. Ziehe Geraden von Mittelpunkt zu Mittelpunkt> 2. Berechne die Winkelhalbierenden der Geraden
...wobei der 5. Kreis entfernt werden muss, da der Weg über die
Mittelpunkte der Kreise den Kreis 5 derart schneidet, dass die gesamte
Entfernung größer würde, würde man ihn nur am Rand anfahren.
mfg mf
Frank M. schrieb:> 1. Ziehe Geraden von Mittelpunkt zu Mittelpunkt> 2. Berechne die Winkelhalbierenden der Geraden> Wie ich auf Winkelhalbierende komme? Einfach aus Symmetrieüberlegungen.> Die gezeichnete rote Linie ist garantiert nicht optimal.
Die Überlegung mit den Winkelhalbierenden und den Symmetrien ist prinzi-
piell richtig. Allerdings darfst du dabei nicht die Winkelhalbierenden
der Verbindungslinien zwischen den Kreismittelpunkten betrachten, son-
dern diejenigen der Liniensegemente des Lösungwegs. Das macht die Sache
komplizierter, weil man die Winkelhalbierenden erst dann bestimmen kann,
wenn man die Lösung bereits kennt.
Der optimale Weg ist also ein Polygonzug, bei dem für jeden der zu
passierenden Kreise bis auf den letzten eine der beiden folgenden
beiden Aussagen gilt:
1. Er geht geradlinig durch den Kreis hindurch.
2. Er führt auf einer Geraden a zu einem Punkt P auf dem Kreisumfang
und biegt dort in eine Gerade b ab, so dass der Kreisradius durch
P den Winkel zwischen a und b halbiert.
Der letzte Kreis wird in Richtung seines Mittelpunkts angefahren, wobei
der Weg an seinem Umfang endet.
Ich habe mal mit Kig ein Beispiel konstruiert (s. Anhang), dabei aller-
dings ein wenig geschummelt, da ich den letzten Kreis so platziert habe,
dass sein Mittelpunkt auf dem zuvor konstruierten Weg liegt und nicht
umgekehrt, wie es eigentlich der Aufgabenstellung entspricht (Hätte ich
es ohne Schummeln geschafft, wäre aus der Konstruktion ein direktes
Lösungscerfahren abgefallen).
Mit den genannten Kriterien kann zwar ein gegebener Weg auf Optimalität
geprüft werden, sie liefern aber leider kein Verfahren, diesen Weg di-
rekt zu berechnen oder zu konstruieren (zumindest ist mir diesbezüglich
nichts eingefallen). Ich vermute, dass es bei zwei oder mehr Knicken im
Weg keine geschlossene Lösungsformel für das Problem gibt.
Es führt also wohl kein Weg an einer numerischen Lösung mittels eines
Iterationsverfahrens vorbei. Man könnte bspw. die Startrichtung des Wegs
so lange variieren, bis nacheinander alle Kreise in der richtigen Rei-
henfolge getroffen werden. Dabei wird vom Startpunkt aus immer so viel
des Wegs berechnet, bis er einen der Kreise verfehlt. Je nachdem, ob der
Weg links oder rechts an dem Kreis vorbeiläuft, und ob die Anzahl der
bisherigen Richtungsänderungen gerade oder ungerade ist, muss der Start-
winkel für die nächste Berechnung um einen geeigneten Betrag vergrößert
oder verkleinert werden. Wenn der Weg schließlich auch den letzten Kreis
passiert, wird noch so lange weiteroptimiert, bis der Weg exakt durch
seinen Mittelpunkt verläuft.
Von dem so gefundenen Weg wird dann noch der Radius des letzten Kreises
weggelassen, weil es ja genügt, dessen Umfang zu erreichen.
Der gefundene Weg entspricht übrigens dem eines Lichtstrahls, der vom
Startpunkt ausgesandt wird, an mehreren halbdurchlässig verspiegelten
Zylindern (die Kreise) reflektiert wird oder diese brechungsfrei durch-
dringt und schließlich durch den Mittelpunkt des letzten Kreises ver-
läuft.
Man könnte also das oben beschriebene rechnerische Verfahren auch physi-
kalisch realisieren, in dem man am Startpunkt einen Laserpointer drehbar
moniert, alle Kreise bis auf den letzten durch halbdurchlässig verspie-
gelte Zylinder ersetzt und den Laserpointer so lange dreht, bis der
Strahl genau ins Ziel fällt. Der gesuchte Weg ist dann der Weg des
Strahls, den man mit etwas Nebel oder Rauch sichtbar machen kann.
Alternativ könnte man statt des Laserpointers eine punktförmige, aber
nicht bündelnde Lichtquelle (kleine LED o.ä.) nehmen und am Zielpunkt
eine kleine Kamera platzieren. Der Punkt, an dem die Lichtquelle im
letzten Zylinder erscheint, wird auf diesem markiert und die Kamera
anschließend an diese Position gestellt. Dann wird der Punkt markiert,
an dem die Lichtquelle im vorletzten Zylinder erscheint. So wird fort-
gefahren, bis alle Zylinder markiert sind. Der gesuchte Weg führt dann
vom Startpunkt über die markierten Punkte zum Ziel.
Es muss allerdings in beiden Varianten dafür gesorgt werden, dass der
Strahl die einzelnen Zylinder tatsächlich nur in der vorgesehenen Rei-
henfolge durchläuft, sonst gelangt das Licht u.U. auf mehreren Wegen zum
Ziel. Da man den optimalen Weg aber ungefähr vorhersehen kann, hilft es
evtl., zwischen den Zylindern geeignete Blenden aufzustellen, die die
Reflexion in "falsche" Richtungen unterbinden.
Nur aus Interesse noch ein paar Fragen an Josef:
- Wozu dient das Ganze überhaupt?
- Soll die Berechnung tatsächlich auf einem Mikrocontroller stattfinden?
- Wie sind die zeitlichen Anforderungen?
MaWin schrieb:> Lösung also kindereinfach und schon beschrieben.
Ich habe doch schon immer gewusst, dass du als Wunderkind geboren bist
;-)
Karl Heinz Buchegger schrieb:> wieso tangiert.
Weil er die Punkte nicht reffen muss, sondern nur, ihnen nahekommen
muss.
WelchenPunkt er dabei durchfahren muss ist aber nicht direkt
berechenbar, sondern muss aus der Umgebung abgeleitet werden.
Die Lösung ist einfach:
Man bestimmt die Gerade der Nachbarpunkte allgemein, hat daraus die
Steigung und somit die Tangente für den Fall verschiederer Kreispunkte.
Diese Distanz muss so ermittelt werden, dass sie minimal ist (Ableitung
= null).
> Die kürzeste Strecke zwischen 2 Punkten ist eine Gerade.
Dies gilt dann, wenn diese Gerade den Kreis von oben schneidet.
Man muss davon ausgehen, dass das zuminstes in jedem zweiten Punkt der
Fall sein muss, da sich sonst keine Geradenstäcke finden lassen, die bei
allen Zwischenpunkten zu einer Lösung führen.
Yalu X. schrieb:> Man könnte also das oben beschriebene rechnerische Verfahren auch physi-> kalisch realisieren
Wow, ich hab bis jetzt an einen amerikanischen Zeitungsjungen auf einem
Fahrrad gedacht, der nur begrenzt weit werfen kann, aber möglichst
schnell seine Runde durch den noch nicht/nicht mehr so dicht besiedelten
Trailerpark nehmen will. :) mfg mf
Joachim минифлоть schrieb:> Die Idee mit den Pins ist schon mal nicht schlecht und entspricht doch> Franks Idee...
Ich fürchte, dass die beiden Ideen sich nicht entsprechen. Die Idee mit
den Winkelhalbierenden funktioniert eigentlich nur für drei Punkte.
Jeder weitere Punkt bzw. dessen Position hat nämlich nicht nur eine
direkte Auswirkung auf die Winkelhalbierenden, an denen er beteiligt
ist, sondern indirekt auch auf alle Winkelgeraden im System. D. h. bei
Verschiebung des sechsten Punktes/Kreises in der Skizze gebe es eine
direkt Auswirkungen auf die Winkelhalbierende zw. den Punkten [4, 5, 6],
[5, 6, 7] und [6, 7, 8]. Aber auch indirekte Auswirkungen zw. den
Punkten [3, 4, 5], [7, 8, 9] usw. Wobei der Effekt (die Größe der
notwendigen Korrektur von bestimmten Geraden) mit zunehmender Entfernung
abnimmt.
Die Folge ist, dass wir hier bei einem iterativen Vorgehen landen, bei
dem nach Zunahme eines neuen Punktes (bzw. der Verschiebung eines
Punktes) alle bisherigen Geraden neu berechnet werden müssen. Und zwar
solange iterativ bis eine vorher festgelegte Genauigkeit erreicht ist.
D. h. die Längenverbesserung der gesamten Strecke bei zwei
aufeinanderfolgenden Iterationen liegt unterhalb eines festgelegten
Schwellwertes. Damit kriegt man eine Annährung an die optimale Strecke
hin.
Ist auf jeden Fall eine schöne Aufgabe und ich hoffe, dass meine
Erklärung verständlich ist;)
PS.: Der Thread gehört wirklich nicht in diesen Bereich.
> Man bestimmt die Gerade der Nachbarpunkte allgemein, hat daraus die> Steigung und somit die Tangente für den Fall verschiederer Kreispunkte.> Diese Distanz muss so ermittelt werden, dass sie minimal ist (Ableitung> = null).
Wobei die Knickpunkte (x_i, y_i) ja alle jeweils innerhalb einer der
abgeschlossenen Kreisscheiben liegen.
Wenn Punkt i jetzt um weniger als den doppelten Kreisradius von der
Verbidungsgerade zwischen Punkt i-1 und Punkt i+1 entfernt liegt, kommen
sowohl Punkte im Innern als auch Punkte auf der Kreislinie in Frage.
Mathematisch gesehen lässt sich das nicht in einen Ausdruck pressen, der
mittels Ableitung minimiert wird, es geht also nicht ohne
Fallunterscheidung. Und zwar für jeden einzelnen Punkt.
Damit haben wir bei n Punkten, wobei Punkt 1 und Punkt n genau getroffen
werden sollte, 2^(n-2) Fälle zu unterscheiden (wir reden noch von einer
festgelegten Reihenfolge!) Wenn n nicht ganz klein ist, geht es damit
also schon mal nicht "ganz einfach", zumindest nicht wenn eine endliche
;-) Laufzeit des Programms gewünscht wird. Evtl. kann man aber einige
Fälle von vornherein eliminieren (wo es mit dem lotrechten Abstand nicht
hinhaut).
Mein Ansatz wäre folgender, der zu einer Näherungslösung führt:
1. Linie als Knickgerade initialisieren, die alle Punkte genau trifft
2. Nacheinander für jeden Punkt von 2. bis zum n-1-ten den Eckpunkt
innerhalb des Spielraums so versetzen, dass die Länge der beiden
angrenzenden Abschnitte minimiert wird.
3. Nachdem in (2) über alle Eckpunkte iteriert wurde, selbiges noch
k-mal wiederholen. Je höher k, desto besser die Lösung.
Ich früchte man muss da alle Punkte gleichzeitg reinnehmen. Es ist ein
nterschied, ob es mit einem nächsten Punkt in die eine, oder andere
Richtung knickt.
Am Besten man versucht zunächst, durch alle Punkte mit einer Gerade
durchzugehen und bricht diese Kette dort, wo der grösste Abstand ist.
Von dort aus untersucht man das in zwei Teilproblemen, u.s.w
Es wird jeweils der Punkt neu bestimmt, der das grösste Problem
darstellt.
Orange ist die erste lösung
türkis die beiden zweiten
und gruen die letzte
es kann natürlich sein, das es bei komplexeren Aufrüchen mehrere
Lösungswege gibt, die dann zu unterschiedlichen Teillösungen führen.
dann müsste man am Ende die kürzeste suchen
Josef schrieb:> anbei eine Skizze, gesucht die rote Strecke.
Lässt sich die Strecke folgendermassen charakterisieren?
- Der jeilige Kreisradius ist Winkelhalbierende den an diesen
Kreis ankommenden / wegführenden beiden Teilstrecken.
Oder ist meine mathematische Ituition falsch...?
Lässt sich zB anhand eines optimalen Weges zeigen, daß obige Bedingung
nicht erfüllt ist?
Hallo,
die optimierten Punkte habe ich über Winkelhalbierende berechnet.
Der Sonderfall dass eine Linie durch einen Kreis geht wie bei Punkt6 vom
Beispiel soll durch die Prüfung geht die Gerade durch Kreis geprüft
werden.
