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

本文介绍了骑士之旅深度优先搜索回溯的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

我正在使用DFS骑士的旅游咨询实施。

I'm working on a knight's tour implementation using DFS.

我的问题是，当我运行它，它工作正常到步骤20，但在此之后，该算法怪胎，并在一个5×5板输出这个（有一个5×5板开始溶液（0,0） ）：

My problem is, when I run it, it works fine up to step 20, but after that the algorithm freaks out and outputs this on a 5x5 board (there is a solution for a 5x5 board starting at (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; n和0℃=列＆LT; n和不会是previous一步。

*Legal successors must be 0 <= row < n and 0 <= column < n and not be a previous step.

我的实现涉及生成使用genSuccessors功能*合法继承人，把它们入栈和堆栈作为新的当前位置的顶部递归运行算法的项目。我只递增STEP_COUNT（负责跟踪正方形的顺序骑士访问）如果下一个位置是没有采取之前的工序。当我不能产生任何更多的孩子，算法探讨在边境其他的替代品，直到空前沿（故障状态）或STEP_COUNT =＃广场上的板（胜利）。

My implementation involves generating *legal successors using the genSuccessors function, throwing them onto a stack and recursively running the algorithm with the item at the top of the stack as the new current position. I only increment the step_count (in charge of tracking the order of squares the knight visits) if the next position is a step not taken before. When I cannot generate any more children, the algorithm explores other alternatives in the frontier until frontier empty (fail condition) or the step_count = # squares on the board (win).

我觉得算法一般是健全的。

I think the algorithm in general is sound.

编辑：我认为问题是，当我不能产生更多的孩子，我去探索，我需要放弃一些目前旅游前沿的其余部分。我的问题是，我怎么知道我怎么早需要去？

edit: I think the problem is that when I can't generate more children, and I go to explore the rest of the frontier I need to scrap some of the current tour. My question is, how do I know how far back I need to go?

从图形上看，在树上，我想我需要去备份到了一个分支的未访问过的孩子最近的节点，并重新开始从那里报废的所有节点下降时，previous（错）分公司参观。它是否正确？我将如何跟踪，在我的code？

Graphically, in a tree I think I would need to go back up to the closest node that had a branch to an unvisited child and restart from there scrapping all the nodes visited when going down the previous (wrong) branch. Is this correct? How would I keep track of that in my code?

感谢您阅读这么长的职务;并感谢所有帮助你们可以给我。

Thanks for reading such a long post; and thanks for any help you guys can give me.

推荐答案

哎呀！您的code是真正可怕的。特别是：

Yikes! Your code is really scary. In particular:

1），它采用突变无处不在。 2），它试图模拟回报。 3）不具备的任意的测试用例。

1) It uses mutation everywhere. 2) It tries to model "return". 3) It doesn't have any test cases.

我将是一个傲慢，大便，在这里，简单地说此言的特性相结合，使得超硬调试的程序。

I'm going to be a snooty-poo, here, and simply remark that this combination of features makes for SUPER-hard-to-debug programs.

另外...为DFS，真的没有必要跟踪自己的堆栈;你可以用递归吧？

Also... for DFS, there's really no need to keep track of your own stack; you can just use recursion, right?

抱歉不能提供更多的帮助。

Sorry not to be more helpful.

下面是我会怎么写：

#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)))