双向搜索Meet in Middle

本文讲的双向搜索为Meet in Middle，有些时候也翻译为折半搜索。折半搜索（Meet-in-the-middle，简称 MITM）是一种算法策略，通常应用于解决一些需要枚举所有可能解的暴力搜索问题。其基本思想是将问题拆分成两部分，并从两端同时搜索，最后在中间相遇合并结果。这种方法能够有效地减少暴力搜索的时间复杂度，使得原本不可行的暴力解法在一定的约束下变得可行。

折半搜索的流程

1. 拆分问题：将原问题拆分为两个较小的子问题，分别处理。
2. 分别搜索：对这两个子问题分别进行搜索并记录中间结果。
3. 合并结果：在两部分中间结果中进行匹配或比较，从而得出最终解。

复杂度分析

在讨论折半搜索的复杂度时，我们需要从不同角度进行分析，特别是空间复杂度、时间复杂度、以及其与其他算法（如暴力枚举、动态规划等）的比较。

时间复杂度

折半搜索的核心思想是将原问题拆分成两个子问题，每个子问题进行搜索，最后将两个部分的结果合并。对于一个大小为 $n$ 的问题，折半搜索将问题拆分为两个大小为 $n/2$ 的子问题。假设在这两个子问题中，我们需要遍历所有可能的子集或者组合，然后再将它们的结果合并。

• 在没有优化的情况下，暴力搜索一个规模为 $n$ 的问题的时间复杂度为 $O(2^n)$。但是，通过折半搜索，我们将问题拆分成两部分，每部分的规模为 $n/2$，而每部分需要遍历的所有子集和组合数为 $2^{n/2}$。
• 合并这两个部分的结果需要 $O(2^{n/2})$ 的时间，因为我们要检查第一部分的每个子集是否可以和第二部分的某个子集匹配。

因此，折半搜索的总时间复杂度是： $O(2^{n/2}) + O(2^{n/2}) = O(2^{n/2})$ 相比暴力搜索的 $O(2^n)$，折半搜索的时间复杂度减少了一个数量级。对于大型问题，折半搜索的这种性能提升可以使得问题在实际应用中变得可解。

不过，折半搜索的复杂度和问题的具体结构密切相关。在某些问题中，我们可能还需要做更多的处理和合并工作，这会导致额外的时间开销。

空间复杂度

折半搜索的空间复杂度通常与我们如何存储中间结果有关。在标准的折半搜索中，我们需要存储两个部分的子集和，这两部分的大小是 $2^{n/2}$。因此，空间复杂度为： $O(2^{n/2})$ 这是因为我们需要存储每一部分的子集和，且每一部分有 $2^{n/2}$ 个子集。

对于大规模问题，存储这些中间结果可能会占用大量内存。因此，在使用折半搜索时，空间复杂度也是一个需要考虑的因素，尤其是在内存资源有限的情况下。

与其他算法的比较

1. 暴力枚举：

   • 传统的暴力枚举算法通常需要遍历所有可能的解，假设有 $n$ 个元素，时间复杂度为 $O(2^n)$。
   • 折半搜索通过将问题拆分成两部分，将时间复杂度降低为 $O(2^{n/2})$。因此，折半搜索对于规模较大的问题具有显著的优势。

2. 动态规划：

   • 动态规划是另一种常用的优化策略，特别是在解决有重叠子问题的情况下。动态规划的时间复杂度通常为 $O(n^2)$ 或 $O(n^3)$ 甚至更高，具体取决于问题的结构。
   • 相比之下，折半搜索不需要存储大量的中间状态，而是通过分而治之的策略来减少计算量。然而，动态规划在某些问题中仍然是更有效的解法，尤其是当问题具有“最优子结构”特性时。

3. 分治算法：

   • 分治算法和折半搜索有相似之处，都是通过将问题拆分成多个子问题来减少计算复杂度。然而，分治算法通常要求子问题是独立的，且不需要像折半搜索那样在两部分结果中进行合并。
   • 在折半搜索中，合并的过程本身也可能会带来额外的复杂度，特别是在合并过程需要进行大量匹配或计算时。

复杂度小结

• 时间复杂度：折半搜索的时间复杂度通常为 $O(2^{n/2})$，显著低于暴力搜索的 $O(2^n)$。
• 空间复杂度：空间复杂度通常为 $O(2^{n/2})$，与存储子集和的数量成正比。
• 适用场景：适用于能够被拆分为两部分的问题，特别是那些需要遍历所有子集的组合问题，如子集和问题、背包问题等。

折半搜索通过巧妙地将大问题分解为小问题，从而减少了搜索的时间和空间开销。然而，在使用折半搜索时，仍然需要权衡问题规模、存储开销以及合并操作的复杂度。

C++模板代码

以下是一个使用 C++ 实现的折半搜索模板，适用于解决子集和问题：

#include <iostream>
#include <vector>
#include <unordered_set>
#include <algorithm>

using namespace std;

