1

我正在尝试在 Scheme 中实现回溯搜索。到目前为止，我有以下内容：

(define (backtrack n graph assignment)  
    (cond (assignment-complete n assignment) (assignment) )

    (define u (select-u graph assignment))

    (define c 1)
    (define result 0)

    (let forLoop ()
        (when (valid-choice graph assignment c)
             (hash-set! assignment u c)

             (set! result (backtrack n graph assignment))

             (cond ((not (eq? result #f)) result))

             (hash-remove! assignment u)            
        )

        (set! c (+ c 1))
        (when (>= n c) (forLoop))
    )

   #f ; I believe this is where I'm having problems
)

我的函数 assignment-complete 和 select-u 通过了单元测试。参数赋值是一个带有 (make-hash) 的哈希表，所以应该没问题。

我相信我遇到的问题与在循环结束时返回 false 有关，如果没有递归返回非 false 值（这应该是有效的赋值）。是否有等效于显式返回语句的方案？

4

1 回答 1

0

你的问题的答案是肯定的：

(define (foo ...)
  (call-with-current-continuation
    (lambda (return)
      ...... ; here anywhere inside any sub-expression 
      ...... ; you can call (return 42)
      ...... ; to return 42 from `foo` right away
    )))

这设置了一个退出 延续，以便您可以从函数体内返回结果值。通常的 Scheme 方法是将您的返回表单放在最后一个，因此返回它的值：

    (let forLoop ()
        (when (valid-choice graph assignment c)
             (hash-set! assignment u c)
             (set! result (backtrack n graph assignment))
             (cond
                 ((not (eq? result #f))
                   result))       ; the value of `cond` form is ignored
             (hash-remove! assignment u))
                                  ; the value of `when` form is ignored
        (set! c (+ c 1))
        (if (>= n c)     ; `if` must be the last form 
           (forLoop)     ; so that `forLoop` is tail-recursive
           ;; else:
           return-value) ; <<------ the last form's value 
    )                    ; is returned from `let` form

   ;; (let forLoop ...) must be the last form in your function
   ;;                   so its value is returned from the function
)

你这里也有问题：

(cond (assignment-complete n assignment) (assignment) )

此代码不拨打电话(assignment-complete n assignment)。相反，它检查变量assignment-complete是否具有非空值，如果没有，则检查assignment变量，但无论如何它的返回值都会被忽略。也许那里缺少更多的括号和/或一个else子句。

于 2013-11-08T09:32:02.620 回答