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

Groups > de.sci.electronics > #202156

Re: Kleines mathematisches Problem

Show all headers | View raw

Am 04.02.2016 17:49, schrieb Stefan:
> Hallo,
>
> vieleicht fehlt mir nur ein Schlüsselwort um was passendes zu finden.
>
> Folgendes Problem:
>
> Ein Roboter befindet sich an der Position (X1,Y1) auf einer Fläche. Er
> soll auf kürzestem Weg die Position (X2,Y2) anfahren.
>
> Problem dabei, es gibt auf dem Weg diverse Hindernisse, also Bereiche,
> die umfahren werden müssen.
>
> Ich stell mir das jetzt so vor, dass ich die Fläche in Kästchen
> aufteile, z.B. 100 Kästchen in X-Richtung und 100 Kästchen in
> Y-Richtung. Jedes Kästchen wird entweder mit 0 oder 1 markiert. Die
> erlaubten Kästen haben den Wert 0, die verbotenen den Wert 1.
>
> Die Position der Hindernisse ist fest, ebenso die Position des Ziels
> (x2,y2). Lediglich die Startposition des Roboters (x1,y1) ist variabel.
>
> Wie finde ich jetzt den kürzesten Weg von (x1,y1) nach (x2,y2)?
>
> Eine Idee, die mir gerade kommt geht so: Ich definiere eine Anzahl
> zusätzlicher Fixpunkte auf der Fläche, die so angeordnet sind, dass
> jeder Punkt auf der Fläche einen dieser Fixpunkte direkt, d.h. auf
> geradem Weg anfahren kann. Für jeden dieser Fixpunkte gibt es einen fest
> programmierten Weg zum Ziel. Jetzt muss ich nur noch den Fixpunkt
> finden, den ich in gerader Linie erreichen kann und der dem Ziel am
> nächsten liegt.
>
> Den kann ich dann noch optimieren.
>
> Ich habe so die Vermutung, dass wenn ich diese Fixpunkte geschickt wähle
> damit schon den optimalen Weg gefunden habe...
>
> Vieleicht kann man die Fixpunkte auch automatisch festlegen...
>
> Hat noch jemand andere Ideen dazu?
>
Meiner Ansicht nach beziehen sich die bisherigen Vorschläge auf sowas 
wie das 'travelling sales man Problem'. Das ist die Frage nach der 
Reihenfolge, in der zu besuchende Punkte angefahren werden sollen.

Du suchst aber nach der kürzesten Strecke, die der Roboter von A (x1,y1) 
nach Punkt B (x2, y2) auf einer Ebene fahren soll, ohne gegen 
Hindernisse zu stoßen.

Ich nehme nun den einfachsten Fall und es gibt genau ein Hindernis. Der 
weg von A nach B auf einer Geraden durch beide Punkte wäre der kürzeste, 
sollte dort kein Hindernis sein.

Ist dort aber eines, dann muß der Roboter ausweichen und zwar zu der 
Seite, wo er weniger von dieser Geraden abweichen muß. Er muß dann 
soweit ausweichen, daß er an dem Hindernis gerade vorbeikommt.

Jetzt kann man diesen Punkt bestimmen ( C an (x3, y3)  ) und die Strecke 
in zwei Teile Teilen und das ganze wiederholen für A->C und C->B.

Das macht man dann solange, bis kein Hindernis mehr auf dem Fahrweg ist.


TH

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