标签：return 进阶 int rest step 搜索 ans

搜索进阶

前提提要

这一章不会有多余的题解，都是例题，当做知识点来讲

前置知识

众所周知，我们写搜索第一步是设计搜索状态，然后再次基础上优化，让他跑的更快

搜索题不要过多纠结于他的时间复杂度，只有 \(\mathcal{O}\)（能过、不能过）这两种时间复杂度（

\(\mathcal{P}art\) 1. 设计搜索状态

略过，应该都知道吧

\(\mathcal{P}art\) 2. 剪枝

经典例题：小木棍子（小波）

乔治有一些同样长的小木棍，他把这些木棍随意砍成几段，直到每段的长都不超过 50。

现在，他想把小木棍拼接成原来的样子，但是却忘记了自己开始时有多少根木棍和它们的长度。

给出每段小木棍的长度，编程帮他找出原始木棍的最小可能长度。

\(\mathcal{S}olvetion\) 1. 普通搜索

我们设 \(dfs(step,rest,last,ans)\) 代表现在拼到 \(step\) 跟棍子，这根棍子还差 \(rest\)，上一个木棍长度为 \(last\)，容易写出21pts的代码

bool dfs(int ans, int step, int rest, int last) {
	if (step == n) {
		if (rest != ans) return false;
		return true;	
	}
	bool f = false;
	for (int i = n; i >= 1; i --) {
		if (v[i] || a[i] > rest || a[i] > last) continue;
		v[i] = 1;
		if (a[i] == rest) {
			f |= dfs(ans, step + 1, ans, ans);
			if (f == true) return true;
		}else {
			f |= dfs(ans , step + 1, rest - a[i], a[i]);
			if (f == true) return true;
		}
		v[i] = 0;
	} 
	return false;
}

\(\mathcal{S}olvetion\) 2. 剪枝进行时

容易想到，木棍子的长度肯定是总长度的因子
我们想到，更长的棍子灵活性更差，短的棍子代价更高，所以当我们从后往前枚举时，这个长棍子已经可以满足，那就不用再试更小的棍子了，直接返回
第一个棍子必须要评成功，因为它是最长的，他如果这里拼不了，哪里拼的了？
我们发现，如果有一段是连续的，只需要判断第一个棍子，其余棍子直接跳过
有了上面的思路，我们很容易想到用桶排优化些常数

至此我们就完成了这道题，注意点细节

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 70;

int n, a[MAXN], t[MAXN];

int maxl, suml;

bool dfs(int ans, int step, int rest, int last) {
	if (step == n) {
		if (rest != ans) return false;
		return true;
	}
	bool f = false;
	for (int i = min(last, min(rest, maxl)); i >= 1; i --) { if (t[i]) {//注：要和maxl取min哦
		-- t[i];//i为木棍的长度 
		if (i == rest) {
			f |= dfs(ans, step + 1, ans, ans);
			++ t[i];
			return f;
			//如果一个棍子可以刚好容纳进去，肯定是最优
			//如果不行就真的不行了
			//如果存在更小的几个可以拼成一个棍子
			//那么和吧这个棍子拿出去根其他木棍拼等价
		}else {
			f |= dfs(ans , step + 1, rest - i, i);
			++ t[i];
			if (f == true) return true;
		}
		if (rest == ans) return f;
		//如果新的一根棒子连第一根都拼不下，其他的也不行 
		//如果存在第二根棒子可以，那么第一根棒子就永远荒废掉了 
		} 
	}
	return false;
}

int main () {
	cin >> n;
	for (int i = 1; i <= n; i ++) cin >> a[i], t[a[i]] ++, maxl = max(maxl, a[i]), suml += a[i];
	for (int l = maxl; ; l ++) 
		if (suml % l == 0) 
			if (dfs(l, 0, l, l)) 
				cout << l << "\n", exit(0);	
	return 0; 
}

\(\mathcal{Part}\) 3.双向搜索

总所周知，我们的 \(bfs\) 是从一头搜到另外一头，这就会导致我们要遍历完整个搜索树

但是我们从答案那端也同时搜，那么这个搜索只需要搜一半不到就行了，大大提高了算法的效率

我们这里用八数码为例题讲解

我们使用双向搜索，把每个八数码变成一个具体的状态，然后我们就可以搜索（~~这道题不用双向搜索也可以过~~

#include<bits/stdc++.h>

using namespace std;

struct node{
	int w[4][4];
	int init() {
		int h = 0;
		for (int i = 1; i <= 3; i ++)
			for (int j = 1; j <= 3; j ++)
				h = h * 10 + w[i][j];
		return h;
	}
	node(int x) {
		for (int i = 3; i >= 1; i --) 
			for (int j = 3; j >= 1; j --)
				w[i][j] = x % 10, x /= 10;
	}
};

