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

<language>Scheme</language>
<language>Scheme</language>
==Beispiel (Geldwechsel)==
Greedy
<code>
(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)
     (madify+ (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)
                     neues-resultat))))))))
           (helfer kandidatenliste '())))))

</code>

<eval>
(geldwechsel 1293)
</eval>

==Verschiedene Greedy-Algorithmen==
Greedy

===Dijkstra===
.

===Kruskal===
.

==Übung==