IDDFS与IDA*
IDDFS
原理
迭代加深搜索是对dfs与bfs的优化，即以bfs进行dfs，对dfs限制了深度，空间复杂度较小
当达到限制的深度d时返回。若一次搜索没有找到合法的解，就让设定的深度+1，重新从根开始
一般用于寻找最优解
过程
首先设定较小深度作为全局变量进行dfs，每进入一次将当前深度+1，当发现d大于设定的深度limit就返回。若搜索途中发现答案可以回溯，回溯时可以记录路径。若没有发现答案，就回到函数入口，增加设定深度，继续搜索
1
2
3
4
5
6
7
IDDFS(u,d)
if d>limit
return
else
for each edge (u,v)
IDDFS(v,d+1)
return应用
bfs空间不够优秀+需要寻找最优解
IDA*
即使用了迭代加深的A*算法
优点
- 不需要判重与排序，利于深度剪枝
- 空间需求少，每个深度下实际是dfs
缺点
重复搜索：即使前后两次搜索差距小，回溯时每次深度变大都要再次从头搜索
剪枝原则
当前局面的估价函数值+当前的搜索深度 > 预定义的最大搜索深度
估计函数的标准可参考：在一定范围内加大各个状态启发函数值的差别
例
P1379 八数码难题
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
#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
const int N = 2e5 + 10;
const int mod = 1e9 + 7;
const string ed = "123804765";
int dx[]={1,-1,0,0};
int dy[]={0,0,-1,1};
int mdepth;
string s;
int h(string s){
int ans = 0;
for (int i = 0; i<s.size();i++){
if (s[i]=='0') continue;
int j = ed.find(s[i]);
int r = i/3, c= i%3;
int x = j/3, y = j%3;
ans+=abs(r-x)+abs(c-y);
}
return ans;
}
bool dfs(int cd, int st){
int cnt = h(s);
if (!cnt) return 1;
if (cd+cnt>mdepth) return 0;
int pos = s.find('0');
int x = pos/3, y = pos%3;
for (int i = 0;i<4;i++){
int nx = x+dx[i], ny = y+dy[i];
if (nx<0||nx>2||ny<0||ny>2||nx*3+ny==st)continue;
swap(s[pos], s[nx*3+ny]);
if(dfs(cd+1,pos)) return 1;
swap(s[pos], s[nx*3+ny]);
}
return 0;
}
void solve() {
cin >> s;
mdepth = h(s);
while(mdepth<=27&&!dfs(0,-1)) mdepth++;
cout << mdepth;
}
int main()
{
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int tomorin=1;
//cin >> tomorin;
while (tomorin--) solve();
return 0;
}