Dynamisches Programmieren

Selbst verfolgen

Einleitung

Staplerfahren

Dyn. Programmieren

konkreter Fall

Selbst verfolgen

Arbeitsblatt

Aufgabe 1

(Zeit statt Strecke)

Statt die Länge des zurückgelegten Weges möchte man gewöhnlich lieber die benötigte Zeit minimieren.

a) Unter welchen (idealisierten) Voraussetzungen ist die Minimierung des Weges gleichbedeutend mit der Minimierung der Zeit?

b) Das Wenden eines Staplers innerhalb einer Gasse wird in der Regel einige Zeit kosten, ohne dass dabei Weg zurückgelegt wird. Geben Sie eine Möglichkeit an, wie man dies im Rahmen der vorgestellten Wegminimierungsaufgabe trotzdem berücksichtigen könnte.

Aufgabe 2

(Vergleich der Wege)

Im Applet der letzten Seite werden für jede zu befahrene Gasse stets ein roter (minimale Länge bei Ausfahrt am Nord-Ende) und ein blauer (minimale Länge bei Ausfahrt am Süd-Ende) Weg betrachtet.

Um wieviel unterscheiden sich die Längen der beiden Wege höchstens? Begründen Sie Ihre Antwort.

Aufgabe 3

(0/1-Rucksack)

Gegeben sind ein Rucksack mit einem Fassungsvermögen V und n Gegenstände G $_1$ ,..,G $_{\text{n}}$ . Gegenstand G $_{\text{i}}$ besitzt das Volumen V $_{\text{i}}$ und erbringt einen Ertrag E $_{\text{i}}$ .

Gesucht ist eine Füllung des Rucksacks mit Gegenständen, so dass der Gesamtertrag maximal ist ("optimale Füllung"). Das Gesamtvolumen der Gegenstände darf dabei natürlich V nicht überschreiten.

a) Bestimmen Sie eine solche optimale Füllung für das folgende Beispiel:

V = 100, n=10

G $_1$ : V $_1$ = 10, E $_1$ = 5
G $_2$ : V $_2$ = 20, E $_2$ = 8
G $_3$ : V $_3$ = 5, E $_3$ = 20
G $_4$ : V $_4$ = 30, E $_4$ = 30
G $_5$ : V $_5$ = 25, E $_5$ = 20
G $_6$ : V $_6$ = 15, E $_6$ = 10
G $_7$ : V $_7$ = 5, E $_7$ = 4
G $_8$ : V $_8$ = 10, E $_8$ = 12
G $_9$ : V $_9$ = 10, E $_9$ = 5
G $_{10}$ : V $_{10}$ = 25, E $_{10}$ = 25

b) Diese Aufgabe kann mit Dynamischem Programmieren gelöst werden. Bearbeiten Sie dazu folgende Fragen und Aufgaben:

Durch welche Optimalitätsbedingung ist die gesuchte Lösung charakterisiert?
Geben Sie verwandte Probleme kleinerer Größe an, die eine entsprechende Optimalitätsbedingung erfüllen. Mögliche Lösungen größerer Probleme sollen sich durch Erweiterung der Lösungen kleinerer Probleme gewinnen lassen. Was ist die Problemgröße?
Formulieren Sie ein Kriterium, wonach die Erweiterung der Lösung eines kleineren Problems nicht auf eine Lösung eines größeren Problems führen kann.
Formulieren Sie einen Algorithmus, der auf dem Prinzip des dynamischen Programmierens beruht.
Illustrieren Sie die Arbeitsweise des Algorithmus an dem Beispiel aus a).

Drucken

der krönende Abschluss

Sie können die einzelnen Schritte des Algorithmus hier verfolgen. Das untere Fenster produziert ein Protokoll.
Von den in jedem Schritt prinzipiell vorhandenen vier Fortsetzungsmöglichkeiten pro Weg werden von vornherein nur jeweils zwei eingezeichnet. (Warum wurde bereits erklärt.). So bleibt das Ganze übersichtlicher.
Rot eingezeichnet wird jeweils der kürzeste Weg mit Ausfahrt am Nord-Ende, blau der mit Ausfahrt am Süd-Ende.