1

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

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

(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 <= row < n 和 0 <= column < n 并且不是上一步。

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

我认为一般的算法是合理的。

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

以图形方式，在树中，我认为我需要返回到最近的节点，该节点有一个未访问的子节点的分支，并从那里重新开始，在走下前一个（错误的）分支时报废所有访问的节点。它是否正确？我将如何在我的代码中跟踪它？

感谢您阅读这么长的帖子；并感谢你们可以给我的任何帮助。

4

1 回答 1

1

哎呀！你的代码真的很可怕。尤其：

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)))
于 2014-02-07T06:32:09.367 回答