bool meet_in_the_middle(const vector<int>& nums, int target) {
    int n = nums.size();
    int mid = n / 2;

    // 第一部分
    vector<int> first_half_sums;
    for (int i = 0; i < (1 << mid); ++i) {
        int sum = 0;
        for (int j = 0; j < mid; ++j) {
            if (i & (1 << j)) {
                sum += nums[j];
            }
        }
        first_half_sums.push_back(sum);
    }

    // 第二部分
    vector<int> second_half_sums;
    for (int i = 0; i < (1 << (n - mid)); ++i) {
        int sum = 0;
        for (int j = 0; j < (n - mid); ++j) {
            if (i & (1 << j)) {
                sum += nums[mid + j];
            }
        }
        second_half_sums.push_back(sum);
    }

    // 将第二部分的和存入哈希集合
    unordered_set<int> second_half_set(second_half_sums.begin(), second_half_sums.end());

    // 检查第一部分和第二部分的和是否能组成目标值
    for (int sum : first_half_sums) {
        if (second_half_set.find(target - sum) != second_half_set.end()) {
            return true;
        }
    }

    return false;
}

int main() {
    vector<int> nums = {3, 34, 4, 12, 5, 2};
    int target = 9;

    if (meet_in_the_middle(nums, target)) {
        cout << "存在和为目标值的子集。" << endl;
    } else {
        cout << "不存在和为目标值的子集。" << endl;
    }

    return 0;
}

折半搜索（Meet-in-the-middle）通过巧妙地将问题拆分成两个部分，并从两端同时进行搜索，显著提高了解决组合问题的效率。它不仅在时间复杂度上比暴力搜索要高效得多，而且在许多算法竞赛问题中表现出色。尽管折半搜索的空间复杂度可能较高，但在问题规模适中的情况下，这种方法依然是一个有效的选择。

例题

P5691 [NOI2001] 方程的解数

题目描述

已知一个 $n$ 元高次方程：

$$\sum\limits_{i=1}^n k_ix_i^{p_i} = 0$$

其中：$x_1, x_2, \dots ,x_n$ 是未知数，$k_1,k_2, \dots ,k_n$ 是系数，$p_1,p_2,…p_n$ 是指数。且方程中的所有数均为整数。

假设未知数 $x_i \in [1,m] \space ( i \in [1,n])$，求这个方程的整数解的个数。

输入格式

第一行一个正整数 $n$，表示未知数个数。
第二行一个正整数 $m$。 接下来 $n$ 行，每行两个整数 $k_i,p_i$。

输出格式

输出一行一个整数，表示方程解的个数。

输入输出样例 #1

输入 #1

3
150
1 2
-1 2
1 2

输出 #1

178

说明/提示

【数据范围】

对于 $100\%$ 的数据，$1\le n \le 6$，$1\le m \le 150$，且

$$\sum\limits_{i=1}^n |k_im^{p_i}| < 2^{31}$$

答案不超过 $2^{31}-1$，$p_i \in \mathbb N^*$。

参考程序：双向DFS+二分

#include <bits/stdc++.h>

using namespace std;

int n, m;
int k[10]; // 系数数组
long long p[10]; // 指数数组
int w[8000000]; // 存储第一部分的所有可能值
int tmp; // 第一部分的长度
int cnt = 0; // 存储第一部分的解的个数
long long ans = 0; // 最终的答案

// 计算 x^y 的值
int calpow(int x, long long y) {
    int res = 1;
    for (long long i = 1; i <= y; i++) {
        res *= x;
    }
    return res;
}

// 深度优先搜索 DFS，枚举第一部分的所有组合
void dfs1(int now, int sum) {
    if (now == tmp) {
        w[++cnt] = sum;
        return;
    }
    for (int i = 1; i <= m; i++) {
        dfs1(now + 1, sum + k[now] * calpow(i, p[now]));
    }
}

// 深度优先搜索 DFS，枚举第二部分的所有组合，并通过二分查找计算答案
void dfs2(int now, int sum) {
    if (now > n) {
        // 二分查找找到匹配的解
        int find = upper_bound(w + 1, w + cnt + 1, -sum) - 
                    lower_bound(w + 1, w + cnt + 1, -sum);
        ans += find;
        return;
    }
    for (int i = 1; i <= m; i++) {
        dfs2(now + 1, sum + k[now] * calpow(i, p[now]));
    }
}

int main() {
    scanf("%d%d", &n, &m); // 读取未知数个数 n 和最大值 m
    for (int i = 1; i <= n; i++) {
        scanf("%d%lld", &k[i], &p[i]); // 读取系数 k 和指数 p
    }

    tmp = n / 2 + 1; // 将未知数分为两部分

    // 计算第一部分的所有解
    dfs1(1, 0);

    // 对第一部分的结果排序
    sort(w + 1, w + cnt + 1);

    // 计算第二部分的所有解，并通过二分查找计算答案
    dfs2(tmp, 0);

    // 输出最终的答案
    printf("%lld\n", ans);

    return 0;
}

思路解析

