当前位置：首页 > article >正文

扩展——双向搜索

article 2024/11/17 16:02:01

1. 基本概念

单向搜索：传统的搜索算法（如广度优先搜索 BFS、深度优先搜索 DFS）通常从起点开始，逐步扩展搜索到目标节点。搜索的时间复杂度与图的大小和结构有关。
双向搜索：双向搜索则同时从起点和终点进行搜索，两个搜索分别扩展，直到在中间相遇。因为每次搜索的深度都减少了一半。

2. 核心思想

双向搜索通过减少单向搜索的路径长度来提高效率。假设图的深度为 d，如果使用广度优先搜索（BFS）从起点到终点进行单向搜索，时间复杂度是 O(b^d)（其中 b 是图的分支因子）。而双向搜索则从起点和终点同时进行搜索，时间复杂度为 O(b^(d/2) + b^(d/2))，即 O(b^(d/2))。

题目

题解：

首先暴力的复杂度为（每个值加或不加），肯定是不行的（2^40），但是如果能将其分解为两个(2^20) ，这题就能被解决。

计算前一半的所有子集和：
- 通过递归或迭代的方法，枚举前一半题目的所有可能组合，计算它们的和，并存储到一个数组 b 中。大约时间复杂度2^20 （1e6）

计算后一半的所有子集和：

类似地，枚举后一半题目的所有可能组合，计算它们的和，并在后续结合前一半的子集和进行处理（我们对b数组进行排序和去重，得到排序数组，我们再对另一半进行搜索）。
对于后一半的每一个子集和 sum2，在 b 中查找满足 sum1 + sum2 <= T 的最大 sum1，从而更新最大时间和 maxSum。

最终，maxSum 即为符合条件的最大和。

#include<bits/stdc++.h>

using namespace std;
using ll = long long;
const int N = 50,M = 1e7+10;
int n,t,cnt;
ll a[N],b[M],ansMax;
void dfsPre(int k,ll sum)
{
    if(sum > t) return ;
    b[cnt++] = sum;
    // 先记录b数组，在判断:
    // 不论当前路径的 sum 是通过选择当前元素还是不选择当前元素产生的
    // 它都应该被记录到 b 数组中，以确保不会遗漏任何一个可能的子集和
    if(k >= (n + 1) / 2) return ;
    // 选a[k]和不选a[k]两种选择
    dfsPre(k + 1, sum + a[k]);
    dfsPre(k + 1, sum);

}
void dfsSuf(int k, ll sum){
    if(sum > t) return ;
    if(k > n) return ;

    // 考虑前半部分，二分查找b数组 + sum最大的不超过t的值
    int l = 0, r = cnt - 1;
    while(l < r){
        int mid  = (l + r + 1) >> 1;
        if(b[mid] + sum <= t) l = mid;
        else r = mid - 1;
    }
    if(b[r] + sum <= t) ansMax = max(ansMax,b[r] + sum);
    dfsSuf(k + 1, sum + a[k]);
    dfsSuf(k + 1, sum);

}
int main() {
    cin >> n >> t;
    for(int i = 0; i < n; i++) cin >> a[i];
    // a数组前半部分进行搜索
    dfsPre(0,0);
    // 对b数组进行排序以及去重
    sort(b, b + cnt);
    cnt = unique(b, b + cnt) - b;
    // a数组后半部分进行搜索
    dfsSuf((n + 1) / 2 , 0);
    cout << ansMax;
    return 0;
}

查看全文

http://www.kler.cn/a/282501.html