搜索算法

回溯法

八皇后问题
8 × 8 的国际象棋棋盘上放置八个皇后,使得任何一个皇后都无法直接吃掉其他的皇后。任两个皇后都不能处于同一条横行、纵行或斜线上。

做法

枚举每一行的皇后放在哪个位置,并且和前面的皇后判断是否冲突,如果冲突就重新选位置,不冲突就继续下一行。直接 for 要写至少8个 for ,使用递归回溯来写可以少写很多行代码。
复杂度分析:表面上看起来这应该是个 O(N^N) 的算法,事实上因为实际可能的方案数很少,通过判断剪枝,复杂度是相当低的。

int Queue_col_in_row[8]; int ans = 0; void dfs(int row){ if(row == 8) { ++ans; return; } for(int col = 0; col < 8; ++col){ Queue_col_in_row[row] = col; bool flag = true; for(int prerow = 0; prerow < row; ++prerow){ if((Queue_col_in_row[row] == Queue_col_in_row[prerow]) || (abs(Queue_col_in_row[row] - Queue_col_in_row[prerow]) == abs(row - prerow))) { flag = false; break; } } if(flag) dfs(row + 1); } }

另一种暴力——状压枚举

N 个数 a_1 … a_n ,选一个子集出来,相加的和为 k 的方案数有多少种? (N \leq 15 , -1e9 \leq a_i \leq 1e9 , -1e9 \leq k \leq 1e9)
显然可以使用上面讲到的回溯法
复杂度分析:每次两种选择,复杂度 O(2^N)

int a[N]; int ans = 0; int k, n; void dfs(int pos, long long sum){ if(pos == n) { if(sum == k) ++ans; return; } dfs(pos + 1, sum + a[pos]); dfs(pos + 1, sum); }

Tips:这种情况较多的枚举,使用递归进行枚举有可能会出现栈空间溢出的情况!
一般电脑的栈空间为 8MB

这种每次都是2种选择的结构,亦可以使用二进制数状态压缩来枚举
复杂度分析:复杂度 O(N*2^N)

int a[N]; int ans = 0; int k, n; void _search(){ for(int msk = 0; msk < 1<<n; ++msk){ long long sum = 0; for(int i = 0; i < n; ++i){ if((1 << i) & msk){ sum += a[i]; } } if(sum == k) ++ans; } }

Meet in Middle

问题同上, N 的取值范围变为 N \leq 35
考虑和上面相同的方法,复杂度为 O(N*2^N) ,大约为 O(1.2e12) ,按照计算机 1s 能跑 1e8 来算,能跑 3.34h
考虑把序列分成两半,分成两个求和问题,变成了求 \left \lceil \frac{N}{2} \right \rceil 个数选子集求出的和有哪些,然后去另一半中查询。这样求方案数的方法即在其中一边求出一种和为 x ,就去另半边查找 k – x 的方案数,此处查询使用 STL 中的 map 进行优化。
复杂度分析: O({\left \lceil \frac{N}{2} \right \rceil} * 2^{\left \lceil \frac{N}{2} \right \rceil} * log_2 2^{\left \lceil \frac{N}{2} \right \rceil} ) = O({\left \lceil \frac{N^2}{4} \right \rceil} * 2^{\left \lceil \frac{N}{2} \right \rceil})
int a[N];
long long ans = 0;
int k, n;
map<long long, long long> M;

void _search(){
    int m = n >> 1;
    for(int msk = 0; msk < 1<<m; ++msk){
        long long sum = 0;
        for(int i = 0; i < m; ++i){
            if((1 << i) & msk){
                sum += a[i];
            }
        }
        M[sum]++;
    }

    for(int msk = 0; msk < 1<<(n-m); ++msk){
        long long sum = 0;
        for(int i = 0; i < n - m; ++i){
            if((1 << i) & msk){
                sum += a[i + m];
            }
        }
        if(M.count(k - sum)){
            ans += M[k - sum];
        }
    }
}
分类: 未分类

发表评论

电子邮件地址不会被公开。 必填项已用*标注

隐藏
变装