回溯算法经典问题及python代码实现

1. 八皇后

2. 0-1背包问题

# 0-1 bag problem

import sys

def f(no, cur_mass, things, num):
    global cur_max
    if no == num or cur_mass == W:
        if cur_mass > cur_max:
            cur_max = cur_mass
        return
    # case1：不加入第no+1个物品
    f(no+1, cur_mass, things, num)
    if things[no] + cur_mass <= W:
        f(no+1, cur_mass+things[no], things, num)

if __name__ == '__main__':
    # no表示当前观察到第几个物品了，things为待装入背包里物品的重量，num为待装入背包里物品的个数，
    # cur_max为当前背包中的物品重量之和的最大值，cur_mass为当前背包中的物品重量之和
    # 背包能装载的最大重量为W
    things = [1,3,5,2,-10,6,8,10,2,9,9,99]
    MAX_INT = sys.maxsize
    MIN_INT = -sys.maxsize-1
    W = 100
    cur_max = MIN_INT
    f(0, 0, things, 12)
    print('cur_max', cur_max)

如果我想打印出具体的方案，应该怎么修改呢

如果每个物品不仅重量不同，价值也不同。如何在不超过背包重量的情况下，让背包中的总价值最大？

3. 图的着色

4. 旅行商问题

5. 数独

6. 全排列

7. 正则表达式匹配

理解了回溯思想后，感觉再也不惧怕解决正则表达式了，不过千万要注意递归的退出条件

# 正则表达式
# 假设只含有？和*两种通配符
# ？表示0或1个任意字符
# *表示0或多个任意字符


def r_match(pattern_i, text_j, pattern, pattern_len, text, text_len):
    global matched
    # 如果已经有一种方案判定匹配成功，则直接退出其他方案的匹配过程
    if matched:
        return
    
    # 若正则表达式已经到结尾了, 且文本串也已经结束则匹配成功，结束；若正则串结束，但是文本串未结束，说明此次匹配失败
    if pattern_i == pattern_len:
        if text_j == text_len:
            matched = True
            return
        else:
            return
    
    # 若正则表达式遇到*, 任意通配符, 则剩下的均可跳过
    if pattern[pattern_i] == "*":
        for k in range(text_j, text_len+1):
            r_match(pattern_i+1, k, pattern, pattern_len, text, text_len)
    elif pattern[pattern_i] == "?":  # ?通配符，文本串可以选择跳过一个字符或不跳过
        r_match(pattern_i+1, text_j, pattern, pattern_len, text, text_len)
        r_match(pattern_i+1, text_j+1, pattern, pattern_len, text, text_len)
    else:
        if text_j < text_len and text[text_j] == pattern[pattern_i]:
            r_match(pattern_i+1, text_j+1, pattern, pattern_len, text, text_len)


pattern_case = "abc*e"
text_case = "abcdefe"

matched = False
r_match(0, 0, pattern_case, len(pattern_case), text_case, len(text_case))
print('matched', matched)

回溯算法本质上就是枚举，优点在于其类似于摸着石头过河的查找策略，且可以通过剪枝少走冤枉路。它可能适合应用于缺乏规律，或我们还不了解其规律 的搜索场景中。