1.什么是试探算法？
2.试探算法的解题的基本步骤
3.试探算法的思想
4.试探算法适合的问题
5.试探算法解决“八皇后”的问题
1.什么是试探算法？
试探算法也叫回溯法，试探算法的处事方式比较委婉，它暂时放弃关于问题规模大小的限制，并将问题的候选解按某种顺序逐一枚举和检验。当发现当前候选解不可能是正确的解时，就选择下一个候选解。如果当前候选解不满足问题规模要求外， 能够满足所有其他要求，则继续扩大当前候选解的规模，并继续试探。如果当前候选解满足包括问题规模在内的所有要求，该候选解就是问题的一个解。在试探算法中，放弃当前候选解，并继续寻找下一个候选解的过程称为回溯。扩大当前候选解的规模，并继续试探的过程称为向前试探。
2.试探算法的解题的基本步骤
- 针对所给问题，定义问题的解空间。
- 确定易于搜索的解空间结构。
- 以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。
3.试探算法的思想
为了求得问题的正确解，试探算法会先委婉地试探某种可能的情况。在进行试探的过程中，一旦发现原来选择的假设情况是不正确的，立即会自觉的退回一步重新选择，然后继续向前试探，如此这般反复进行，直至得到解或证明无解时才死心.
4.试探算法适合的问题
比如有一个元组n组成的一个状态空间，关于元组n,有多个条件组成的约束集合，满足这个条件约束集合的任一n元组为问题的一个解。只要检测出元组中有一个违反了约束，就可以肯定这个元组就不是问题的解，因而不必去搜素和检测它们，试探算法就是针对这类问题而推出的，比枚举算法的效率更高。
5.试探算法解决“八皇后”的问题
“八皇后”问题是一个古老而著名的问题，是试探法的典型例题。该问题由19世纪的数学家高斯于1850年手工解决：在8×8的国际象棋上摆放8个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。
可以将整个问题简化为4×4的棋盘，就有两种摆法，每行摆在列2、4、1、3或列3、1、4、2上
试探算法将每行的可行位置入栈（就是放入数组a[5]，用的是a[1]~a[4]），不行就退栈还列重新试，直到找到一套方案并输出，接着从第一行换列重试其他方案。
为了简化问题，考虑到8个皇后不同行，则每一行放置一个皇后，每一行的皇后可以放置于第0~7列，我们认为每一行的皇后有8种状态。那么，只要套用子集树模板，从第0行开始，自上而下，对每一行的皇后，遍历它的8个状态即可。
n = 8
x = [] # 一个解（n元数组）
X = [] # 一组解
# 冲突检测：判断x[k] 是否与前面的x[0] ~ x[k-1]
def conflict(k):
global x
for i in range(k): # 遍历前面的x[0] ~ x[k-1]：
if x[i] == x[k] or abs(x[i] - x[k]) == abs(i - k): # 判断是否与x[k]冲突
return True
return False
# 套用子集树模板
def queens(k): # 到达第k行
global n, x, X
if k >= n: # 超出最底行
X.append(x[:]) # 保存（一个解），注意x[:]
else:
for i in range(n): # 遍历第0~n-1列（即n个状态）
x.append(i) # 皇后置于第i列，入栈
if not conflict(k): # 剪枝
queens(k + 1)
x.pop() # 回溯，出栈
def show(x):
global n
for i in range(n):
print('. ' * (x[i]) + 'X ' + '. ' * (n - x[i] - 1))
if __name__ == '__main__':
queens(0) # 从第0行开始
print(X[-1], '\n')
show(X[-1])
程序运行结果：
| 
转播
