Algorithmus zur Einengung von Intervallen

Wissenschaft Mathematik
1

Liebe/-r Experte/-in,

wie der Betreff schon sagte, suche ich einen Algorithmus, welcher Intervalle einengt.

Aber erst einmal zu den Intervallen: Es handelt sich um Zeitintervalle an fixen Routenpunkten, die dadurch aufgespannt werden, dass z. B. ein Fahrzeug schnell oder langsam fährt. Die frühesten Zeiten ergeben sich also durch das Fahren mit einer Mindestgeschwindigkeit, die spätesten Zeiten durch schnellstmögliches Fahren.
Nun wird am letzten Routenpunkt eine Zielzeit vorgegeben. Die Fragen sind jetzt:

  1. Wie beeinflusst das die vorherigen Intervalle?
  2. Wie kann man das algorithmisch ausdrücken?

Nun habe ich etwas davon gehört, die Intervallabstände überkreuz zu betrachten; komme aber auf keinen grünen Zweig damit.

Vielleicht noch einmal ein Beispiel zu verdeutlich des Sachverhalts:

Gegeben sind vier Intervalle (in [s]) an
aufeinanderfolgenden Routenpunkt (und ein
Startintervall mit Distanz 0):

S [0…0]
A [10…20]
B [15…30]
C [40…70]
D [65…100]

Nun soll an Punkt D die Zielzeit 75 getroffen werden.

Zuerst werden die Intervallgrenzen an Punkt D auf 65
gesetzt:
S [0…0]
A [10…20]
B [15…30]
C [40…70]
D [65…65]

Dann werden überkreuz die (alten) Abstände C-D von C
subtrahiert (glaube ich):

S [0…0]
A [10…20]
B [15…30]
C [35…40]
D [65…65]

Und hier passt es schon nicht mehr: die neue frühe
Zeit an C liegt vor der frühesten Zeit…

Vielleicht kannst Du mir weiterhelfen?! Vielen Dank schon einmal im Voraus und viele Grüße,

Christian

2

Hallo,

fährt das Auto immer gleich schnell ?!? Ansonsten kann man bei B auch 40 schaffen ?
(20-0)+(30-10) wenn ich es mal so interpretiere, dass wenn man bei 10 bei A war man es trotzdem bis 30 zu B schaffen kann - wenn man dann schneller fährt ?!? Ansonsten müsste man die Geschwindigkeitsgrenzen auch noch kennen .

ML

3

Hallo,

das Auto fährt nicht gleich schnell. Es hat zwei Grenz-Geschwindigkeiten (die die Intervalle aufspannen): eine minimale und eine maximale. Zwischen diesen kann sich die Geschwindigkeit bewegen.

Die späteste Zeit bei B, die ich von 10 bei A erreichen kann, ist 20 ( 20 = B30] - A20] + A[10)
Die früheste Zeit wiederum, an der ich von A20] aus C erreiche, ist 25.

Hoffentlich waren meine Ausführungen verständlich :wink:

Danke und beste Grüße,

Christian

4

Tut mir leid, ich kann dir leider mit diesem Algorithmus nicht helfen. Aber bestimmt findest du jemand anderes, der dir helfen kann :smile:

5

OK also die Differenz der frühesten entspricht immer der schnellsten und die Differenz der spätesten immer der langsamste Geschwindigkeit (?).

Du Schreibst Zielzeit 75. Dann muss das Intervall bei D auch 75,75 werden und nicht 65,65

Dann muss ich um 75 da zu sein spätestens um 75-(65-40)=60 losfahren
und darf frühestens um 75-(100-70) =45 losfahren

Also neues Intervall für C wäre 45,60

D.h. da ich von B aus zwischen 25 und 40 Min brauche muss ich bei B
im Intervall 5,35 losfahren geschnitten mit dem gegebenen also in 15,30 und ab dann ist es egal, die Intervalle bleiben.

ML

6

Danke! Das klingt gut, wobei 75-(65-40) = 50. Aber dann ist es nachvollziehbar und lässt sich in einen Algorithmus fassen!

Ach ja, Du hast recht: es musste an D 75,75 natürlich heißen.

Daraus lässt sich jetzt prima ein Algorithmus basteln. Diesen sende ich beizeiten…

Vielen Dank noch einmal und einen schönen Abend!

Christian

7

Hi,

mein Verständis ist folgendes:

Die Intervallgrenzen geben dir die Fahrtzeit-intervalle, z.B.

C->D [25,30]

wenn du um 65 (nicht 75) in D sein sollst musst du also frühestens 35 (+30=65) und spätestens 40 (+25=65) aufbrechen. Die überkreuz-Regel stimmt.

