Aus ProgrammingWiki

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

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

Übung 1

Entwerfen Sie einen Entscheidungsbaum für ein Rucksackproblem mit 4 Gegenständen (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

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

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

ausführen

Übung 4

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

(breitensuche '(10 20 30))

ausführen

(Alternativ kann natürlich auch DrRacket verwendet werden)