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 unbeschränkten Tiefensuchbaum für die 4 Gegenstände (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ät <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 entgegen nehmen kann.

<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">(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>