搜索算法、装载问题

搜索算法

解空间树

子集树

比如n种可选物品的01背包，对其进行选择。解空间为长度为n的01向量表示。解空间树是一颗完全二叉树。

排列树

比如旅行商问题，对n进行排列。

解空间搜索方式

DFS

深度优先。回溯法。

BFS

广度优先或最小耗费优先。分支限界法。

在扩展节点处，先生成所有的儿子节点，再从活节点列表中选择一个最有利的节点作为新的扩展节点。

回溯法

就是穷举，深度优先去找到解空间中满足约束条件的所有解，再选择一个最好的出来。

类似于走迷宫：走到死路或者已经达不到最优解就及时回头。要注意剪枝。

搜索子集树

1
2
3
4
5
6
7
8
9
10
11
12
13
void dfs(int t) {
  if (t > n) {
    output(x);
    return;
  }
  // 0和1两种选择
  for (int i = 0; i <= 1; i++) {
    x[t] = i;
    if (legal(t)) {
      bfs(t+1);
    }
  }
}

搜索排列树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void dfs(int t) {
  if (t > n) {
    output(x);
    return;
  }
  // 遍历所有t的可能：还剩下的可选择的内容，前面t-1已经确定了
  for (int i = t; i <= n; i++) {
    swap(x[t], x[i]);
    if (legal(t)) {
      bfs(t + 1);
    }
    swap(x[t], x[i]);
  }
}

分支限界法

广度优先或者最小消费优先去搜索解空间树，去找到使目标函数达到极大或者极小解，某种意义下的最优解。

每个活节点只有一次机会成为扩展节点，成为时，就一次性产生其所有儿子节点。舍弃不可行或导致非最优解的儿子节点，其余儿子节点加入活节点列表。从活节点列表中取出下一个节点作为新的扩展节点。

广度优先搜索

队列式分支限界法

最小消费优先搜索

优先队列式分支限界法。每个活节点有一个优先级。通常用最大堆来实现最大优先队列。

装载问题

问题描述

\(n\)个集装箱质量分别为\(w_i\)， 要装上总容量为\(c\)的轮船。 问，怎样装，才能使装得最多？ \[ \begin{align} & \max \sum_{i}^nx_i\cdot w_i \\ & \sum_{i}^nx_i\cdot w_i \le c \\ & x_i \in\{0,1\}, \quad \text{表示装或不装} \end{align} \]

贪心解法

贪心策略：集装箱从轻到重排序，轻者先装， 直到超重。

BFS

有2艘轮船，\(\sum_i^n w_i \le c_1 + c_2\)， 怎样才能把n个集装箱装到这2艘轮船。

可知最优方案：尽量把第一艘轮船装满，剩余的装到第二艘上。

定义Solution

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
class Solution {
    public:
        // 集装箱数量
        int n;
        // 集装箱的重量
        vector<int> w;
        // 船的载重
        int c;
        // 当前重量
        int cw;
        // 最优重量
        int bestw;
		// 回溯遍历index=i的箱子
        void backtrack(int i);
		
  		// 构造函数
        Solution(const vector<int> &w, int c):w(w), c(c) {
            this->cw = 0;
            this->bestw = 0;
            this->n = w.size();
        }
};

int max_loading(const vector<int> &w, int c) {
    Solution solu(w, c);
    solu.backtrack(0);
    return solu.bestw;
}

无剪枝的dfs

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void Solution::backtrack(int i) {
    if (i == n) {
        if (cw > bestw) {
            bestw = cw;
        }
        return;
    }
	// 选择i
    if (cw + w[i] <= c) {
        cw = cw + w[i];
        backtrack(i + 1);
        cw = cw - w[i];
    }
    // 不选择i
    backtrack(i + 1);
}

剪枝的dfs

进入下一步遍历之前，检查\(\rm{cw+rest > bestw}\) ，如果剩下的所有加上都小于最优解的话，那么就不用进入了。

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
/*
 * 剪枝的dfs
 */
void Solution::dfs(int i) {
    if (i == n) {
        if (cw > bestw) {
            bestw = cw;
        }
        return;
    }
    // 剩余
    r = r - w[i];
    // 选择i
    if (cw + w[i] <= c) {
        cw += w[i];
        // 剪枝
        if (cw + r > bestw) {
            dfs(i + 1);
        }
        cw -= w[i];
    }

    // 不选择i，剪枝
    if (cw + r > bestw) {
        dfs(i + 1);
    }
    r = r + w[i];
}