2

不久前，作为概念证明（并且因为我和自闭症儿子一起使用 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
    }
  }

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

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

作为 Racket 的新手，我相信这可以由专家在眨眼间完成，甚至可以由比我更初级的任何人完成。但现在我为自己感到困惑。谢谢！

4

1 回答 1

3

我认为这会起作用：

(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)))))
于 2017-05-07T15:41:03.093 回答