AuK/Systematische Suche Übungen SS11

Wiki-Quelltext dieser Seite.

<language>Scheme</language>
<code id="4dbfc25206b7f" hidden>;; TRACING + NICHTDETERMINISMUS
(import debugging) (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)))))</code>


= Übung 1 =

Entwerfen Sie einen Entscheidungsbaum für ein Rucksackproblem mit 4 Gegenständen (A, B, C, D) 

<popup name="Lösung">

[[Bild:U1.png]]

</popup>

= Übung 2 =

Den Gegenständen aus Übung 1 werden nun folgende Werte und Gewichte zugeordnet:

{| class="wikitable"
|- align="right"
! Gegenstand
| Gewicht || Wert 
|- align="right"
! A
| 15 || 50 
|- align="right"
! B
| 30 || 70 
|- align="right"
! C
| 40 || 50
|- align="right"
! D
| 50 || 60 
|}


Bestimmen Sie anhand eines reduzierten Breitensuchbaums den optimalen Rucksack für die Kapazitätgrenze <math> K = 100 </math>


<popup name="Lösung">

[[Bild:U2.png]]

</popup>

= Übung 3 =

Ändern Sie die Prozeduren rucksack4 und rucksack5, sodass rucksack5 eine Gegenstandsliste aus Gewichts-Wert-Paaren entgegennehmen kann und den optimalen Rucksack bestimmt.

Aufrufbeispiel: (rucksack5 '((10 . 3) (15 . 6) (20 . 9)) 37) liefert (((15 . 6) (20 . 9)) . 15)

<code>(define rucksack4
  (lambda (gls k)
    (let ((sls (multichoice gls (randomchoice (length gls)))))
      (if (<= (apply + sls) k)
          sls
          (choice '())))))

(define rucksack5
  (lambda (gls k)
    (let ((max 0) (resultat '()))
      (let ((alle-sls (bag-of  (rucksack4 gls k))))
        (map
         (lambda (sls)
           (let ((slssumme (apply + sls)))
             (if (> slssumme max)
                 (begin
                   (set! max slssumme)
                   (set! resultat sls)))))
         alle-sls))
      (cons resultat max))))</code>

<run>
(initialize-amb-fail)
</run>


<popup name="Lösung">

<code id="4dbfc1a0d23e8">
(define ls_gewicht 
  (lambda (ls) 
   (if (null? ls)
     0
     (+ (car (car ls)) (ls_gewicht (cdr ls))))
))

(define ls_wert
  (lambda (ls) 
   (if (null? ls)
     0
     (+ (cdr (car ls)) (ls_wert (cdr ls))))
))


(define ls_rucksack4
  (lambda (gls k)
    (let ((sls (multichoice gls (randomchoice (length gls)))))
      (if (<= (ls_gewicht sls) k)
          sls
          (choice '())))))

(define ls_rucksack5
  (lambda (gls k)
    (let ((max 0) (resultat '()))
      (let ((alle-sls (bag-of  (ls_rucksack4 gls k))))
        (map
         (lambda (sls)
           (let ((slssumme (ls_wert sls)))
             (if (> slssumme max)
                 (begin
                   (set! max slssumme)
                   (set! resultat sls)))))
         alle-sls))
      (cons resultat max))))
</code>

<run id="4dbfc1a0d2455">
(initialize-amb-fail)
(ls_rucksack5 '((10 . 3) (15 . 6) (20 . 9)) 37)</run>

</popup>

= Übung 4 =

Entwickeln Sie eine Scheme-Prozedur für das Durchlaufen eines reduzierten Breitensuchbaums.

<code id="4dbf27ed83895"></code>

<run id="4dbf27ed838f7">
(breitensuche '(10 20 30))

</run>

(Alternativ kann natürlich auch DrRacket verwendet werden)

<popup name="Lösung">

<code id="4dbf287ce4765">
(define loesung_breitensuche
  (lambda (g-ls)
    (let ((queue '()))
      (letrec ((helfer 
         (lambda (g-ls s-ls)
           (newline)(display "Breitensuche ")(display g-ls)(display s-ls)(newline)  
           (letrec ((breite
            (lambda (g-ls)
              (if (null? g-ls)
                  (begin
                       (if (not (null? queue))
                        (let ((knoten queue))    ;pop
                         (set! knoten (car queue))
                         (set! queue (cdr queue))
                        
                         (helfer (car knoten) (car (cdr knoten)))))    
                    )
                  (begin
                   
                   (set! queue (append queue (list (list (if (null? (cdr g-ls)) '() (cdr g-ls)) (cons (car g-ls) s-ls))))) ;push
                   
                   (display "Knoten: ")(display (list (if (null? (cdr g-ls)) '() (cdr g-ls)) (cons (car g-ls) s-ls)))(newline)
                   
                   (breite (cdr g-ls))
                  ))))) (breite g-ls))
           
           ))) (helfer g-ls '())))))
</code>

<run id="4dbf287ce47d8">(loesung_breitensuche '(10 20 30))</run>

</popup>