回溯算法从空解开始，并逐渐扩大该解。搜寻递归地通过各种不同的构造解决方案的路径。
例如，斟酌计算n皇后问题：在n*n的棋盘上放置彼此不受袭击的n个皇后。文章源自微观生活（93wg.com）微观生活-https://93wg.com/22134.html
（皇后可以袭击在同一行、同一列、同一斜线上的棋子）文章源自微观生活（93wg.com）微观生活-https://93wg.com/22134.html
按以上规则：同一行或同一列或同一斜线上只能有一个皇后，同一行或同一列上必需有一个皇后。文章源自微观生活（93wg.com）微观生活-https://93wg.com/22134.html
n皇后问题的解空间是一棵n叉树，树的深度为n。文章源自微观生活（93wg.com）微观生活-https://93wg.com/22134.html
当n为4时，有两种可能的解决方案：文章源自微观生活（93wg.com）微观生活-https://93wg.com/22134.html
八皇后问题对于每一一行是不是可以放置皇后，可用一个范围为8的循环去判断。每一一行的判断操作相同，如果操作完成为了8行（放置了8个皇后），便求出了一个解。所以该问题可以用递归去做。如果某一行全体位置没法放置皇后时，不必要继续深刻，可以回溯到上一步，也就是使用回溯法。对于非尾递归，递归函数回退时，递归点后面的代码就是递归函数回退后执行的部份。对于八皇后问题，上述的循环可以判断某行下一列是不是可以放置皇后，而上一列放置皇后的操作进行逆操作后便完成为了回溯（递归有天然的回退阶段）。文章源自微观生活（93wg.com）微观生活-https://93wg.com/22134.html
八皇后问题的暴力枚举搜寻或递归解法会构成一个棵8叉完整树，回溯解法可以通过束缚前提防止一些搜寻继续深刻，构成一棵8叉不完整树。文章源自微观生活（93wg.com）微观生活-https://93wg.com/22134.html
为简便起见，咱们可以用四皇后问题去理解，然后泛化到一般的情况。文章源自微观生活（93wg.com）微观生活-https://93wg.com/22134.html
在底层，前三种配置是非法的，由于皇后们相互袭击。但是，第四种配置是有效的，可以通过在棋盘上再放置两个皇后来扩大到完全的解决方案。只有一种办法可以放置剩下的两个皇后。文章源自微观生活（93wg.com）微观生活-https://93wg.com/22134.html
如下面左图所示：文章源自微观生活（93wg.com）微观生活-https://93wg.com/22134.html
从y=0,x=0开始，search(0)递归调用search(1)（x=2,y=1），递归调用search(2)
当y=2，x=3时，递归函数search(2)执行终了，回退到search(1)，x=0，逆操作，循环到x=3……
code demo:
代码假定棋盘的行以及列编号从0到n-1。当使用参数y调用函数搜寻时，它会在行y上放置皇后，然后使用参数y-1调用本身。然后，如果y=n，则已找到解决方案，变量count增添1。
数组column跟踪包括皇后的列，数组diag1以及diag2跟踪对角线。不允许在已包括皇后的列或对角线中添加其他皇后。例如，4*4棋盘编号如下，当x、y取不同的值时，对应列方向column[x]、&
y＝2，x=3
回溯。
y＝1，x=3
……
count=1。
回溯到下面绿色点：
继续逐渐回溯：
……
count=2。
继续逐渐回溯，最后count=2。
可视化操作的网页地址：
https://pythontutor.com/render.html
-End-
以上就是微观生活（93wg.com）关于“算法｜八皇后问题理解回溯法”的详细内容，希望对大家有所帮助！
评论