Aus ProgrammingWiki
< AuK < Greedy-Algorithmen SS11 Aufgaben
Archivierte Version vom 2012-12-10T13:12:42+00:00. Aktuelle Version

1. Übung Bruchteil-Rucksackproblem

Berrechnen Sie den höchst möglichen Wert, den Sie in den Rucksack mit der Kapazität K = 30 einpacken können. Gegeben sind folgende Gegenstände:

S3sademu_Bruchteil-Rucksackproblem-Übung1.png

Überprüfen Sie Ihr Ergebnis mit Hilfe der Prozedur bruchteilrucksack.


Lösung

Zunächst werden die Gegenstände absteigend nach ihrem spezifischem Gewicht geordnet.

\frac{w_7}{g_7}\ge\frac{w_1}{g_1}\ge\frac{w_2}{g_2}\ge\frac{w_3}{g_3}\ge\frac{w_4}{g_4}\ge\frac{w_6}{g_6}\ge\frac{w_5}{g_5} K - \left(g_7 + g_1 + g_2 + g_3 + g_4 + g_6\right) = t \cdot g_5 t = \frac{30 -\left(2 + 7 + 6 + 5 + 4 + 3\right)} {4} t = \frac{3} {4}


W = w_7 + w_1 + w_2 + w_3 + w_4 + w_6 + t \cdot w_5 W = 8 + 21 + 18 + 15 + 12 + 9 + \frac{3} {4} \cdot 10 W = 90.5


2. Übung zum Dijkstra-Algorithmus

Gegeben ist folgende Matrix:

s3sademu_Entfernungsmatrix_-_Übung2.png


Zeichnen Sie den Graphen und wenden Sie den Dijkstra-Algorithmus auf diesen an. Gesucht ist der kürzeste Weg von A nach H.


Musterlösung

S3sademu_Lösung2.png


3. Übung zur Bildung eines minimalen Spannbaums

Wenden Sie einen Algorithmus Ihrer Wahl (Kruskal oder Prim) auf den Graphen aus Aufgabe 2 an und erstellen Sie den minimalen Spannbaum.


Musterlösung

S3sademu_Lösung3.png


4. Gegeben ist folgender Graph:

s3sademu_Übung4.png

Finden Sie mit Hilfe des Dijkstra-Algorithmus den kürzesten Weg von A nach P.


Lösung

Meine Musterlösung, gerechnet 10.12.2012 mit Excel:

Simohn_Dijkstra.jpg

Diese alte Musterlösung ist falsch!! bitte ENTFERNEN:

S3sademu_Lösung4_T.png
S3sademu_Lösung4_1.png
S3sademu_Lösung4_2.png


5. Bilden Sie den minimalen Spannbaum für den Graphen aus Aufgabe 4 mit einem Algorithmus Ihrer Wahl und begründen Sie, warum Sie sich für den benutzten Algorithmus entschieden haben.


Lösung

S3sademu_Lösung5.png


6. Programmieren Sie auf Grundlage des Greedy-Templates eine Scheme-Prozedur, die eine Zahl in ihre Primfaktoren zerlegen kann. Beachten Sie dabei, dass Sie die Hilfsprozedur delete benötigen.

  (define delete
   (lambda (item ls)
    (cond
      ((null? ls) '())
      ((eqv? (car ls) item) (cdr ls))
      (else
        (cons (car ls) (delete item (cdr ls)))))))

Aufrufbeispiel:

> (primfaktoren 30)

((5 3 2) 3)

Hinweis: Die letzte "3" ist die Anzahl der Primfaktoren.

Weitere Aufrufbeispiele:

  • 28
  • 76
  • 102
  • 1024
  • 2011


Lösung