Systematische Suche Übungen SS11

Aus ProgrammingWiki

< AuK

Archivierte Version vom 2011-05-03T11:38:47+00:00. Aktuelle Version

Inhaltsverzeichnis

1 Übung 1
2 Übung 2
3 Übung 3
4 Übung 4

Übung 1

Entwerfen Sie einen unbeschränkten Tiefensuchbaum für die 4 Gegenstände (A, B, C, D)

Übung 2

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

Gegenstand	Gewicht	Wert
A	15	50
B	30	70
C	40	50
D	50	60

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

Übung 3

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

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

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

(initialize-amb-fail)

Übung 4

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

(breitensuche '(10 20 30))

(Alternativ kann natürlich auch DrRacket verwendet werden)