AuK/Greedy-Algorithmen SS09

Wiki-Quelltext dieser Seite.

==Einführung==
lalala

==Bruchteilrucksack-Problem==
Greedy

<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

==Beispiel (Geldwechsel)==
Greedy

==Verschiedene Greedy-Algorithmen==
Greedy

===Dijkstra===
.

===Kruskal===
.

==Übung==