Greedy-Algorithmen SS09

Aus ProgrammingWiki

< AuK

Archivierte Version vom 2009-05-17T11:25:44+00:00. Aktuelle Version

Inhaltsverzeichnis

1 Einführung
2 Bruchteilrucksack-Problem
3 Aufbau
4 Anwendbarkeit
5 Beispiel (Geldwechsel)
6 Verschiedene Greedy-Algorithmen
- 6.1 Dijkstra
- 6.2 Kruskal
7 Übung

Einführung

lalala

Bruchteilrucksack-Problem

Greedy

Aufbau

(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 ‘())))))

Anwendbarkeit

Greedy

Beispiel (Geldwechsel)

Greedy

(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 '())))))

Greedy-Algorithmen SS09

Inhaltsverzeichnis

Einführung

Bruchteilrucksack-Problem

Aufbau

Anwendbarkeit

Beispiel (Geldwechsel)

Verschiedene Greedy-Algorithmen

Dijkstra

Kruskal

Übung

Suche