Greedy-Algorithmen SS09

Aus ProgrammingWiki

< AuK

Archivierte Version vom 2009-05-17T11:13:46+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 ‘())))))

Greedy-Algorithmen SS09

Inhaltsverzeichnis

Einführung

Bruchteilrucksack-Problem

Aufbau

Anwendbarkeit

Beispiel (Geldwechsel)

Verschiedene Greedy-Algorithmen

Dijkstra

Kruskal

Übung

Suche