Da du weißt dass du frühstens 40 in C sein kannst ist das C-Intervall also [40,40].

Dann weiter zu B: direkt [0,15], korrigiert [15,15].
A: direkt [5,10], korrigiert [10,10]
S: direkt [-10,0], aber da muss man ja sowie so um 0 losfahren :wink:.
Dieses Beispiel ist extrem weil 65 die früheste Zeit in D ist (damit gibt es keine Flexibilität)

für D=[75,75] ergibt sich [45,50] -> [5,25]/[15,25] -> [5,20]/[10,20] -> [-10,10]/[0,10]. Damit hast du engere Intervalle (aber nicht so eng wie bei D 65).

Klappt doch alles :smile:

Ben

8

Hallo, vielen Dank für Deine umfassende Antwort! Du hast recht, am Punkt D soll das Intervall auf die Zielzeit 75 gesetzt werden. Somit heißt das Intervall dort [75,75]. Ja, das Prinzip habe ich verstanden - daraus einen Algorithmus zu basteln ist jetzt nicht mehr schwer.

Danke nochmals und viele Grüße,

Christian

9

Hallo Christian,

ich kenne mich damit nicht wirklich aus, aber vielleicht ist folgende Überlegung ja nicht allzu verkehrt:

1.) Die „kleinen“ Zeiten geben immer die minimale Zeitspanne vor, die man braucht um einen Punkt zu erreichen. Das heisst, um von A nach B zu kommen braucht man mindestens 5 Minuten (da 15-10=5). Schneller geht es nicht, sonst müsste der kleine Wert von B niedriger sein.

2.) Die „großen“ Zeiten geben immer die maximale Zeitspanne vor, die man braucht um einen Punkt zu erreichen. Von A nach B bedeutet das, dass man maximal 10 Minuten benötigt (30-20).

Aus diesen beiden Überlegungen heraus, kannst du nun von deiner „Ziel-Zeit“ aus zurückrechnen. Du weisst ja, wie schnell und wie langsam du maximal vom vorletzten Punk aus dort hinkommst.
Um also spätestens zum Zeitpunkt 65 am letzten Punkt zu sein, wenn man vom vorletzten Punkt aus mindestens 25 Minuten (=65-40) braucht, musst du allerspätestens zum Zeitpunkt 40 (=Ziel-Zeit - Mindest-Dauer) dort los.

In diesem Fall ist es kein Zufall, dass das Intervall bei C auf [40…40] reduziert wird. Logisch betrachtet, wenn man zum frühest möglichen Zeitpunkt bei D sein will, muss man auch schon zum frühest möglichen Zeitpunkt bei C gewesen sein - genauso auch bei B und bei A.

Interessanter wird es, wenn du zum Zeitpunkt 80 bei D sein möchtest, dann sähe es für C folgendermaßen aus:
Altes Intervall: [40…70] (erweitern darf man ein Intervall ja sinnvoller Weise nicht, nur weiter einschränken)
Neues Intervall: [50…55]
Erklärung: Man braucht von C nach D mindestens 25 Minuten (=65-40) und maximal 30 Minuten (=100-70). Wenn wir von 80 bei D das Maximum abziehen, wissen wir wann wir frühestens bei C sein dürfen um nicht zu früh zu kommen. (50=80-30). Wenn wir von 80 bei D das Minimum abziehen, wissen wir wann wir spätestens bei C sein müssen um nicht zu spät zu kommen.
Von C aus können wir auf B schliessen:
Altes Intervall: [15…30]
Neues Intervall: [15…30]
Erklärung: Min/Max von B nach C = 25/40
Spätester Zeitpunkt bei B mit Maximalgeschwindigkeit noch rechtzeitig bei „neuem“ C anzukommen: 55-25 = 30.
Frühester Zeitpunkt bei B, um mit Mindestgeschwindigkeit nicht zu früh zu „neuem“ C zu kommen: 50-40 = 10.
Es ändert sich nichts, weil wir das alte Intervall ja nicht erweitern dürfen - sonst würden wir ja die alten Mindest- und Höchst-Geschwindigkeiten ausser Kraft setzen.

Grundprinzip ist also: Von hinten nach vorne die min- und max-Zeiten rechnen, um so das Vorgänger-Intervall einzuschränken. Wenn es eingeschränkt wurde, nochmal ein weiteres Intervall zurückrechnen … and so on …
… klingt das logisch?

Grüße, Daniel

10

Hallo Daniel,

erst einmal vielen Dank für Deine hilfreiche Antwort! Da hast Du Dir sehr viel Mühe gemacht!

Es klingt alles logisch und nachvollziehbar - der Algorithmus dahinter ist anhand Deiner Beispiele gut erkennbar!

Nochmals danke und viele Grüße,

Christian