IDDFS
使用场景：
- 搜索树非常大而答案的深度较浅，一般在 \(20\) 以内，且 dfs 会 TLE，bfs 会 MLE。
算法原理：
-
以 dfs 的形式搜索；
-
设定搜索的深度限制 \(dep\)；
-
dfs 深度不能超过 \(dep\)，且要恰好遍历所有 \(dep\) 的状态；
-
若在 \(dep\) 层没有找到答案，\(dep+1 \to dep\)，重新 DFS。
剪枝：
-
最优性剪枝：考虑将选择序列排序，优先选最大 / 最小。
-
可行性剪枝：按照最优策略选择时如果还不能在剩下的层数之内达到目标就剪枝。
UVA529
观察到此题的答案序列形如 Fib 数列，
而众所周知这玩意增长极快，
因此答案绝对不会过大，考虑 IDDFS。
朴素搜索是简单的，但 \(n\) 达到 \(10^4\) 规模，因此考虑剪枝。
最优性剪枝：从大到小选数，一遍更快地凑近 \(n\)。
可行性剪枝：
最快的正常方式显然是不断选择两个当前的数然后求和。
（得益于题目的限制，当前的数即为最大的）
设当前层数为 \(cur\)，深度限制为 \(dep\)，当前的数为 \(x\)（定义下文同），
则若 \(2^{dep-cur} \times x<n\) 则直接剪枝即可。
code
//
// UVA529.cpp
//
//
// Created by _XOFqwq on 2024/10/5.
//
#include<bits/stdc++.h>
using namespace std;
const int N=1e4+5;
int n,ans[N],dep;
bool dfs(int cur){
if (cur==dep) {
return ans[cur]==n;
}
if (ans[cur]*(1<<(dep-cur))<n) {
return 0;
}
for (int i=cur; i>=1; i--) {
for (int j=i; j>=1; j--) {
if (ans[i]+ans[j]<=n&&ans[i]+ans[j]>ans[cur]) {
ans[cur+1]=ans[i]+ans[j];
if (dfs(cur+1)) {
return 1;
}
ans[cur+1]=0;
}
}
}
return 0;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
while (cin>>n&&n) {
ans[1]=1;
for (dep=1; !dfs(1); dep++);
for (int i=1; i<dep; i++) {
cout<<ans[i]<<' ';
}
cout<<ans[dep]<<'\n';
}
return 0;
}
总结：
-
对于看上去像搜索但数据较大的题目时，考虑 IDDFS + 剪枝。可以大胆猜想答案不会很大。
-
剪枝时考虑最优情况是怎样，然后就能推导出可行性剪枝。
-
写 dfs 函数时，注意函数末尾的
return 0。
UVA1374
根据乘方的性质，\(x \to x^n\) 的过程实质即为指数的加减。
考虑到操作序列仍形如 Fib 数列，考虑 IDDFS。
最优性剪枝：从大到小选即可。
可行性剪枝：设前面选的最大指数为 \(x\)，则若 \(2^{dep-cur} \times x<n\) 就剪枝。
细节：
枚举时无需枚举两个数，仅需枚举一个然后和当前数参与运算。
这是因为如果当前数不参与运算，它完全可以现在不被计算出来。
而上一题需要枚举两个数是因为题目有递增的限制，
当前数即使不参与运算也要计算出来以构造下一个数。
code
//
// UVA1374.cpp
//
//
// Created by _XOFqwq on 2024/10/5.
//
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e3+5;
int n,dep,ans[N];
bool dfs(int cur){
if (cur==dep) {
return ans[cur]==n;
}
int mx=-1e18;
for (int i=0; i<=cur; i++) {
mx=max(mx,ans[cur]);
}
if (mx*(1<<(dep-cur))<n) {
return 0;
}
for (int i=cur; i>=0; i--) {
ans[cur+1]=ans[cur]+ans[i];
if (dfs(cur+1)) {
return 1;
}
ans[cur+1]=0;
if (ans[cur]-ans[i]>0) {
ans[cur+1]=ans[cur]-ans[i];
if (dfs(cur+1)) {
return 1;
}
ans[cur+1]=0;
}
}
return 0;
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
while (cin>>n&&n) {
ans[0]=1;
for (dep=0; !dfs(0); dep++);
cout<<dep<<'\n';
}
return 0;
}
P10489
个人认为，这题只要把题读懂了就不难想出。
形式化题意：
给定 \(n\) 个数（可重），求最少的等差数列的个数，使得它们覆盖每个数恰好 \(1\) 次，且每个等差数列覆盖至少 \(2\) 个数。
注意到答案 \(\le 17\)，考虑 IDDFS。
维护 \(cnt_i\) 表示第 \(i\) 个数的出现次数，先预处理所有合法的等差数列，然后枚举每个等差数列暴力覆盖即可。
最优性剪枝：按长度从大到小选择。
可行性剪枝：当不停地选择当前的（即最长的）等差数列都无法完全覆盖时剪枝。
code
//
// P10489.cpp
//
//
// Created by _XOFqwq on 2024/10/5.
//
#include <bits/stdc++.h>
using namespace std;
const int N=3e3+5;
int n,tot,dep;
int cnt[N];
struct Seq {
int x,d,len;
}seq[N];
bool cmp(Seq a,Seq b){
return a.len>b.len;
}
bool check(int x,int d){
for (int i=x; i<60; i+=d) {
if (!cnt[i]) {
return 0;
}
}
return 1;
}
bool dfs(int cur,int pos,int sum){
if (cur==dep) {
return sum==n;
}
if (sum+seq[pos].len*(dep-cur)<n) {
return 0;
}
for (int i=pos; i<=tot; i++) {
if (check(seq[i].x,seq[i].d)) {
for (int j=seq[i].x; j<60; j+=seq[i].d) {
cnt[j]--;
}
if (dfs(cur+1,i,sum+seq[i].len)) {
return 1;
}
for (int j=seq[i].x; j<60; j+=seq[i].d) {
cnt[j]++;
}
}
}
return 0;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cin>>n;
for (int i=1,x; i<=n; i++) {
cin>>x;
cnt[x]++;
}
for (int i=0; i<60; i++) {
for (int j=i+1; i+j<60; j++) {
if (check(i,j)) {
seq[++tot]={i,j,(59-i)/j+1};
}
}
}
sort(seq+1,seq+tot+1,cmp);
for (dep=0; !dfs(0,1,0); dep++);
cout<<dep;
return 0;
}
总结：
- 对于晦涩难懂的题目，首先提炼出形式化题意。
IDA*
可以看作是带有估价函数的 IDDFS。
而估价函数可以看作是复杂一点的可行性剪枝。
P2324
根据题意，答案一定很小，考虑 IDA*。
首先有一个很重要的转化：将骑士的移动看作空位的移动。这样就只有一个东西在动了。
考虑设计可行性剪枝。容易发现空位每动一次就会复原至多一个位置，最后一步至多复原两个位置。
于是设计估价函数 \(h\) 检查有多少个位置没有被复原，设有 \(x\) 个，则 \(dep-cur+1<x\) 时就可以剪枝了。
code
//
// P2324-2.cpp
//
//
// Created by _XOFqwq on 2024/10/5.
//
#include <bits/stdc++.h>
using namespace std;
const int N=5;
const int dx[]={-1,1,-1,1,-2,2,-2,2};
const int dy[]={2,2,-2,-2,1,1,-1,-1};
const char tar[N][N]=
{
{'1','1','1','1','1'},
{'0','1','1','1','1'},
{'0','0','*','1','1'},
{'0','0','0','0','1'},
{'0','0','0','0','0'}
};
int t,dep;
char a[N][N];
int h(){
int res=0;
for (int i=0; i<5; i++) {
for (int j=0; j<5; j++) {
res+=a[i][j]!=tar[i][j];
}
}
return res;
}
bool dfs(int cur,int x,int y){
int cost=h();
if (!cost) {
return 1;
}
if (dep-cur+1<cost) {
return 0;
}
for (int i=0; i<8; i++) {
int xx=x+dx[i],yy=y+dy[i];
if (xx>=0&&xx<5&&yy>=0&&yy<5) {
swap(a[x][y],a[xx][yy]);
if (dfs(cur+1,xx,yy)) {
return 1;
}
swap(a[x][y],a[xx][yy]);
}
}
return 0;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cin>>t;
while (t--) {
int sx=-1,sy=-1;
for (int i=0; i<5; i++) {
for (int j=0; j<5; j++) {
cin>>a[i][j];
if (a[i][j]=='*') {
sx=i,sy=j;
}
}
}
for (dep=0; dep<=15&&!dfs(0,sx,sy); dep++);
cout<<(dep>15?-1:dep)<<'\n';
}
return 0;
}
总结：
- 这个转化是棋盘搜索类问题的通用套路，需要牢记。
P10488
根据题意，答案一定很小，考虑 IDA*。
考虑可行性剪枝。发现答案序列一定是一个公差为 \(1\) 的等差数列，因此判断有多少对相邻的数差不为 \(1\) 就说明最少要操作多少次。设最少要操作 \(x\) 次，则 \(dep-cur<x\) 时就可以剪枝了。
（注意，这里不能计算有多少个数不等于其下标，因为即使某个数在相应位置上，当它前面的数和它差不为 \(1\)，则也需要操作）
然后注意一下状态更新时不要写复杂了即可。具体见代码。
code
//
// P10488-3.cpp
//
//
// Created by _XOFqwq on 2024/10/5.
//
#include <bits/stdc++.h>
using namespace std;
const int N=31;
int T,n,dep;
int a[N],t[6][N];
int h(){
int res=0;
for (int i=1; i<n; i++) {
res+=a[i]+1!=a[i+1];
}
return res;
}
void fuck_that_bitch(int cur,int l,int r,int p){
int pos=l;
for (int i=r+1; i<=p; i++,pos++) {
a[pos]=t[cur][i];
}
for (int i=l; i<=r; i++,pos++) {
a[pos]=t[cur][i];
}
}
bool dfs(int cur){
int cost=h();
if (!cost) {
return 1;
}
if (3*(dep-cur)<cost) {
return 0;
}
for (int i=1; i<=n; i++) {
for (int j=i; j<=n; j++) {
for (int k=j+1; k<=n; k++) {
memcpy(t[cur],a,sizeof a);
fuck_that_bitch(cur,i,j,k);
if (dfs(cur+1)) {
return 1;
}
memcpy(a,t[cur],sizeof a);
}
}
}
return 0;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cin>>T;
while (T--) {
cin>>n;
for (int i=1; i<=n; i++) {
cin>>a[i];
}
for (dep=0; dep<5&&!dfs(0); dep++);
if (dep>=5) {
cout<<"5 or more\n";
} else {
cout<<dep<<'\n';
}
}
return 0;
}
总结：
- 状态更新与剪枝是 IDDFS / IDA* 最重要的部分。前者力求简洁，而后者则需要仔细思考其正确性。
UVA1505
根据题面 PDF，
答案一定很小，考虑 IDA*。
考虑可行性剪枝。每次操作最多消除一种颜色，因此统计除了左上角联通块外还有多少种不同的颜色。设有 \(x\) 种，则 \(dep-cur<x\) 时就可以剪枝了。
考虑状态更新。每次从左上角联通块的边界开始染色即可，需要单独写另一个 dfs，并且需要在一开始预先染色左上角的联通块。
code
//
// UVA1505-2.cpp
//
//
// Created by _XOFqwq on 2024/10/5.
//
#include<bits/stdc++.h>
using namespace std;
const int N=10;
const int dx[]={0,1,0,-1};
const int dy[]={1,0,-1,0};
int n,dep;
int a[N][N];
int cnt[N],vis[N][N];
int h(){
memset(cnt,0,sizeof cnt);
for (int i=1; i<=n; i++) {
for (int j=1; j<=n; j++) {
if (vis[i][j]!=1) {
cnt[a[i][j]]++;
}
}
}
int res=0;
for (int i=0; i<=5; i++) {
res+=cnt[i]>0;
}
return res;
}
void erect(int x,int y,int c){
vis[x][y]=1;
for (int i=0; i<4; i++) {
int xx=x+dx[i],yy=y+dy[i];
if (xx>=1&&xx<=n&&yy>=1&&yy<=n&&vis[xx][yy]!=1) {
vis[xx][yy]=2;
if (a[xx][yy]==c) {
erect(xx,yy,c);
}
}
}
}
bool dfs(int cur){
int cost=h();
if (!cost) {
return 1;
}
if (dep-cur<cost) {
return 0;
}
int t[N][N];
memcpy(t,vis,sizeof t);
for (int i=0; i<=5; i++) {
bool f=0;
for (int x=1; x<=n; x++) {
for (int y=1; y<=n; y++) {
if (a[x][y]==i&&vis[x][y]==2) {
erect(x,y,i);
f=1;
}
}
}
if (f&&dfs(cur+1)) {
return 1;
}
memcpy(vis,t,sizeof vis);
}
return 0;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
while (cin>>n&&n) {
memset(vis,0,sizeof vis);
for (int i=1; i<=n; i++) {
for (int j=1; j<=n; j++) {
cin>>a[i][j];
}
}
erect(1,1,a[1][1]);
for (dep=0; !dfs(0); dep++);
cout<<dep<<'\n';
}
return 0;
}