第十章

离散优化问题

我们可以另外定义两个宏,用来得到一个 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.