迪三
0%

四.回溯算法

发表于 更新于 分类于 Valine：

原创 进阶算法概述

四.回溯算法

1.算法本质

  • 解决多选择问题
  • 选择时判断，符合条件继续，不符合条件返回
  • 把问题的解空间转化成了图(深度优先)或者树(左右根)的结构表示。

2.算法步骤

2.1 算法基本的步骤思想为：

  • 在搜索过程中动态产生问题的解空间
  • 只保存从根结点到当前扩张结点的路径
  • 深度优先方式搜索解空间，能找出满足约束条件的所有解

2.2 伪代码:

1
2
3
4
5
6
7
8
def Backtrack(t)
    if t>n :
        output(x) #记录可行解
    else:
        for i in ResultTree
            X[t] = h(i) # h(i)表示当前结点处的第i个可选值
            if constraint(t)&&bount(t) #解空间的约束函数和限界函数
                Backtrack(t+1)

3.回溯算法应用

3.1 八皇后问题

八皇后问题是一个以国际象棋为背景的问题：如何能够在 8×8 的国际象棋棋盘上放置八个皇后，使得任何一个皇后都无法直接吃掉其他的皇后？

为了达到此目的，任两个皇后都不能处于同一条横行、纵行或斜线上。八皇后问题可以推广为更一般的n皇后摆放问题：这时棋盘的大小变为n×n，而皇后个数也变成n。当且仅当 n = 1 或 n ≥ 4 时问题有解

  • Input

    无输入

  • Output

    多种

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    No. 1
    1 0 0 0 0 0 0 0 
    0 0 0 0 0 0 1 0 
    0 0 0 0 1 0 0 0 
    0 0 0 0 0 0 0 1 
    0 1 0 0 0 0 0 0 
    0 0 0 1 0 0 0 0 
    0 0 0 0 0 1 0 0 
    0 0 1 0 0 0 0 0 
    No. 2
    1 0 0 0 0 0 0 0 
    0 0 0 0 0 0 1 0 
    0 0 0 1 0 0 0 0 
    0 0 0 0 0 1 0 0 
    0 0 0 0 0 0 0 1 
    0 1 0 0 0 0 0 0 
    0 0 0 0 1 0 0 0 
    0 0 1 0 0 0 0 0 
    No. 3
    1 0 0 0 0 0 0 0 
    0 0 0 0 0 1 0 0 
    0 0 0 0 0 0 0 1 
    0 0 1 0 0 0 0 0 
    0 0 0 0 0 0 1 0 
    0 0 0 1 0 0 0 0 
    0 1 0 0 0 0 0 0 
    0 0 0 0 1 0 0 0
  • 求解思路

观察棋盘坐标

同一斜线上的“/”上的坐标点，横纵坐标之和相同

同一斜线上的“\”上的坐标点，横纵坐标之差相同

  • 基本步骤
  1. 判断皇后冲突
  2. 递归得到结果
  3. 输出所有结果
  • 代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
# state是一个元组，存放每行的坐标,从首行开始
# pos是当前行不与之前皇后冲突的位置
>>> def confict(state, pos):
    nextY = len(state)
    if pos in state: return True
    '''判断斜线'''
    for i in range(nextY):
        if nextY-pos == i-state[i]: return True
        if nextY+pos == i+state[i]: return True
    return False

>>> def queens(num, state=()):
        if num-1 == len(state): #若当前是最后一次选择
            for i in range(num):
            #遍历选择的所有值，此次选择不与前值冲突，以元祖形式返回该值
                if not confict(state, i):
                    yield (i,)
        else:
            for pos in range(num):
            #当前不是最后一次选择：
            #遍历所有取值，若不与之前的选择序列冲突，
            #“返回”当前选择取该值的基础上，接来的选择结果。
                if not confict(state, pos):
                    for result in queens(num, state+(pos,)):
                        yield (pos,) + result

                    
>>> for i in list(queens(8)):
        print(i)

3.2 数独问题

3.3 集合问题

3.4 图着色问题