DFS剪枝

DFS剪枝简介

DFS剪枝是一种启发式搜索算法，它通过对搜索树进行剪枝，来减少搜索树的大小，从而减少搜索时间。

DFS剪枝的基本思想是，在搜索树的每一步，都要判断是否可以直接跳过某些分支，从而减少搜索树的大小。

具体来说，DFS剪枝有以下几种方法：

  1. 剪枝准则：在搜索树的每一步，都要判断是否可以直接跳过某些分支，从而减少搜索树的大小。

  2. 启发式函数：启发式函数是指对节点的评估函数，它可以帮助搜索算法更好地选择下一步要探索的节点。

  3. 代价估计：代价估计是指估计节点的代价，并据此来判断是否应该继续探索该节点的子节点。

  4. 动态规划：动态规划是指利用搜索树的结构性质，对搜索树进行预处理，从而减少搜索树的大小。

  5. 启发式搜索：启发式搜索是指利用启发式函数对搜索树进行排序，从而减少搜索树的大小。

  6. 备忘录：备忘录是指在搜索树的每一步，都记录下已经探索过的节点，从而减少搜索树的大小。

  7. 并行搜索：并行搜索是指在多线程或多进程环境下，对搜索树进行搜索，从而减少搜索树的大小。

  8. 剪枝策略：剪枝策略是指对搜索树进行剪枝，从而减少搜索树的大小。

  9. 多目标搜索：多目标搜索是指在搜索树的每一步，都要同时考虑多个目标，从而减少搜索树的大小。

实例一：学生分队问题

问题描述

数字王国开学了，它们也和我们人类一样有开学前的军训，现在一共有 n 名学生，每个学生有自己的一个名字 ai
​
（数字王国里的名字就是一个正整数，注意学生们可能出现重名的情况），此时叛逆教官来看了之后感觉十分别扭，决定将学生重新分队。

排队规则为：将学生分成若干队，每队里面至少一个学生，且每队里面学生的名字不能出现倍数关系（注意名字相同也算是倍数关系）。

现在请你帮忙算算最少可以分成几队？

例：有 4 名学生 (2,3,4,4)，最少可以分成 (2,3)、(4)、(4) 共 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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
def check(x, group):
    for y in group:
        if y % x == 0 or x % y == 0:
            return False
    return True

def dfs(depth):
    # 最优解的剪枝
    global ans
    # 如果当前分组状态已经比ans大，则直接返回
    if len(Groups) > ans:
        return 

    # 当前是第depth层
    if depth == n:
        global ans
        ans = min(ans, len(Groups))
        return 
    
    # 每个学生的基础操作
    # 遍历每个分组
    for every_group in Groups:
        # 可行性剪枝
        if check(a[depth], every_group):
            every_group.append(a[depth])
            dfs(depth+1)
            every_group.pop()
    
    # 单独作为一组
    Groups.append([a[depth]])
    dfs(depth+1)
    Groups.pop()        



n = int(input())
a = list(map(int, input().split()))
# 学生分组,每个元素是一个列表，表示一个分组
Groups = []
ans = n

dfs(0)

print(ans)