Pfadfindung - Wegberechnung - Optimierung der Fahrliste

04/06/2009 - 09:29 von Andreas Ott | Report spam
Hallo!

Hardware - Aufbau
http://www1.minpic.de/bild_anzeigen...6&ende

Die Maschine hat einen Einlauf und einen Auslauf.
Die Markiereinheit bewegt sich nicht, ist fix!! Es bewegen sich
lediglich die Achsen.


Es kommt eine unsortierte Liste, die ich nach dem kürzesten Weg
abfahren muss. Nummern sind hier nicht relevant. Taktzeit ist wichtiger,
schnell.

##### jetzt wird noch komplizierter ######
##### wo könnte ich da nachschauen, math. Stichwort
##### wer hat hier einen Algorithmus?
##### der auch zu verstehen ist ;-)
Das habe ich gefunden, komme aber nicht so recht weiter.
Pfadfindung - Wegberechnung
http://www.vbarchiv.net/tipps/details.php?id75
http://wiki.delphigl.com/index.php/...re_Algebra


Was will ich?

Input.
mylistSortWay.push_back(CSortWay(50,10));
mylistSortWay.push_back(CSortWay(50,40));
mylistSortWay.push_back(CSortWay(50,70));
mylistSortWay.push_back(CSortWay(50,100));

mylistSortWay.push_back(CSortWay(90,10));
mylistSortWay.push_back(CSortWay(90,40));
mylistSortWay.push_back(CSortWay(90,70));
mylistSortWay.push_back(CSortWay(90,100));

mylistSortWay.push_back(CSortWay(10,10));
mylistSortWay.push_back(CSortWay(10,40));
mylistSortWay.push_back(CSortWay(10,70));
mylistSortWay.push_back(CSortWay(10,100));

mylistSortWay.push_back(CSortWay(30,10));
mylistSortWay.push_back(CSortWay(30,40));
mylistSortWay.push_back(CSortWay(30,70));
mylistSortWay.push_back(CSortWay(30,100));

mylistSortWay.push_back(CSortWay(70,10));
mylistSortWay.push_back(CSortWay(70,40));
mylistSortWay.push_back(CSortWay(70,70));
mylistSortWay.push_back(CSortWay(70,100));

1. Position ist die
10,10
2. Position ist die
30,10
weil x = 30-10 = 20
weil y = 40-10 = 30 ja größer ist, also fahre ich ja erst
die x Werte an.

TODO
Abstand berechnen
Punkt 1 - Ausgangspunkt 10,10
Zu diesem Punkt jetzt alle Abstànde berechnen,
den kürzesten nehmen.
Habe ich den, sprich Punkt 2, zu diesem wieder alle
Abstànde berechnen, den kürzesten nehmen.

Problem:
Wie berechne ich jetzt die Distanz, etc.?
Wie gehe ich da math. ran?

Danke für Eure Hilfe.

Grüße Andreas
 

Lesen sie die antworten

#1 Karsten W.
04/06/2009 - 11:25 | Warnen spam
Vielleicht kann man das Problem als Netzwerk-Fluss-Problem
formulieren?
http://en.wikipedia.org/wiki/Minimu...ow_problem
http://mathworld.wolfram.com/NetworkFlow.html

Gruß,
K.

On 4 Jun., 09:29, Andreas Ott wrote:
Hallo!

Hardware - Aufbauhttp://www1.minpic.de/bild_an...6&ende

Die Maschine hat einen Einlauf und einen Auslauf.
Die Markiereinheit bewegt sich nicht, ist fix!! Es bewegen sich
lediglich die Achsen.

Es kommt eine unsortierte Liste, die ich nach dem kürzesten Weg
abfahren muss. Nummern sind hier nicht relevant. Taktzeit ist wichtiger,
schnell.

##### jetzt wird noch komplizierter ######
##### wo könnte ich da nachschauen, math. Stichwort
##### wer hat hier einen Algorithmus?
##### der auch zu verstehen ist ;-)
Das habe ich gefunden, komme aber nicht so recht weiter.
Pfadfindung - Wegberechnunghttp://www.vbarchiv.ne...ils.php?id75http://wiki.delphigl.com/index.php/...re_Algebra

Was will ich?

Input.
          mylistSortWay.push_back(CSortWay(50,10));
          mylistSortWay.push_back(CSortWay(50,40));
          mylistSortWay.push_back(CSortWay(50,70));
          mylistSortWay.push_back(CSortWay(50,100));

          mylistSortWay.push_back(CSortWay(90,10));
          mylistSortWay.push_back(CSortWay(90,40));
          mylistSortWay.push_back(CSortWay(90,70));
          mylistSortWay.push_back(CSortWay(90,100));

          mylistSortWay.push_back(CSortWay(10,10));
          mylistSortWay.push_back(CSortWay(10,40));
          mylistSortWay.push_back(CSortWay(10,70));
          mylistSortWay.push_back(CSortWay(10,100));

          mylistSortWay.push_back(CSortWay(30,10));
          mylistSortWay.push_back(CSortWay(30,40));
          mylistSortWay.push_back(CSortWay(30,70));
          mylistSortWay.push_back(CSortWay(30,100));

          mylistSortWay.push_back(CSortWay(70,10));
          mylistSortWay.push_back(CSortWay(70,40));
          mylistSortWay.push_back(CSortWay(70,70));
          mylistSortWay.push_back(CSortWay(70,100));

1. Position ist die
      10,10
2. Position ist die
      30,10
weil x = 30-10 = 20
weil y = 40-10 = 30 ja größer ist, also fahre ich ja erst
die x Werte an.

TODO
Abstand berechnen
     Punkt 1 - Ausgangspunkt 10,10
Zu diesem Punkt jetzt alle Abstànde berechnen,
den kürzesten nehmen.
Habe ich den, sprich Punkt 2, zu diesem wieder alle
Abstànde berechnen, den kürzesten nehmen.

Problem:
Wie berechne ich jetzt die Distanz, etc.?
Wie gehe ich da math. ran?

Danke für Eure Hilfe.

Grüße Andreas

Ähnliche fragen