迭代深搜简单来说就是限制深度的深搜，这样就可以避免像广搜一样占用大量空间，又可以像广搜找到最佳的路径。
两道例题
1.埃及分数
#include<cstdio>
#include<set>
#include<cstring>
using namespace std;
const int N = 10;
typedef long long LL;
set<LL>s;
LL now[N], pre[N];
bool flag;
LL gcd(LL a, LL b) {
return b ? gcd(b, a%b) : a;
}
bool good(int k) {//比较出较好的结果
for (int i = k; i>0; i--) {
if (now[i] != pre[i]) {
return pre[i] == 0 || now[i] < pre[i];
}
}
return 0;
}
void dfs(LL a, LL b, int k, int dep) {
if (k == dep) {
if (b%a ||b/a<=now[k-1]||s.count(b/a)) {
return;
}
now[k] = b / a;
if (!flag || good(k)) {
memcpy(pre, now, sizeof(now));
}
flag = 1;
return;
}
LL j = b / a;
if (j <= now[k - 1]) {
j = now[k - 1] + 1;
}
LL t = (dep - k + 1)*b / a;//如果不满足，那么永远不可能有结果，所以就可以限制上限
for (LL i = j; i <= t; i++) {
if (s.count(i)) {
continue;
}
now[k] = i;
LL m = gcd(a*i - b, b*i);
dfs((a*i - b) / m, b*i / m, k + 1, dep);
}
}
void fun(LL a, LL b) {
now[0] = 1;
for (int dep = 2; dep <= N; dep++) {
dfs(a, b, 1, dep);
if (flag) {
for (int i = 1; i <= dep; i++) {
if (i != dep) {
printf("1/%lld+", pre[i]);
}
else {
printf("1/%lld", pre[i]);
}
}
printf("\n");
return;
}
}
}
int main() {
int T;
scanf("%d", &T);
for (int i = 1; i <= T; i++) {
memset(now, 0, sizeof(now));
memset(pre, 0, sizeof(pre));
s.clear();
LL a, b;
int k, t;
flag = 0;
scanf("%lld%lld%d", &a, &b, &k);
while (k--) {
scanf("%d", &t);
s.insert(t);
}
printf("Case %d: %lld/%lld=", i, a, b);
fun(a, b);
}
return 0;
}2.＃
这道题没有过oj，就纯过了样例，但重要的是理解迭代深搜的思想。
#include<cstdio>
#include<cstring>
#include<vector>
#include<iostream>
using namespace std;
int arr[8][8];
int num;
vector<char> vec;
char name(int x, int y, int dir) {
if (y) {
if (dir == -1) {
if (y == 2) {
return 'A';
}
else {
return 'B';
}
}
else if (dir == 1) {
if (y == 2) {
return 'F';
}
else {
return 'E';
}
}
}
else if (x) {
if (dir == 1) {
if (x == 2) {
return 'C';
}
else {
return 'D';
}
}
else if (dir == -1) {
if (x == 2) {
return 'H';
}
else {
return 'G';
}
}
}
}
int judge() {
int x = arr[2][2];
for (int j = 2; j <= 4; j += 2) {
for (int i = 2; i <= 4; i++) {
if (arr[j][i] != x) {
return 0;
}
}
}
for (int i = 2; i <= 4; i += 2) {
if (arr[3][i] != x) {
return 0;
}
}
return x;
}
void move(int x, int y, int dir) {
if (y != 0) {
if (dir<0) {
int t = arr[6][y];
for (int i = 0; i<6; i++) {
arr[(i + dir + 7) % 7][y] = arr[i][y];
}
arr[5][y] = t;
}
else if (dir>0) {
int t = arr[0][y];
for (int i = 6; i>0; i--) {
arr[(i + dir + 7) % 7][y] = arr[i][y];
}
arr[1][y] = t;
}
}
else if (x != 0) {
if (dir<0) {
int t = arr[x][6];
for (int i = 0; i<6; i++) {
arr[x][(i + dir + 7) % 7] = arr[x][i];
}
arr[x][5] = t;
}
else if (dir>0) {
int t = arr[x][0];
for (int i = 6; i>0; i--) {
arr[x][(i + dir + 7) % 7] = arr[x][i];
}
arr[x][1] = t;
}
}
}
void dfs(int k, int dep) {
if (k == dep) {
int j = judge();
if (j) {
num = j;
return;
}
return;
}
for (int i = 2; i <= 4; i += 2) {
if (num != -1) {
return;
}
move(0, i, -1);
vec.push_back(name(0, i, -1));
dfs(k + 1, dep);
if (num != -1) {
return;
}
vec.pop_back();
move(0, i, 1);
}
for (int i = 2; i <= 4; i += 2) {
if (num != -1) {
return;
}
move(i, 0, 1);
vec.push_back(name(i, 0, 1));
dfs(k + 1, dep);
if (num != -1) {
return;
}
vec.pop_back();
move(i, 0, -1);
}
for (int i = 2; i <= 4; i += 2) {
if (num != -1) {
return;
}
move(0, i, 1);
vec.push_back(name(0, i, 1));
dfs(k + 1, dep);
if (num != -1) {
return;
}
vec.pop_back();
move(0, i, -1);
}
for (int i = 2; i <= 4; i += 2) {
if (num != -1) {
return;
}
move(i, 0, -1);
vec.push_back(name(i, 0, -1));
dfs(k + 1, dep);
if (num != -1) {
return;
}
vec.pop_back();
move(i, 0, 1);
}
}
void iinput(int i) {
int t;
for (int j = 2; j <= 4; j += 2) {
scanf("%d", &t);
arr[i][j] = t;
}
}
void input() {
int t;
scanf("%d", &t);
arr[0][5] = t;
iinput(1);
for (int i = 0; i<7; i++) {
scanf("%d", &t);
arr[2][i] = t;
}
iinput(3);
for (int i = 0; i<7; i++) {
scanf("%d", &t);
arr[4][i] = t;
}
iinput(5);
iinput(6);
}
int main() {
int t;
while (scanf("%d", &t) != EOF) {
memset(arr, 0, sizeof(arr));
arr[0][3] = t;
num = -1;
vec.clear();
input();
for (int dep = 1; dep <= 10; dep++) {
dfs(0, dep);
if (num != -1) {
break;
}
vec.clear();
}
for (int i = 0; i<vec.size(); i++) {
cout << vec[i];
}
cout << endl << num << endl;
}
return 0;
}