搜索法

  • 穷举法
  • 回溯法
  • 分支界限法

穷举策略

  • 不经过思考（很少思考），把问题的所有情况和所有过程交给计算机去一一尝试。

    • 顺序查找
    • 穷举搜索

  • 穷举法解决问题的过程

    • 找出问题的范围
    • 找出约束条件

百钱百鸡问题

  • 我国古代数学家张丘建在《算经》一书中提出的数学问题：

    鸡翁一值钱五，鸡母一值钱三，鸡雏三值钱一。百钱买百鸡，问鸡翁、鸡母、鸡雏各何？

  • 算法一

    求解范围：每种鸡数目<=100
    约束条件：a+b+c=100 

                    ((5*a)+(3*b)+(c/3))=100

    1
    2
    3
    4
    5
    for(a=1;a<=100;a++) 
        for(b=1;b<=100;b++)
            for(b=1;b<=100;b++)           
       			if((5*a)+(3*b)+(c/3))==100)and(a+b+c=100 ))                 
               		printf("%d %d %d\n",a,b,c);

    算法效率：尝试1000000次

  • 优化

    • 缩减求解范围

    • 同时可能需要修改约束条件

1
2
3
4
5
6
for (a = 1; a <= 20; a++)
    for (b = 1; b <= 33; b++) {
        if ((100 - a - b) % 3 == 0&&(5 * a + 3 * b + (100 - a - b) / 3 == 100)) {
            printf("%d %d %d\n", a, b, 100-a-b);
        }
    }

回溯法

Backtracking

基本思想

image-20220428004603626

深度优先策略（DFS）

image-20220428004627934

  • 图的遍历（dfs）

image-20220428004921020

DFS实现

  • 像下面的图，要考虑图的连通性

image-20220428010149587

  • 伪代码
1
2
3
4
5
6
7
8
9
10
11
12
procedure explore(G,v)
visited[v] = true
for each edge (v,u) in E:
    if not visited[u]:
          explore(G,u)

procedure dfs(G)
for all v in V:
   visited[v] = false
for all v in V:
   if not visited[v]:
         explore(G,v)
  • 核心代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
//C[ ][ ]是图的邻接矩阵，visited[i]表示顶点i是否被访问过
For (i=0;i<=n-1;i++)   // n个顶点标志位初始化
    visited[i]=0;
 
DFSk (Graph g, int k)  //对图g的顶点K进行深度遍历
{  visited[k]=1;
    visit k;
    for (i=0;i<=n-1;i++)
       if (g.c[k][i]==1 && visited[i]==0)  DFSk(g,i);
}
 
DFS (Graph g)   //考虑g的连通性
{   for (i=0;i<=n-1,i++)
        if (visited[i]==0)  DFSk(g,i);
}

背包问题

01背包问题—物体不可分割

image-20220428010558519

普通背包问题—物体可分割

image-20220428010614757

回溯法求解01背包问题

image-20220428012147749

子集树和排列树

image-20220428010659497

image-20220428010721372

image-20220428010742055

子集树：0-1背包问题

image-20220428011022730

image-20220428011138108

排列树： 旅行售货员问题

image-20220428012356661

image-20220428012611027

剪枝函数

image-20220428012618493

image-20220428012710211

剪枝函数优化01背包问题

image-20220428012800629

  • 核心代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
private static void backtrack (int i)
   {// 搜索第i层结点
      if (i > n)  // 到达叶结点
      更新最优解bestx,bestw;return;
      r -= w[i];
      if (cw + w[i] <= c) {// 搜索左子树 背包还能装的下
         x[i] = 1;
         cw += w[i];
         backtrack(i + 1);
         cw -= w[i];      }
      if (cw + r > bestw)  {
         x[i] = 0;  // 搜索右子树 后面价值更高，放弃某件物品
         backtrack(i + 1);      }
      r += w[i];
   }

剪枝函数优化旅行售货员问题

image-20220428013129851

8皇后问题

image-20220428014001403

方法一

  • 若不考虑约束条件，每个皇后都可以尝试放在64个方格中，可以用简单穷举算法,构造如下： 
1
2
3
4
5
6
7
for p1:=1 to 64 do
for p2:=1 to 64 do   
for p3:=1 to 64 do     
for p8:=1 to 64 do     
if（任意两个皇后满足不在同一行、同一列、同一斜线上） 
	then          
输出该摆放方法

显然，这种不加条件约束的穷举，需要64的8次方次搜索，时间不够用。因此如果用穷举，需要加约束条件减少搜索次数

方法二

  • 题目已经规定了任意两个皇后不能位于同一行，那么就可以假定第1个皇后位于第一行，第2个皇后位于第二行……第8个皇后位于第八行。这样,每个皇后只需要在8个列的位置中进行选择: 
1
2
3
4
5
6
7
for p1:=1 to 8 do
	for p2:=1 to 8 do if p2<>p1 then     
		for p3:=1 to 8 do   if p3<>p2 then    
		……
        	for p8:=1 to 8 do         
        		if（任意两个皇后满足不在同一列、同一斜线上） then              
        			输出该摆放方法。

这个程序只需要8的8次方次运算

回溯法

  • 在N个皇后未放置完成前，摆放第I个皇后和第I+1个皇后的试探方法是相同的，因此完全可以采用递归的方法来处理。
  • 算法结构如下：
1
2
3
4
5
6
7
8
9
10
11
12
Procedure Try(I:integer)；{搜索第I行皇后的位置}
 var  j:integer;
 begin
  if I=n+1 then 输出方案；
  for j:=1 to n do 
    if 皇后能放在第I行第J列的位置 then begin
       放置第I个皇后；
       对放置皇后的位置进行标记；
       Try（I+1） 
       对放置皇后的位置释放标记；
    End;
 End;
  • 解向量：(x1, x2, … , xn)
  • 显约束：xi=1,2, … ,n
  • 隐约束：
    • 不同列：xi != xj
    • 不处于同一正、反对角线：|i-j|!=|xi-xj|
1
2
3
4
5
6
7
8
9
10
11
12
13
private static boolean place (int k){
    for (int j=1;j<k;j++)
    	if ((Math.abs(k-j)==Math.abs(x[j]-x[k]))||(x[j]==x[k])) return false;
    return true;
} 
private static void backtrack (int t){
      if (t>n) sum++;       //sum是可行方案的个数
        else
          for (int i=1;i<=n;i++) {
            x[t]=i;
            if (place(t)) backtrack(t+1);
           }
}

分支界限法

Branch-and-Bound

基本思想

image-20220428015748309

image-20220428015754954

image-20220428015812806

image-20220428015818014

image-20220428015826461

image-20220428015931186

BFS实现

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
public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x) {
        val = x;
    }
}

public List<List<Integer>> levelOrder(TreeNode root) {
    List<List<Integer>> allResults = new ArrayList<>();
    if (root == null) {
        return allResults;
    }
    Queue<TreeNode> nodes = new LinkedList<>();
    nodes.add(root);
    while (!nodes.isEmpty()) {
        int size = nodes.size();
        List<Integer> results = new ArrayList<>();
        for (int i = 0; i < size; i++) {
            TreeNode node = nodes.poll();
            results.add(node.val);
            if (node.left != null) {
                nodes.add(node.left);
            }
            if (node.right != null) {
                nodes.add(node.right);
            }
        }
        allResults.add(results);
    }
    return allResults;
}

image-20220428042630332

配套作业

配套作业——搜索

https://gallifrey.asia/posts/5bdd72ac472b/