Kleines mathematisches Problem

04/02/2016 - 17:49 von Stefan | Report spam
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?

Gruß

Stefan
 

Lesen sie die antworten

#1 Bernd Nebendahl
04/02/2016 - 17:54 | Warnen spam
Am 2016-02-04 um 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?



Ohne das genau analysiert zu haben. Ich denke dass man dein Problem wie
das "Problem des Handlungsreisenden" behandeln kann (siehe z.B.
<https://de.wikipedia.org/wiki/Probl...senden>)

Dazu existiert umfassendes wissenschaftliches Material.

Bernd

Ähnliche fragen