typedef map<int, int> Map;
typedef queue<node> Que;

const int D[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

void bfs(Que &Q1, Que &Q2, Map &M1, Map &M2) {
	node u = Q1.front(); Q1.pop();
	
	int x, y, h1 = u.init();
	for (int i = 1; i <= 3; i ++)
		for (int j = 1; j <= 3; j++)
			if (u.w[i][j] == 0)
				x = i, y = j;
	 
	for (int d = 0; d < 4; d ++) {
		int tx = x + D[d][0], ty = y + D[d][1];
		if (1 <= tx && tx <= 3 && 1 <= ty && ty <= 3) {
			node v = u;
			swap(v.w[x][y], v.w[tx][ty]); 
			int h2 = v.init();
			if (!M1.count(h2)) {
				Q1.push(v), M1[h2] = M1[h1] + 1;
			}
			if (M2.count(h2)) cout << M1[h1] + 1 + M2[h2], exit(0);
		}
	}
}

int main () {
	int s, e = 123804765;
	cin >> s;
	if (s == e) cout << 0 << endl, exit(0);
	Map M1, M2; Que Q1, Q2;
	Q1.push(node{s}), M1[s] = 0;
	Q2.push(node{e}), M2[e] = 0;
	while (!Q1.empty() && !Q2.empty()) {
		bfs(Q1, Q2, M1, M2);
		bfs(Q2, Q1, M2, M1);
	}
	return 0;
}

\(\mathcal{Part}\) 4.折半搜索

这种题和状态压缩可以结合在一起，也可以和搜索

在 \(n\) 的规模比较小的时候，我们一般考虑状态压缩和搜索，但正巧 \(n \le 40\) 超过了范围，但是 \(\cfrac{n}{2}\) 没有，我们这时就可以考虑折半搜索

我们这里用 P4799 [CEOI2015 Day2] 世界冰球锦标赛作为例题讲解

如果考虑用朴素的背包，时间复杂度为 \(\mathcal{O}(nm)\)，这里的 \(m\) 特别大，但是 \(n\) 特别小，但是又不能直接使用搜索，考虑折半

我们讲前 \(\lfloor \cfrac{n}{2}\rfloor\) 作为一组，将合为 \(i\) 的状态记下来，剩下的同理

我们考虑怎么合并搜索树

我们任取左边的一个状态，使用二分搜索找到 \(a+b> m\) 的第一个值，他前面的都是可以的

至此完成了题目

#include<bits/stdc++.h>

using namespace std;

const int MAXN = 40 + 7;
const int MAXM = (1 << 20 + 3);

typedef long long ll;

int  n, t;
ll a[MAXN], m, W[MAXM];

int main () {
	cin >> n >> m;
	for (int i = 1; i <= n; i ++) cin >> a[i];
	int p = n / 2, u = 1 << p, v = 1 << n - p;
	for (int i = 0; i < u; i ++) {
		ll w = 0;
		for (int j = 1; j <= p; j ++) 
			if (i & (1 << j - 1)) w += a[j];
		W[++t] = w;
	}
	sort(W + 1, W + 1 + t);
	
	ll ans = 0;
	for (int i = 0; i < v; i ++) {
		ll w = 0;
		for (int j = 1; j <= n - p; j ++) 
			if (i & (1 << j - 1)) w += a[p + j];
		ans += upper_bound(W + 1, W + 1 + t, m - w) - W - 1;
	}
	cout << ans << endl;
	return 0;
}

\(\mathcal{Part}\) 5.迭代加深搜索

在某些问题我们需要用 \(dfs\) 来解决问题时，发现搜索树无限宽或者无限深

这时，我们可以使用迭代加深搜索来进行剪枝，限制深度，可能会有意想不到的剪枝哦

这里我们用P1763 埃及分数进行讲解

我们设 \(limit\) 为这次搜索的最深深度，因为我们是从大到小进行枚举，设这一层最小分数为 \(\cfrac{1}{x}\)

则其天然满足（设 \(last\) 为上一个选的数，\(rest\) 为剩下的分数），

\[\begin{cases} \cfrac{1}{x} &< \cfrac{1}{last}\\ \cfrac{1}{x} &\le rest\\ \cfrac{1}{x}\times(limit-depth)&\ge rest \end{cases} \]

这下，我们就可以写了

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

struct Frac{
	ll a, b;
	Frac(ll _a = 0, ll _b = 1) : a(_a), b(_b){};
	inline Frac maintain() {
		ll d = __gcd(a, b); a /= d, b /= d;
		return *this;//返回本身 
	}
	inline Frac operator -(Frac x) {
		ll d = __gcd(b, x.b);
		ll ta = x.b / d * a - b / d * x.a;
		ll tb = b / d * x.b;
		//不能先乘后除，不然会炸 
		return Frac(ta, tb).maintain(); 
	}
};

const int MAXN = 1e2 + 7;

int A[MAXN], R[MAXN];

bool dfs(int limit, int depth, Frac rest, int last) {
	if (depth > limit) return false;
	int l = max(1ll * last + 1ll, rest.b / rest.a + !!(rest.b % rest.a));//向上取	整 
	int r = rest.b * (limit - depth) / rest.a;
	bool f = 0;
	for (int i = l; i <= r; i ++) {
		A[depth + 1] = i;
		if (rest.a == 1 && rest.b == i) {
			if (R[limit] == 0 || A[limit] < R[limit]) 
				for (int j = 1; j <= limit; j ++) R[j] = A[j];
			return true;
		}
		f |= dfs(limit, depth + 1, rest - Frac(1, i), i);
	}
	return f;
} 

int main () {
	int a, b;
	cin >> a >> b;
	for (int limit = 1; ; limit ++) {
		if (dfs(limit, 0, Frac(a, b).maintain(), 1)) {
			for (int j = 1; j <= limit; j ++) 
				cout << R[j] << " ";
			return 0;
		}
	}
		
	return 0;
}

\(\mathcal{P}art\) 6. \(A^\) 和 \(Ida^\)

我们在进行搜索的时候，总是盲目的乱搜，找不到一个搜索的方向，这就需要我们引出估价函数了

我们记估价函数 \(g(x)\) 和最优状态 \(h(s)\)，估价函数满足 \(g(s)\le h(s)\)

因此，估价函数被称为“最完美函数”（~~虽然不太可能达到~~

\(A^*\)

就是在 \(bfs\) 基础上加上估价函数，使用优先队列进行排序，决定搜索的顺序

\(Ida*\)

就是在迭代搜索的前提下，加上估价函数，当前 \(depth+g(s) > limit\) 就退出

我们使用P2324 [SCOI2005]骑士精神进行讲解

这道题显而易见的估价函数设计为：

我们设一步回到它的位置，即估价函数的值就为多少匹马不在它该在的位置上

因此我们写出 \(A^*\)

#include<bits/stdc++.h>

using namespace std;

const int E[6][6] = {
	{},
	{0, 1, 1, 1, 1, 1},
	{0, 0, 1, 1, 1, 1},
	{0, 0, 0, 2, 1, 1},
	{0, 0, 0, 0, 0, 1},
	{0, 0, 0, 0, 0, 0}
};

const int D[8][2] = {
	{2, 1}, {2, -1}, {-2, 1}, {-2, -1},
	{1, 2}, {1, -2}, {-1, 2}, {-1, -2}
};

struct Node{
	int w[10][10], x, y, step;
	int init() {//类似哈希 
		int h = 0;
		for (int i = 1; i <= 5; i ++)
			for (int j = 1; j <= 5; j ++)
				h = h * 2 + w[i][j];
		h = h * 6 + x, h = h * 6 + y;
		return h;
	}
	int estimate() {//估价函数 
		int h = 0;
		for (int i = 1; i <= 5; i ++) {
			for (int j = 1; j <= 5; j ++) {
				if (!(i == x && j == y)) 
					h += E[i][j] != w[i][j];
			}
		}
		return h; 
	}
	bool operator <(const Node x) const {return false; }
};

typedef pair<int, Node> Pair;

inline char readchar() {char c; while (!isgraph(c = getchar())); return c;} //以防意外 

int main () {
	int T;
	for (cin >> T; T; T --) {
		priority_queue<Pair, vector<Pair>, greater<Pair> > Q;
		map <int, bool> M;
		Node s; s.step = 0;
		for (int i = 1; i <= 5; i ++)
			for (int j = 1; j <= 5; j ++) {
				char c = readchar();
				if (c == '0') s.w[i][j] = 0;
				else if (c == '1') s.w[i][j] = 1;
				else s.w[i][j] = 0, s.x = i, s.y = j;		
			}
		Q.push(make_pair(0 + s.estimate(), s));
		M[s.init()] = true; bool flag = false;
		while (!Q.empty()) {
			Pair p = Q.top(); Node u = p.second; Q.pop();
			if (u.estimate() == 0) {
				cout << u.step << endl;
				flag = true;
				break;
			}
			if (u.step >= 15) continue;
			for (int d = 0; d < 8; d ++) {
				int tx = u.x + D[d][0], ty = u.y + D[d][1];
				if (1 <= tx && tx <= 5 && 1 <= ty && ty <= 5) {
					Node v = u;
					swap(v.w[u.x][u.y], v.w[tx][ty]);
					v.x = tx, v.y = ty;
					v.step = u.step + 1;
					int e = v.step + v.estimate();
					if (e > 15) continue;
					if (!M.count(v.init())) {
						M[v.init()] = true;
						Q.push(make_pair(e, v));
					}
				}
				
			}
		}
		if (!flag) cout << -1 << endl;
	}	
		
	return 0;
}

我们写出 \(Ida^*\)

#include<bits/stdc++.h>
using namespace std;
typedef long long i64;
const int INF = 2147483647;
const int E[6][6] = {
    {},
    {0, 1, 1, 1, 1, 1},
    {0, 0, 1, 1, 1, 1},
    {0, 0, 0, 2, 1, 1},
    {0, 0, 0, 0, 0, 1},
    {0, 0, 0, 0, 0, 0}
};
const int D[8][2] = {
    {2, 1}, {2, -1}, {-2, 1}, {-2, -1},
    {1, 2}, {1, -2}, {-1, 2}, {-1, -2}
};
struct Node{
    int W[6][6], x, y, step;  // (x, y) 为空格位置
    int to_int(){
        int h = 0;
        for(int i = 1;i <= 5;++ i)
            for(int j = 1;j <= 5;++ j)
                h = h * 2 + W[i][j];
        h = h * 6 + x;
        h = h * 6 + y;
        return h;
    }
    int estimate(){
        int h = 0;
        for(int i = 1;i <= 5;++ i)
        for(int j = 1;j <= 5;++ j)
            if(!(i == x && j == y))
                h += E[i][j] != W[i][j];
        return h;
    }
    bool operator <(const Node x) const { return false; }
};
using Pair = pair<int, Node>;

char readchar(){
    char c; while(!isgraph(c = getchar())); return c;
}

bool ida(int limit, Node s){
    int e = s.estimate();
    if(e == 0){
        printf("%d\n", s.step); return true;
    } else
    if(s.step + e > limit) return false; else {
        int x = s.x;
        int y = s.y;
        for(int d = 0;d < 8;++ d){
            int nx = x + D[d][0];
            int ny = y + D[d][1];
            if(1 <= nx && nx <= 5 && 1 <= ny && ny <= 5){
                Node v = s;
                swap(v.W[x][y], v.W[nx][ny]);
                v.x = nx;
                v.y = ny;
                v.step = s.step + 1;
                if(ida(limit, v)) return true;
            }
        }
    }
    return false;
}
int main(){
    int T; scanf("%d", &T);
    for(int test = 1;test <= T;++ test){
        Node s; s.step = 0;
        for(int i = 1;i <= 5;++ i)
        for(int j = 1;j <= 5;++ j){
            char c = readchar();
            if(c == '0') s.W[i][j] = 0;
            if(c == '1') s.W[i][j] = 1;
            if(c == '*') s.W[i][j] = 0, s.x = i, s.y = j;
        }
        int ans = 0;
        for(;ans <= 15;++ ans){
            if(ida(ans, s)) break;
        }
        if(ans == 16) puts("-1");
    }
    return 0;
}

后记

搜索题要练习，加油吧

标签：return,进阶,int,rest,step,搜索,ans
From： https://www.cnblogs.com/Phrvth/p/17472550.html

搜索进阶

搜索进阶

前提提要

前置知识

\(\mathcal{P}art\) 1. 设计搜索状态

\(\mathcal{P}art\) 2. 剪枝

\(\mathcal{S}olvetion\) 1. 普通搜索

\(\mathcal{S}olvetion\) 2. 剪枝进行时

\(\mathcal{Part}\) 3.双向搜索

\(\mathcal{Part}\) 4.折半搜索

\(\mathcal{Part}\) 5.迭代加深搜索

\(\mathcal{P}art\) 6. \(A^\) 和 \(Ida^\)

后记

相关文章

赞助商

阅读排行

搜索进阶

搜索进阶

前提提要

前置知识

\(\mathcal{P}art\) 1. 设计搜索状态

\(\mathcal{P}art\) 2. 剪枝

\(\mathcal{S}olvetion\) 1. 普通搜索

\(\mathcal{S}olvetion\) 2. 剪枝进行时

\(\mathcal{Part}\) 3.双向搜索

\(\mathcal{Part}\) 4.折半搜索

\(\mathcal{Part}\) 5.迭代加深搜索

\(\mathcal{P}art\) 6. \(A^*\) 和 \(Ida^*\)

后记

相关文章

赞助商

阅读排行

\(\mathcal{P}art\) 6. \(A^\) 和 \(Ida^\)