Path: csiph.com!fu-berlin.de!uni-berlin.de!individual.net!not-for-mail From: Hans-Peter Diettrich Newsgroups: de.sci.electronics Subject: Re: Kleines mathematisches Problem Date: Thu, 04 Feb 2016 22:32:20 +0100 Lines: 48 Message-ID: References: Mime-Version: 1.0 Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 8bit X-Trace: individual.net Dy8xib1VKFNJjOwpk6zSvAHdsMl2ADmCHpNvoIesJ4oABEatlW Cancel-Lock: sha1:a0a55sIlTLr7BsQlcWWgEZzi8x4= User-Agent: Thunderbird 2.0.0.21 (Windows/20090302) In-Reply-To: Xref: csiph.com de.sci.electronics:201439 MaWin schrieb: > "Stefan" schrieb im Newsbeitrag > news:n8vvfc$nqq$1@news.albasani.net... > >> Wie finde ich jetzt den kürzesten Weg von (x1,y1) nach (x2,y2)? > > Du füllst alle erlaubten Felder um x1,y1 mit 2 > Dann füllst du alle erlaubten um die Felder auf denen 2 steht > mit 3, dann füllst du alle erlaubten um die Felder auf denen > 3 steht mit 4 usw. bis du das Feld x2,y2 füllen musst. Diesen Algorithmus habe ich in einem Layout-Programm für Leiterkarten (Autorouter) schon mal verwendet. Nur > Der Algorithmus heisst Lee's maze algorithmus das wußte ich noch nicht. > Den Weg zurück findet man durch Nachbarschaftssuche nach dem > nächstkleineren. Letztlich reichen auch 4 Zahlenwerte (nach 4 > kommt wieder 2), dann weisst du aber nicht so schnell, wie weit > es war. Das Finden des Rückwegs wird etwas knifflig, wenn man den geometrischen Abstand statt der Manhatten-Distanz nutzen möchte. Beim Layout ist das weniger tragisch, wenn man die Richtung der Leitungen auf 45° oder gar 90° beschränkt, bei einer freien Bewegung sollte man prüfen, wo signifikante Richtungswechsel (um die Ecke eines Hindernisses herum) auftauchen, und ob sich auf der direkten Verbindung zwischen zwei solchen Punkten Hindernisse befinden, die eine gerade Bahn unmöglich machen. Eventuell könnte auch ein Verfahren zur Konstruktion einer "konvexen Hülle" helfen. Dort könnte man die Punkte mit der größten Abweichung von der geraden Verbindung rauswerfen, bis man die schlankste Hülle gefunden hat. Dumm nur, wenn die Hindernisse nicht punktförmig sind... Ein Graph mit gewichteten Kanten könnte auch hilfreich sein. Nur müssen dann (wie bei der konvexen Hülle) erst mal alle Tangenten zwischen den Objekten berechnet werden, um die Knoten und Kanten insgesamt zu finden. Dabei sollte die Größe des Roboters berücksichtigt werden, einmal um die Punkte zu finden, an dem der Roboter ein Hindernis gerade mal streift, und um andererseits zu enge Passagen auszuschließen, durch die der Roboter nicht durchpaßt. Der Hinweis von Lutz ist auch interessant, wenn man die mögliche Beschleunigung und die Zeit für Drehungen des Roboters einbezieht, d.h. auf minimale Fahrzeit statt auf minimale Strecke optimiert. DoDi