recursion - 骑士之旅深度优先搜索回溯

Question

我正在使用 DFS 实现骑士之旅。

我的问题是，当我运行它时，它在第 20 步之前工作正常，但在那之后算法会崩溃并在 5x5 板上输出它(有一个 5x5 板的解决方案从 (0,0) 开始):

(1  10 5  16 24)
(4  15 2  11 20)
(9  6  17 23 22)
(14 3  8  19 12)
(7  18 13 21 25)

*合法的继任者必须是 0 <= 行 < n 和 0 <= 列 < n 并且不能是前一步。

我的实现涉及使用 genSuccessors 函数生成*合法的后继者，将它们放入堆栈并以堆栈顶部的项目作为新的当前位置递归运行算法。如果下一个位置是之前未采取的步骤，我只会增加 step_count(负责跟踪骑士访问的方格的顺序)。当我无法再生成更多 child 时，该算法会探索边界中的其他替代方案，直到边界为空(失败条件)或 step_count = # 棋盘上的方 block (获胜)。

我认为该算法总体上是合理的。

编辑:我认为问题是当我不能产生更多的 child 时，我去探索其余的边界我需要取消一些当前的旅行。我的问题是，我怎么知道我需要回溯多远？

从图形上看，在一棵树中，我认为我需要返回到最近的节点，该节点有一个未访问过的子节点的分支，并从那里重新开始，在沿着前一个(错误的)分支向下移动时废弃所有访问过的节点。它是否正确？我如何在我的代码中跟踪它？

感谢您阅读这么长的文章；并感谢你们能给我的任何帮助。

Answer 1

哎呀!你的代码真的很可怕。特别是:

1) 它到处都使用突变。 2)它试图模拟“回归”。 3) 它没有任何测试用例。

在这里，我要成为一个傲慢的便便，并且简单地说，这种功能组合使得程序 super 难以调试。

此外...对于 DFS，确实没有必要跟踪您自己的堆栈；你可以只使用递归，对吧？

抱歉没有提供更多帮助。

我是这样写的:

#lang racket

;; a position is (make-posn x y)
(struct posn (x y) #:transparent)

(define XDIM 5)
(define YDIM 5)

(define empty-board
  (for*/set ([x XDIM]
             [y YDIM])
    (posn x y)))

(define (add-posn a b)
  (posn (+ (posn-x a) (posn-x b))
        (+ (posn-y a) (posn-y b))))

;; the legal moves, represented as posns:
(define moves
  (list->set
   (list (posn 1 2) (posn 2 1)
         (posn -1 2) (posn 2 -1)
         (posn -1 -2) (posn -2 -1)
         (posn 1 -2) (posn -2 1))))

;; reachable knights moves from a given posn
(define (possible-moves from-posn)
  (for/set ([m moves])
    (add-posn from-posn m)))

;; search loop. invariant: elements of path-taken are not
;; in the remaining set. The path taken is given in reverse order.
(define (search-loop remaining path-taken)
  (cond [(set-empty? remaining) path-taken]
        [else (define possibilities (set-intersect (possible-moves
                                                    (first path-taken))
                                                   remaining))
              (for/or ([p possibilities])
                (search-loop (set-remove remaining p)
                             (cons p path-taken)))]))

(search-loop (set-remove empty-board (posn 0 0)) (list (posn 0 0)))

;; start at every possible posn:
#;(for/or ([p empty-board])
  (search-loop (set-remove empty-board p) (list p)))