AuK/Greedy-Algorithmen SS09

Wiki-Quelltext dieser Seite.

==Einführung==
lalala

==Bruchteilrucksack-Problem==
Greedy

<language>Scheme</language>
<language>Scheme</language>
<language>Scheme</language>
<language>Scheme</language>
==Aufbau==
<code>
(define greedy
 (lambda (vorgabewert) ; z.B.: Kapazitaet der Rucksacks
  (let
       ((kandidatenliste '(......))
        (loesung? (lambda (ls) ... ))
        (okay? (lambda (ls) ... ))
        (naechster (lambda (ls) ... ))
        (modify+ (lambda (x ls) ... ))
        (modify- (lambda (x ls) ... ))
        (ziel (lambda (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>

==Anwendbarkeit==
Greedy

<language>Scheme</language>
<language>Scheme</language>
<language>Scheme</language>
<language>Scheme</language>
<language>Scheme</language>
<language>Scheme</language>
==Beispiel (Geldwechsel)==
<code>
(define delete
(lambda (item ls)
  (cond
    ((null? ls) '())
    ((eqv? (car ls) item) (cdr ls))
    (else
      (cons (car ls) (delete item (cdr ls))))))) 


(define geldwechsel
(lambda (restbetrag)
  (let ((kandidatenliste '(200 100 50 20 10 5 2 1))
    (loesung? (lambda (ls)(= restbetrag (apply + ls))))
    (okay? (lambda (ls) (<= (apply + ls) restbetrag)))
    (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>

<eval>
(geldwechsel 1293)
</eval>

==Verschiedene Greedy-Algorithmen==
Greedy

===Dijkstra===
[http://de.wikipedia.org/wiki/Edsger_Wybe_Dijkstra Edsger Wybe Dijkstra auf Wikipedia]

===Kruskal===
.

==Übung==