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 hidden>
;;;  Nondeterminism

;;  amb (which stands for ambiguous)
;;  Inventor: McCarthy; MzScheme implementation: Dorai Sitaram
;;  Source: "Teach yourself Scheme in Fixnum Days"
;;  This is a Chez Scheme implementation.

(define amb-fail '*)

(define initialize-amb-fail
  (lambda ()
    (set! amb-fail
      (lambda ()
        (error "amb" "It fails")))))

(initialize-amb-fail)

(define-syntax amb
  (syntax-rules ()
    ((amb alt ...)
     (let ((+prev-amb-fail amb-fail))
       (call/cc
         (lambda (+sk)
           (call/cc
             (lambda (+fk)
               (set! amb-fail
                     (lambda ()
                       (set! amb-fail +prev-amb-fail)
                       (+fk 'fail)))
               (+sk alt)))
           ...
           (+prev-amb-fail)))))))

(define-syntax bag-of
  (syntax-rules ()
    ((bag-of e)
     (let ((+prev-amb-fail amb-fail)
           (+results '()))
       (if (call/cc
             (lambda (+k)
               (set! amb-fail (lambda () (+k #f)))
               (let ((+v e))
                 (set! +results (cons +v +results))
                 (+k #t))))
           (amb-fail))
       (set! amb-fail +prev-amb-fail)
       (reverse! +results)))))

(define choice
  (lambda (ls)
    (eval
      (cons
        'amb
        (map (lambda (x) (list 'quote x)) ls)))))

(define multichoice
  (lambda (ls n) 
    (if (= n 0)
        '()
        (let ((item (choice ls)))
          (cons item (multichoice (delete item ls) (- n 1)))))))

(define delete
  (lambda (item ls)
    (cond
      ((null? ls) '())
      ((eqv? (car ls) item) (cdr ls))
      (else
        (cons (car ls) (delete item (cdr ls)))))))

(define randomchoice
  (lambda (n)
    (letrec
      ((enumerate
         (lambda (i)
           (if (= i 0)
               '()
               (cons i (enumerate (- i 1)))))))
      (let ((numberlist (enumerate n)))
        (choice numberlist)))))



; ------  examples using nondeterminism  -----

(define number-between
  (lambda (lo hi) 
    (let loop ((i lo)) 
      (if (> i hi) 
          (amb) 
          (amb i (loop (+ i 1)))))))

(define assert 
  (lambda (pred) 
    (if (not pred) (amb))))

(define prime?
  (lambda (n)
    (letrec
      ((helper 
         (lambda (i)
           (cond
             ((> i (ceiling (sqrt n))) #t)
             ((zero? (modulo n i)) #f)
             (else
               (helper (+ i 2)))))))
      (cond
        ((= n 1) #f)
        ((= n 2) #t)
        ((= n 3) #t)
        ((even? n) #f)
        (else
          (helper 3))))))

(define gen-prime
  (lambda (hi)
    (let ((i (number-between 2 hi)))
      (assert (prime? i))
      i)))

; (bag-of (gen-prime 20))

(define all-divider-of 
  (lambda (n)
    (let ((i (number-between 2 (- n 1))))
      (assert (zero? (modulo n i)))
      i)))

; (bag-of (all-divider-of 18))
(initialize-amb-fail)
</code>

<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)
     (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===
.

===Kruskal===
.

==Übung==