Racket 中的递归回溯？

Question

不久前，作为概念证明（并且因为我正在与自闭症儿子一起使用 Logo），我在 Logo 中编写了一个程序，使用回溯法在图中（如果存在）找到哈密顿回路。我使用的基本回溯模式是：

boolean hamilton(path p, graph g) 
  {
  if p has as many vertices as g 
    {
    if the last and first vertices in p are adjacent, 
      return true
    else 
      return false
    } 
  else 
    {
    for each vertex x of g not in p and adjacent to the last vertex of p
      {
      if hamilton(path p + x,graph g) succeeds, 
        return true
      }
    return false
    }
  }

你可以看到一个讨论 here。我可以在 Logo 中轻松做到这一点，因为它允许使用 OUTPUT 命令从一个函数中多个退出点。

然而，Racket 不允许多个出口点（至少，不容易）。所以我希望有人指出一些 material 的方向，这将解释 (a) 如何管理一个函数的多个退出点（我有一个模糊的概念，我可以用延续来做到这一点，就像 let/ec) 或 (b) 如何以更适合该语言的方式管理 Racket 中的递归回溯。

作为 Racket 的新手，我相信这可以由专家在眨眼之间完成，甚至可以由任何比我还不是新手的人完成。但是现在我为自己提供资金时感到非常难过。谢谢！

Answer 1

我认为这会起作用：

(define (hamilton p g)
  (if (>= (number-of-vertices p)
          (number-of-vertices g))
      (first-and-last-vertex-adjacent? p)
      (for/or ([v (in-vertices g)])
        (and (not (belongs-to-path v p))
             (not (adjacent v) (last-vertex p))
             (hamilton (append-vertex p x) g)))))

Racket 中的递归回溯？

Recursive backtracking in Racket?

graph

hamiltonian-cycle

racket

recursive-backtracking