close

Anmelden

Neues Passwort anfordern?

Anmeldung mit OpenID

Aufgabenblatt 6 - Angewandte Geometrie und Diskrete Mathematik

EinbettenHerunterladen
Technische Universität München, Zentrum Mathematik
Lehrstuhl für Angewandte Geometrie und Diskrete Mathematik
Algorithmische Diskrete Mathematik (MA 2501)
Prof. Dr. P. Gritzmann | Dr. M. Ritter | Dipl.-Math. F. Schmiedl
Aufgabenblatt 6
Tutoraufgabe 6.1 (Intervallpflasterung)
[4 Punkte]
Eine Instanz von Intervallpflasterung sei gegeben durch n = 3, a = (3, 4, 6), β = 12.
a) Stellen Sie diese Instanz als eine Aufgabe der dynamischen Optimierung dar. Geben Sie dazu
den Schichtgraphen an und beschreiben Sie, welche Zustände die Knoten jeweils darstellen. Wie
sieht die Stufenkostenfunktion und die Rekursionsvorschrift dieser Aufgabe aus?
b) Ändern Sie die Aufgabe so ab, dass eine Lösung x ∈ N30 bestimmt wird, bei der möglichst wenige
verschiedene Gegenstände verwendet werden (d. h., minimalem |{i ∈ [n] : xi = 0}|). Bestimmen
Sie eine optimale Lösung.
Aufgabe 6.2 (Ein Knapsack-Problem)
[6 Punkte]
Gegeben sei ein Knapsack-Problem mit 4 Gegenständen durch den Gewichtsvektor w = (2, 4, 3, 4)T ,
die Werte c = (1, 3, 2, 5)T und die Gewichtsschranke ρ = 6. Wir lösen das Problem mittels dynamischer
Optimierung. Dabei steht jede Schicht des Schichtgraphen für einen Gegenstand, jeder Knoten für
einen Zustand mit vorgegebener Restkapazität. Der Knoten vk,j gehört also zur k-ten Schicht (in
der darüber entschieden wird, ob Gegenstand k eingepackt wird oder nicht) und repräsentiert eine
Teil-Lösung mit Restkapazität j.
Definieren Sie auf dieser Basis einen geeigneten Schichtgraphen, Knotenwerte α(vk,j ) und eine passende
Stufenkostenfunktion. Wenden Sie damit den Algorithmus aus der Vorlesung an, um das KnapsackProblem zu Lösen. Geben Sie den optimalen Zielfunktionswert sowie eine mögliche Optimallösung
an.
Aufgabe 6.3 (Knapsack mit Werten als Zustandsbeschreibung)
[6 Punkte]
In der Vorlesung haben Sie einen dynamischen Ansatz zur Lösung des Knapsack-Problems kennengelernt, bei dem die Zustände jeweils die noch freie Restkapazität repräsentieren. Wie müssen Sie
diesen Algorithmus abändern, wenn jeder Zustand den aktuell erreichten Gesamtwert des Knapsack
repräsentieren soll? Geben Sie den vollständigen Algorithmus an (mit Schichtgraph und Stufenkostenfunktion) und wenden Sie ihn auf das Knapsack-Problem mit Gewichtsvektor w = (2, 4, 3, 4)T ,
Gewichtsschranke ρ = 6 und Werten v = (1, 3, 2, 5)T an.
Aufgabe 6.4 (Bellman-Ford)
[10 Punkte]
Sei n ∈ N, V = {v1 , . . . , vn } und G = (V, E, φ) ein Digraph mit Kantengewichtung φ : E → R ohne
negative Kreise. Wir betrachten in dieser Aufgabe einen Algorithmus, der mit Hilfe der dynamischen
Optimierung einen kürzesten v1 -vn -Weg in G bestimmt (oder feststellt, dass kein solcher existiert).
a) Wir definieren folgenden Schichtgraphen: In der k-ten Schicht befinden sich alle Knoten aus V ,
die über einen Weg aus höchstens k Kanten von v1 aus erreichbar sind. Den „Vertreter“ von
Knoten vi in Schicht k bezeichnen wir mit vk,i . Wie sieht die Kantenmenge des Schichtgraphen
aus? Wieviele Schichten besitzt Ihr Schichtgraph?
Bitte wenden!
b) Für jeden Knoten vk,i des Schichtgraphen sei α(vk,i ) die Länge eines kürzesten v1 -vi -Weges mit
höchstens k Kanten (oder „∞“, falls kein solcher Weg existiert). Geben Sie eine Rekursionsformel
für die α(vk,i ) an (d. h., bestimmen Sie die Stufenkostenfunktion). Mit welchen Werten starten
Sie die Rekursion? Beweisen Sie, dass die Rekursion die korrekten Werte liefert (also tatsächlich
die Länge eines kürzesten v1 -vi -Weges).
c) Welche Laufzeit besitzt Ihr Algorithmus (Größenordnung)?
d) Erweitern Sie den Algorithmus so, dass die Länge eines kürzesten v1 -vi -Weges für alle i simultan
bestimmt wird.
e) Erweitern Sie den Algorithmus so, dass die Existenz eines negativen Kreises in G entdeckt
werden kann und zum Abbruch mit einer entsprechenden Fehlermeldung führt (Beweis der
Korrektheit nicht vergessen).
Bonusaufgabe 6.5 (Dynamisches Travelling Salesman Problem)
[8 Punkte]
Sei n ∈ N und Kn = ([n], E) der vollständige Graph auf n Knoten. Zeigen Sie mit Hilfe dynamischer
Programmierung, dass zu jeder Kostenfunktion c : E → R≥0 eine optimale TSP-Tour auf Kn in
O n2 2n Schritten gefunden werden kann. Um welchen Faktor ist diese Laufzeit besser als die „brute
force“-Lösung mit Laufzeit n!, wenn Sie n = 5 bzw. n = 10 Knoten betrachten?
Diese Bonusaufgabe zählt nicht für die Punkte-Obergrenze der „sinnvoll bearbeitet“-Punkte, Sie können
damit also einen Extrapunkt erwerben.
Abbildung 1: Quelle: http://xkcd.com/399/, Lizenz: Creative Commons BY-NC 2.5
Die Abgabedaten von Blatt 6 für Ihre Gruppe finden Sie auf der Homepage zur Vorlesung
unter http://www-m9.ma.tum.de/WS2014/ADM.
Document
Kategorie
Gesundheitswesen
Seitenansichten
2
Dateigröße
321 KB
Tags
1/--Seiten
melden