Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > de.sci.electronics > #201439

Re: Kleines mathematisches Problem

Show all headers | View raw

MaWin schrieb:
> "Stefan" <df9bi@arcor.de> 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

Back to de.sci.electronics | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

Kleines mathematisches Problem Stefan <df9bi@arcor.de> - 2016-02-04 17:49 +0100
  Re: Kleines mathematisches Problem Bernd Nebendahl <Bernd_Nebendahl@web.de> - 2016-02-04 17:54 +0100
    Re: Kleines mathematisches Problem Stefan <df9bi@arcor.de> - 2016-02-04 18:37 +0100
  Re: Kleines mathematisches Problem "MaWin" <me@private.net> - 2016-02-04 18:03 +0100
    Re: Kleines mathematisches Problem Stefan <df9bi@arcor.de> - 2016-02-04 18:23 +0100
      Re: Kleines mathematisches Problem "MaWin" <me@private.net> - 2016-02-04 18:36 +0100
        Re: Kleines mathematisches Problem Stefan <df9bi@arcor.de> - 2016-02-04 19:00 +0100
    Re: Kleines mathematisches Problem Hans-Peter Diettrich <DrDiettrich1@aol.com> - 2016-02-04 22:32 +0100
    Re: Kleines mathematisches Problem Robin Koch <robin.koch@t-online.de> - 2016-02-05 02:57 +0100
  Re: Kleines mathematisches Problem Marc Santhoff <m.santhoff@t-online.de> - 2016-02-04 18:20 +0100
  Re: Kleines mathematisches Problem Thomas Prufer <prufer.public@mnet-online.de.invalid> - 2016-02-04 18:23 +0100
    Re: Kleines mathematisches Problem Robin Koch <robin.koch@t-online.de> - 2016-02-05 03:08 +0100
  Re: Kleines mathematisches Problem Lutz Schulze <lschulze@netzwerkseite.de> - 2016-02-04 18:59 +0100
    Re: Kleines mathematisches Problem Stefan <df9bi@arcor.de> - 2016-02-05 08:11 +0100
      Re: Kleines mathematisches Problem Christian Müller <spamalottomat@yahoo.de> - 2016-02-05 16:11 +0100
        Re: Kleines mathematisches Problem Stefan <df9bi@arcor.de> - 2016-02-05 17:13 +0100
  Re: Kleines mathematisches Problem Eric Brücklmeier <usenet@nerdcraft.de> - 2016-02-05 11:05 +0100
  Re: Kleines mathematisches Problem Thomas Heger <ttt_heg@web.de> - 2016-02-14 18:53 +0100
    Re: Kleines mathematisches Problem Stefan <df9bi@arcor.de> - 2016-02-14 20:04 +0100
      Re: Kleines mathematisches Problem Thomas Heger <ttt_heg@web.de> - 2016-02-15 05:13 +0100
        Re: Kleines mathematisches Problem Stefan <df9bi@arcor.de> - 2016-02-16 14:08 +0100
    Re: Kleines mathematisches Problem Hans-Peter Diettrich <DrDiettrich1@aol.com> - 2016-02-15 18:33 +0100

csiph-web