AuK/Systematische Suche Übungen SS11

Wiki-Quelltext dieser Seite.

<language>Scheme</language>
= Ü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.

= Ü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>