- 分治法： 通过将问题划分为两部分，降低了计算复杂度。对于每部分，我们枚举所有可能的解，将解的结果存储起来，最后利用二分查找求解匹配的解对。

- 二分查找： 对于第二部分的每个解，通过二分查找来查找第一部分解中能与其相加得到零的项。由于二分查找的时间复杂度是 $(O(log n))$，所以这一过程的时间复杂度是 $(O(n \log n))$，进一步提高了算法效率。

P10484 送礼物

题目描述

作为惩罚，GY 被遣送去帮助某神牛给女生送礼物 (GY：貌似是个好差事）但是在 GY 看到礼物之后，他就不这么认为了。某神牛有 $N$ 个礼物，且异常沉重，但是 GY 的力气也异常的大 (-_-b)，他一次可以搬动重量和在 $w$ 以下的任意多个物品。GY 希望一次搬掉尽量重的一些物品，请你告诉他在他的力气范围内一次性能搬动的最大重量是多少。

输入格式

第一行两个整数，分别代表 $W$ 和 $N$。

以后 $N$ 行，每行一个正整数表示 $G_i$。

输出格式

仅一个整数，表示 GY 在他的力气范围内一次性能搬动的最大重量。

输入输出样例 #1

输入 #1

20 5
7
5
4
18
1

输出 #1

19

说明/提示

对于所有测试数据，$1 \le N \le 46$, $1 \le W,G[i] \le 2^{31}-1$。

参考程序：DFS+二分

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

vector<ll> a, b;
ll w, n, g[50];

// 计算子集和
void dfs(int l, int r, ll sum, vector<ll> &v) {
    if (l > r) {
        if (sum <= w) v.push_back(sum);
        return;
    }
    dfs(l + 1, r, sum + g[l], v);
    dfs(l + 1, r, sum, v);
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> w >> n;
    for (int i = 0; i < n; i++) cin >> g[i];

    // 计算左右两部分的子集和
    dfs(0, n / 2 - 1, 0, a);
    dfs(n / 2, n - 1, 0, b);

    sort(b.begin(), b.end());

    ll ans = 0;
    for (ll x : a) {
        if (x > w) continue;
        auto it = upper_bound(b.begin(), b.end(), w - x);
        if (it != b.begin()) ans = max(ans, x + *(--it));
    }

    cout << ans << '\n';
    return 0;
}

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

int n, m; // 物品数量n，背包最大容量m
int g[50]; // 存储物品的重量
int w[1 << 25]; // 存储能够放进背包的重量
int ans, cnt; // w的数量为cnt，记录当前解的最优值

// dfs1函数：搜索前半部分的物品，边界是 u = n / 2
void dfs1(int u, int s) {
    if (u == n / 2) { 
        w[cnt++] = s;  // 记录当前背包组合的重量
        return;
    }
    // 不选择当前物品
    dfs1(u + 1, s); 
    // 选择当前物品，且背包容量不超过m
    if (g[u] <= m - s) dfs1(u + 1, s + g[u]);
}

// dfs2函数：搜索后半部分的物品，并通过二分查找计算最优解
void dfs2(int u, int s) {
    if (u == n) { 
        ans = max(ans, *(upper_bound(w, w + cnt, m - s) - 1) + s); // 二分查找
        return;
    }
    // 不选择当前物品
    dfs2(u + 1, s); 
    // 选择当前物品，且背包容量不超过m
    if (g[u] <= m - s) dfs2(u + 1, s + g[u]);
}

int main() {
    cin >> m >> n; // 输入背包容量m和物品数量n
    for (int i = 0; i < n; i++) cin >> g[i]; // 输入物品的重量

    // 将物品按照重量从大到小排序，优化搜索顺序
    sort(g, g + n, greater<int>());
    
    // 计算前半部分物品的所有组合
    dfs1(0, 0);
    
    // 对前半部分的结果进行排序
    sort(w, w + cnt);
    
    // 去重并更新cnt的值
    cnt = unique(w, w + cnt) - w;
    
    // 计算后半部分物品的所有组合，并计算最终的最优解
    dfs2(n / 2, 0);
    
    // 输出结果
    cout << ans << endl;

    return 0;
}

思路解析

- 分治法： 将礼物分为两部分，减少了可能的组合数量。每部分最多有 (2^{N/2}) 种组合，这比直接考虑所有 (2^N) 种组合要高效。

- 二分查找： 利用二分查找对第二部分的组合进行优化，可以在对 (a) 中的每个元素进行查询时快速找到最佳解。

总结

折半搜索作为一种优化暴力搜索的方法，在算法竞赛中具有广泛的应用。通过将问题拆分为两部分，折半搜索能够有效地减少计算量，尤其在面对中等规模的组合问题时表现优秀。理解折半搜索的工作原理和应用场景，能够帮助选手在竞赛中更高效地解决一些看似复杂的问题。然而，折半搜索也并非万能，它的适用性和效果依赖于问题的具体结构，选手在使用时需要根据实际情况进行合理选择。希望本文能够帮助读者更好地理解和应用折半搜索，提升算法竞赛中的解题能力。