我们可以另外定义两个宏,用来得到一个 amb 系统的最大值或者最 小值:
(define-syntax min-of (syntax-rules () ((_ e cost) (let ((prev-amb-fail amb-fail) (results '())) (if (call/cc (lambda (k) (set! amb-fail (lambda () (k #f))) (let ((v e)) (cond ((null? results) (set! results (list v))) ((< (cost v) (cost (car results))) (set! results (list v))) ((= (cost v) (cost (car results))) (if (not (member v results)) (set! results (cons v results))))) (k #t)))) (amb-fail)) (set! amb-fail prev-amb-fail) (reverse! results))))) (define-syntax max-of (syntax-rules () ((_ e cost) (let ((prev-amb-fail amb-fail) (results '())) (if (call/cc (lambda (k) (set! amb-fail (lambda () (k #f))) (let ((v e)) (cond ((null? results) (set! results (list v))) ((> (cost v) (cost (car results))) (set! results (list v))) ((= (cost v) (cost (car results))) (if (not (member v results)) (set! results (cons v results))))) (k #t)))) (amb-fail)) (set! amb-fail prev-amb-fail) (reverse! results)))))
min-of 和 max-of 都接受两个参数,一个是用来生成结果的表达式, 和一个用来衡量结果费用的函数。它的返回值是一个list,里面是达 到最小(最大)值的所有解。
比如,我们可以这样用:
(define (f1) (* (amb 34 23 12 3 8 34 45 94 32 18) (amb 3 8 42 45 64 47 68 19 10 2))) (min-of (f1) (lambda (x) x))
这样我们就可以求得 f1 里的两个 amb 可能的最小乘积。
这两个函数可以作为通用的离散优化函数。比如我们可以用 max-of 来解决装箱问题(bin-pack).
(define (bin-pack objs volume) (let pack ((in-bag '()) (out-of objs)) (call/cc (lambda (return) (let ((next (apply-amb out-of))) (if (<= (apply + (cons next in-bag)) volume) (begin (pack (cons next in-bag) (del next out-of))) (return in-bag)))))))
我们的帮助函数 del 是用来从一个 list 里去掉一个元素的。
bin-pack 接受两个参数,第一个是一些物体的重量,第二个是我们 的箱子(行包)的容积。
每次运行就会得到一个不超过容积的解,比如:
(bin-pack (list 48 102 180 23 3 45 201 19 29 34 55 82 24) 300)
就会得到 (102 48).
我们可以用 max-of 得到最大可能的装箱:
(max-of (bin-pack (list 48 102 180 23 3 45 201 19 29 34 55 82 24) 300) (lambda (l) (apply + l)))
结果是 ((55 19 45 3 23 102 48)). 总重 295.