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

Question

我正在使用DFS进行骑士的旅行实施。

我的问题是，当我运行它时，直到第20步，它可以正常工作，但是此后，该算法会吓坏并将其输出在5x5板上（有一个用于5x5板的解决方案，用于（0,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＆lt; = row＆lt;n和0＆lt; =列＆lt;n，不是前一步。

我的实现涉及使用Gensuccessors功能生成 *法律继任者，将其扔到堆栈上，并递归地运行该算法，其中该项目是堆栈顶部作为新的当前位置。如果下一个位置不是前一个步骤，我只会增加step_count（负责跟踪骑士访问的平方顺序）。当我无法再生成任何孩子时，该算法会探索边境中的其他替代方案，直到边境为空（失败条件）或step_count =＃squares in the Board（Win）。

我认为算法通常是正确的。

编辑：我认为问题是，当我无法生成更多的孩子时，我去探索其余的边境时，我需要废除一些当前的旅行。我的问题是，我怎么知道我需要走多远？

从图形上讲，在树上，我认为我需要返回到有一个未访问的孩子的分支的最接近的节点，然后从那里重新启动，在下一个（错误的）分支上播放的所有节点。它是否正确？我如何在我的代码中跟踪它？

感谢您阅读如此长的文章；并感谢你们可以给我的任何帮助。

Answer 1

yikes！您的代码真的很可怕。特别是：

1）它在各处使用突变。2）它试图建模"返回"。3）它没有任何测试用例。

我将在这里成为一个嘲笑的人，只是说这种功能的组合使超级挑战程序构成了。

也...对于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)))