在方案中实施深度优先搜索的问题

Question

我试图在方案中实现深度优先搜索，但我只能让它部分工作。 这是我的代码：

 (define (depth-first-search graph node neighbour path dest)
  (cond ((null? neighbour) #f)
        ((equal? node dest) path)
        ((member (car neighbour) path) (depth-first-search graph node (cdr neighbour) path dest))
        ((memq (car neighbour) (car graph)) (depth-first-search (cdr graph) (car neighbour) (memq (car neighbour) (car graph)) (append path (list (car neighbour))) dest))
        (else depth-first-search (cdr graph) path dest)))

这是我的图表，数据结构：

  (define complete-graph
  '((a b c d e)
    (b a c)
    (c a b f)
    (d a e h)
    (e a d)
    (f c g i)
    (g f h i j) 
    (h d g j)
    (i f g j)
    (j g h i)))

这就是我调用该过程的方式：

(depth-first-search complete-graph (caar complete-graph) (cdar complete-graph) (list (caar complete-graph)) 'd)

过程应该以列表形式返回从起始节点到目标（ination）的完整路径，但它似乎只能工作具有一些起始节点和目标节点。如果我从 'a 和 'c 开始，它会返回正确的列表 '(abc)，但如果我尝试使用 'a 和 'd，我会得到 #f 作为回报。所以很可能是算法中的回溯出了问题。但是我看了代码太久了，实在找不到问题所在。

Answer 1

假设节点 'a 有子节点 '(bcde)，节点 'b 有子节点 '(ac)，节点 ... 首先，您需要一个将节点扩展到其子节点的函数。

(define (expand graph node)
  (let ((c (assq node graph)))
    (if c (cdr c) '())))

第二：你必须记住所有访问过的节点。一般来说，帽子与路径不同（也许在这个例子中并不重要）。第三：你需要记住你想要访问的所有节点（节点扩展过程的结果）。因此定义一个辅助函数

(define (dfs* graph visited border path dest)

如果没有剩余节点可供访问，则不存在道路。

  (cond ((null? border) #f)

如果边界中的第一个元素等于我们的目的地，那么我们很高兴

        ((eq? (car border) dest) (cons (car border) path))

让我们检查所有访问过的节点。如果之前访问过边界中的第一个节点，则继续进行而不进行节点扩展

        ((memq (car border) visited)
         (dfs* graph visited (cdr border) path dest))

否则扩展边界的第一个节点

        (else (dfs* graph
                   (cons (car border) visited)
                   (append (expand graph (car border)) (cdr border))
                   (cons (car border) path)
                   dest))))

使用访问、边界和路径的起始值调用该辅助函数：

(define (dfs graph src dst)
  (dfs* graph '() (list src) '() dst)

对于呼吸优先搜索：将扩展的节点附加在边界末尾

编辑:
a) 访问过的路径和路径相同，可以删除其中一个
b) 以相反的顺序返回路径
c) 程序不正确，路径包含所有访问过的节点。但是 dfs* 结果的后处理就可以完成这项工作。

Answer 2

在进行深度优先搜索时，您不想更改图形，而只想更改当前节点。如果您想纯粹按功能执行操作，请让您的函数如下所示：（

(define (depth-first-search graph node dest path)
  (let dfs ((node node) (path path))
    (let ((recur (lambda (node) (dfs node (cons node path)))))
      ; Write code here
      ; Recursive calls should use recur, not dfs or depth-first-search
      ...)))

返回路径或 #f 作为结果）。您可以使用ormap（在 Racket 或 SRFI-1 中）迭代节点的所有邻居，返回第一个不是 #f 的值。