0

要启动回溯算法，i=0 时可以调用以下伪代码；X[1..0] 表示空元组。

ALGORITHM Backtrack(X[1..i])
   //Gives a template of a generic backtracking algorithm
   //Input: X[1..i] specifies first i promising components of a solution.
   //Output: Alll the tuples representing the problem's solutions
   If X[1..i] is a solution write X[1..i]
   else
     for each element x belongs to Si+1 consistent with X[1..i] and constraints do
        X[i+1] <- x
        Backtrack(X[1..i+1])

我很难理解上述逻辑。我试图通过逐步解决 4 皇后问题，但没有。请通过 4 个皇后问题的步骤帮助您理解上述逻辑。

谢谢！

4

1 回答 1

1

看看这个 PDF 文件，第 25 页。它有一步一步的描述，其中包含关于 4 个带回溯的皇后解决方案的图像。

http://ce.sharif.edu/courses/90-91/2/ce417-1/resources/root/Lectures/Chapter-6.pdf

简单来说：

该算法试图为数组 X 的每个元素找到一个与所有约束一致的赋值。

为了通过回溯做到这一点，我们使用递归函数。在每个步骤中，我们检查当前变量（域集 S i+1）的所有可用值，如果它与约束一致，我们递归地转到下一个变量，直到找到解决方案。

于 2012-05-04T12:56:23.657 回答