我正在使用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我的实现涉及到使用gensuccessors函数生成*合法继承者，将它们放到堆栈上，并递归地运行算法，将堆栈顶部的项作为新的当前位置。如果下一个位置是之前没有执行的步骤，我只增加步骤计数（负责跟踪骑士访问的方块顺序）当我无法生成更多的子项时，该算法将探索边界中的其他替代项，直到边界为空（失败条件）或棋盘上的步数=平方（获胜）。
我认为算法总体上是合理的。
编辑：我想问题是当我不能再生孩子的时候，我要去探索边疆的其他地方，我需要放弃目前的一些旅行我的问题是，我怎么知道我需要走多远？
从图形上看，在树中，我认为我需要返回到最近的节点，该节点有一个分支到一个未访问的子节点，并从那里重新启动，从而取消上一个（错误的）分支时访问的所有节点这是对的吗我该如何在代码中跟踪它？
谢谢你看了这么长的帖子，谢谢你们能给我的帮助。
最佳答案
哎呀你的代码真的很吓人。特别地：
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)))
关于algorithm - 骑士之旅深度优先搜索回溯，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/21620259/