LCS(最长公共子序列)

Question

我试着用方案来实现LCS算法，但是有一个缺陷。

(定义X(列表#\A #\B #\C #\B #\D #\A #\B))

(定义Y(列表#\B #\D #\C #\A #\B #\A)

(定义前缀(lambda (i s) (if (= i 0) '() (con (car s) (前缀(- i 1) (cdr S)

(定义(pick ith s) (if (= ith 1) (car s) (pick (- ith 1) (cdr S)

(定义(LCS )(定义(最优i)) (cond (或(= i0) (= j0)) 0) ((eq？))(最大(LCS (前缀(- I1) x) y) (LCS x(前缀(- j1)y)(最优长度(长度)(长度y))

1 ]=> (负载"lcs.scm") 加载"lcs.scm"..。已完成；价值: lcs 1 ]=> (lcs ) ；价值:5

结果应该是4，我不知道哪里有bug。

Answer 1

因为最后的最优递归调用是不正确的，所以会得到错误信息。您使用前缀i-1表示x或j-1表示y，但另一个呢？j和i可能小于各自字符串的长度，因此需要对参数进行相应的前缀。

以下代码正常工作。

(define (LCS x y)
  (define (optimal i j)
    (cond
      ((or (= i 0) (= j 0)) 0)
      ((eq? (pick i x) (pick j y)) (+ 1 (optimal (- i 1) (- j 1))))
      (else (max (LCS (prefix (- i 1) x) (prefix j y)) (LCS (prefix i x) (prefix (- j 1) y))))))
  (optimal (length x) (length y)))

请注意，此问题之所以存在，是因为您混合了两种不同类型的调用。一个用前缀调用LCS，另一个用较小的i和j调用optimal，您可以用最优方法替换LCS调用，以获得更简单的解决方案。

(define (LCS x y)
  (define (optimal i j)
    (cond
      ((or (= i 0) (= j 0)) 0)
      ((eq? (pick i x) (pick j y)) (+ 1 (optimal (- i 1) (- j 1))))
      (else (max (optimal (- i 1) j) (optimal i (- j 1))))))
  (optimal (length x) (length y)))