学习笔记_ 迭代加深搜索... [搜索, 迭代加深搜索, 优化, 暴力]

找不到就回来吧

不必一条路到黑

懵逼的 题目

传送至 Vijos

扯淡的 题解

迭代加深搜索…一般就是在找可行解或者[首先要求层数尽量少]的最优解中使用…为什么是首先要求层数尽量少捏…因为迭代加深的性质决定了他找到的第一个解就是最浅的解…(是不是有点像BFS?)

迭代加深的具体流程是酱紫的…

  1. 定一个小目标(MAXD)先赚他一个亿, 在几层之内找到解…
  2. DFS: 如果搜索树的高度已经超过了MAXD, 那么返回, 也就是说搜索完了整个搜索树内MAXD深度以上的节点
  3. 如果找到解, 结束程序, 否则增大深度MAXD(因为当前深度找不到解说明解一定在更深的地方), 返回 2

现在讲一讲迭代加深好处都有啥谁说对了金坷垃就给他

  1. 和BFS相比

和BFS不同的一点就是空间占用小…在有些题中BFS可能还没等扩展完一层节点就已经爆空间了_(:з」∠)_…而迭代加深并不需要扩展完整个一层就可以找搜索树的下一层(DFS特性)
就拿埃及分数来说…BFS会扩展完一层节点才去扩展下一层, 而这个”一层节点”实际上是扩展不完的(你要扩展整数集合啊)

这里写图片描述


  1. 和DFS相比

既然BFS不行那DFS呐…DFS爆时间…如果解的位置比较刁钻, 在搜索树的”后面”而深度又比较浅, DFS会沿着搜索树上的某一条路径按照顺序扩展, 直到找到可行解, 所以”后面”的解可能没能扩展就T飞了…

这里写图片描述


  1. 迭代

我承认我图特丑…
迭代的好处就是不用扩展完每一层节点(DFS的实现方式), 而且又不用担心解位置的问题(逐层扩展)
但有细节要注意, 在当前深度限制内找到一个可行解的时候不要立刻返回, 当前的深度可能还有更优解, 所以这就是为什么迭代搜索要求[深度浅]是判断最优解的第一条件…

这里写图片描述


Emmmmmm…那埃及分数很显然是个迭代…
有几个细节…

  • 剪枝: 迭代的效率和搜索树的宽度关系挺大…如果当前的a / b减去MAXD1 / i都大于0, 那就没有扩展的必要了…
  • 别剪成巨斧砍大树: 不能因为a / b - 1 / i的分母(约分后)大于当前答案里的最大数就退出…再减几个1 / i可能分母就可以约分而变小了…

没了

沙茶的 代码

改了1 Day…没了…
发现我不会搜索…Emmmmmm….

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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#define pii pair<int, int>
#define MAXN (1000 + 5)
#define INF (0x7ffffff)
#define max(a, b) ((a) > (b) ? (a) : (b))
#define min(a, b) ((a) < (b) ? (a) : (b))
using namespace std;
int a, b;
int ans = INF;
int minl = INF;
int MAXD;
int out[MAXN];
int dout[MAXN];
bool ok = false;
void dfs(int, int, int, int, int);
pii js(int, int, int);
int gcd(int, int);
void solve();
int main()
{
scanf("%d%d", &a, &b);
int r = gcd(a, b);
a /= r, b /= r;
solve();
for (int i = 1; i <= ans; i++)
{
printf("%d ", out[i]);
}
return 0;
}
void dfs(int dans, int last, int da, int db)
{
// printf("%d / %d\n", da, db);
if (da == 1 && db > last)
{
dout[dans] = db;
if (dans < ans)
{
ans = dans;
memcpy(out, dout, MAXN - 1);
ok = true;
}
else if (dans == ans && db < out[ans])
memcpy(out, dout, MAXN - 1);
}
else if (dans > MAXD)
return ;
else
{
for (int i = last + 1; ((double)da / db / (1.0 / i)) - 1 <= MAXD; i++)
{
pii dq = js(da, db, i);
// if (ans < INF && dq.second > out[ans])
// continue;
if (dq.first != -1/* && dq.second < MAXN*/)
{
dout[dans] = i;
dfs(dans + 1, i, dq.first, dq.second);
}
}
}
}
int gcd(int a, int b)
{
return ((b == 0) ? (a) : (gcd(b, a % b)));
}
// return a fraction: (da / db - 1 / x)
/*
t = x / gcd;
da *= gcd
db *= gcd

*/
pii js(int da, int db, int x)
{
int r = gcd(db, x);
int t = x / r;
da *= t;
da -= db / r;
db *= t;
if (da < 0)
return make_pair(-1, 0);
r = gcd(da, db);
da /= r;
db /= r;
return make_pair(da, db);
}
void solve()
{
for (; !ok; MAXD++)
{
dfs(1, 1, a, b);
}
}

/*
19 45
ans: 5 6 18
*/

By 月考好像翻盘的(Flag?) Cansult