AuK/Greedy-Algorithmen SS11 Aufgaben/

Wiki-Quelltext dieser Seite.

<language>Scheme</language>
1. Übung Bruchteil-Rucksackproblem

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

[[Bild:S3sademu_Bruchteil-Rucksackproblem-Übung1.png]]
   
Überprüfen Sie Ihr Ergebnis mit Hilfe der Prozedur ''bruchteilrucksack''.


<popup name = "Lösung">
Zunächst werden die Gegenstände absteigend nach ihrem spezifischem Gewicht geordnet.

<math>\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}</math> 

<math>K - \left(g_7 + g_1 + g_2 + g_3 + g_4 + g_6\right) = t \cdot g_5</math>

<math>t = \frac{30 -\left(2 + 7 + 6 + 5 + 4 + 3\right)} {4}</math>

<math>t = \frac{3} {4}</math>


<math>W = w_7 + w_1 + w_2 + w_3 + w_4 + w_6 + t \cdot w_5</math>

<math>W = 8 + 21 + 18 + 15 + 12 + 9 + \frac{3} {4} \cdot 10</math>

<math>W = 90.5</math>
</popup>


2. Übung zum Dijkstra-Algorithmus

Gegeben ist folgende Matrix:

[[Bild: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.


<popup name = "Musterlösung">
Meine Musterlösung, gerechnet 10.12.2012 mit Excel:
[[Bild:Simohn_Dijkstra.jpg]]
Diese alte Musterlösung ist falsch!! bitte ENTFERNEN!
[[Bild:S3sademu_Lösung2.png]]
</popup>


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. 


<popup name = "Musterlösung">
[[Bild:S3sademu_Lösung3.png]]
</popup>


4. Gegeben ist folgender Graph:

[[Bild:s3sademu_Übung4.png]]

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


<popup name = "Lösung">
<center>
<gallery perrow="2"  widths="500" heights="300" caption="Wie man hier sieht, findet der Algorithmus zwei kürzeste Wege.">
Bild:S3sademu_Lösung4_T.png
Bild:S3sademu_Lösung4_1.png
Bild:S3sademu_Lösung4_2.png
</gallery>
</center>
</popup>


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.


<popup name = "Lösung">
[[Bild:S3sademu_Lösung5.png]]
</popup>


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


<popup name = "Lösung">
<code id="4de6236c0ca6e">
  (define delete
    (lambda (item ls)
     (cond
       ((null? ls) '())
       ((eqv? (car ls) item) (cdr ls))
       (else
         (cons (car ls) (delete item (cdr ls)))))))

  (define primfaktoren
    (lambda (wert)
      (let
        ((kandidatenliste '(19 17 13 11 7 5 3 2))
         (loesung? (lambda (ls) (= wert (apply * ls))))
         (okay? (lambda (ls) (and
                              (>= wert (apply * ls))
                              (= (round (/ wert (apply * ls)))(/ wert (apply * ls))))))
         (naechster car)
         (modify+ (lambda (x ls) ls ))
         (modify- (lambda (x ls) (delete x ls)))
         (ziel (lambda (ls)(cons (reverse ls) (list (length ls))))))
      (letrec
          ((helfer
            (lambda (kandidaten resultat)
              (cond
                ((loesung? resultat)(ziel resultat))
                ((and (null? kandidaten)(not(loesung? resultat)))
                 ((error 'greedy "Es gibt keine Loesung")))
                (else
                 (let* ((neuer-kandidat (naechster kandidaten))
                        (neues-resultat (cons neuer-kandidat resultat)))
                   (if (okay? neues-resultat)
                       (helfer (modify+ neuer-kandidat kandidaten) neues-resultat)
                       (helfer (modify- neuer-kandidat kandidaten) resultat))))))))
        (helfer kandidatenliste '())))))
</code>

<run id="4dc99d9a1c1c6">(primfaktoren 30)</run>
</popup>