Dynamische Programmierung - Spezielles Problem

[rohamis7]

Hallo zusammen und guten Tag,

ich schreibe nun zum ersten Mal hier (gerade registriert, wusste gar nicht dass es dieses Forum gibt. Richtig schön!).

Was mich dazu gebracht hat, mich hier zu registrieren (aber ich denke ich werde dieses Forum so oder so auch für andere Themen benutzen ab jetzt) ist die Dynamische Programmierung.

Ich soll eine Aufgabe bewältigen, bei der ich ein paar Sachen nicht verstehen kann.

Ich habe einen Startpunkt, und einen Endpunkt, wo eine Fertigung eines Produktes statt findet.

Es gibt allerdings 2 Wege von Start nach Ende, A und B.

Auf jedem Weg gibt es i Stationen. Bei jeder Station benötigt die Fertigung eine bestimmte Zeit, bis das Produkt zur nächsten rüber geht. Es kann auch von Station SA(i) nach SB(i+1) gehen, dass heist zB. von SA(1) nach SB(2) (also kreuzweise) der Schritt erfolgen, allerdings braucht das auch Zeit (tA ist die Zeit von eine Station A(i) nach B(i+1) und tB ist die Zeit von eine Station B(i) nach A(i+1)).

Gesucht ist der Weg, von Start nach Ende, wo ein Produkt mit der kürzeste Zeit fertiggestellt wird.

Im Anhang ein Bild davon.

Mein Problem ist, ich kann nicht begreifen, wie genau es rekursiv laufen soll, da ich schon ein Rahmenprogramm habe, wo ich halt den Algorithmus implementieren soll.

Hier die Funktion:

void loesen( Zeiten sA, Zeiten sB, Zeiten tA, Zeiten tB, Lauf optA, Lauf optB, Zeit *sumA, Zeit *sumB, int i, int n )

Dabei sind:

- sA, sB : die Zeiten, die eine Station braucht

- tA, tB : die Zeiten, die das Produkt braucht um von A nach B zu kommen

- optA, optB : Felder mit 0 oder 1 bzw. 'A' oder 'B'.. Das wird dann am Ende für die Ausgabe des Weges benutzt

- sumA und sumB : dienen wohl als die bis dahin gespeicherte Zeit

- i : Laufindex von 0 bis n-1

- n : die Länge der Fertigung

Ich stecke schon seit 4 Tagen, kann aber keine richtige Lösung bzw. keine richtig Logik dazu finden.

Ich frage hier nicht nach eine fertige Lösung, nein, das soll ich ja selbst machen.

Aber ich brauche nur einen "Schupser" um halt richtig das ganze zu lösen. Und das, weil ich halt hier 2 Summen der bis dahin erstellten min. Zeiten habe, und 2 optimalen Wege. Das irritiert mich ein bisschen.

Danke

Bearbeitet 11. Mai 2011 von rohamis7

[Klotzkopp]

Der schnellste Weg von jedem Knoten aus ist die schnellere der beiden Möglichkeiten, von diesem Knoten wegzukommen. Und das ist jeweils der Weg zum nächsten Knoten plus dem schnellsten Weg von diesem Knoten.

[rohamis7]

Hallo und danke für deine Antwort.

Ich habe das verstanden was du meinst, soweit war ich auch.

Schnellster Weg bis einschliesslich SA entweder

- schnellster Weg durch SA[i-1], danach direkt zu SA, oder

- schnellster Weg durch SB[i-1], danach Strassenwechsel zu SA

und natürlich analog bei Vertauschung von A und B.

Nur ich weiss nicht so recht wie ich das in dem Code (in C) eintragen soll, und das auch noch als rekursion. Und vor allem, in genau dieser Funktion mit diesen Parametern

void loesen( Zeiten sA, Zeiten sB, Zeiten tA, Zeiten tB, Lauf optA, Lauf optB, Zeit *sumA, Zeit *sumB, int i, int n )

Muss ich die erste Station extra an sich alleine betrachten? Wenn ich eine Überprüfung mache wie diese hier:

if((optA[i-1]+sA[i]) <= (optB[i-1]+tB[i-1]+sA[i]))

{

  optA[i] = optA[i-1]+sA[i];

  // rekursion hier

}

else

{

  optA[i] = optB[i-1]+tB[i-1]+sA[i];

  // rekurion hier

}

weiss ich nicht so genau was ich mit sumA bzw. sumB machen soll, bzw. wie ich die Rekursion aufrufe.

[flashpixx]

Das ganze via Rekursion zu lösen, ist ein denkbar schlechter Weg. Dieses Problem kann man als Netzflussproblem (minimum-cost flow problem) auffassen, das man mit Hilfe eines leicht veränderten Simplexverfahren lösen kann. Bei größeren Netzen ist die Laufzeit der Rekursion nicht mehr gut.

[rohamis7]

Ja ich weiss dass die Rekursion in dem Fall nicht geeignet ist.

Aber so lautet ja meine Aufgabe. Da geht kein Weg dran vorbei.

Daher auch meine ganze Problematik an der Sache.

Ich muss das also so lösen, wie vorgegeben. Mit Rekursion und mit der oben stehenden Funktion und auch mit dessen Parameter.