首页 > 代码库 > UVa 11212 编辑书稿（dfs+IDA*）
UVa 11212 编辑书稿（dfs+IDA*）
https://vjudge.net/problem/UVA-11212
题意：给出n个自然段组成的文章，将他们排列成1,2...，n。每次只能剪切一段连续的自然段，粘贴时按照顺序粘贴。
思路：状态空间的搜索问题。
首先介绍一下IDA*，它属于DFS，在DFS遍历的时候，设定一个深度上限maxd，当前结点n的深度为g（n），乐观估价函数为h（n），则当g（n）+h（n）>maxd时应 该剪枝。这样的算法就是IDA*。
在这道题目中，由于最多就9个数，所以最多只需要剪切8次肯定是可以完成升序排列的。所以最大深度可以从1开始一直到8，依次去寻找是否能成功。
在这题中最重要的剪枝就是考虑后继不正确的数字个数h，可以证明每次剪切时h最多减少3，因此如果3*（maxd-d）<h，则可以直接剪枝。因为此时即使一直遍历到限定深 度maxd，也无法将h的个数减为0。另外也还有许多地方可以剪枝，下面的代码中我有仔细介绍。
1 #include<iostream> 2 #include<string> 3 #include<cstring> 4 using namespace std; 5 6 int n; 7 int a[12]; 8 9 bool goal() //判断是否已达到最终状态10 {11 for (int i = 0; i < n - 1; i++)12 {13 if (a[i]>a[i + 1]) return false;14 }15 return true;16 }17 18 int h() //计算后继不正确的个数19 {20 int number = 0;21 for (int i = 0; i < n-1; i++)22 {23 if (a[i + 1] != a[i] + 1)24 number++;25 }26 if (a[n - 1] != n) number++;27 return number;28 }29 30 bool dfs(int d, int maxd)31 {32 if (3 * d + h()>3 * maxd) return false; //剪枝33 if (goal()) return true;34 int pre[12]; //保存原来序列35 int cut[12]; //保存剪切后的序列36 for (int i = 0; i < n; i++) //枚举，i为剪切起点，j为剪切终点37 {38 if (i == 0 || a[i] != a[i - 1]+1) //剪枝，不破坏连续的数字片段39 {40 for (int j = i; j < n; j++)41 {42 while (a[j + 1] == a[j] + 1) j++; //剪枝，如果一个数字片段已经连续，则不要去破坏它43 memcpy(pre, a, sizeof(a)); 44 int cnt = 0;45 for (int k = 0; k < n; k++) //保存剪切后的序号46 {47 if (k<i || k>j)48 cut[cnt++] = a[k];49 }50 for (int k = 0; k <= cnt; k++) //枚举，依次插入到第k个位置之前51 {52 int cnt2 = 0;53 for (int t = 0; t < k; t++) a[cnt2++] = cut[t];54 for (int t = i; t <= j; t++) a[cnt2++] = pre[t];55 for (int t = k; t < cnt; t++) a[cnt2++] = cut[t];56 if (dfs(d + 1, maxd)) return true; //继续深搜57 memcpy(a, pre, sizeof(pre)); //如果失败，则恢复a[]的原来的数字片段58 }59 }60 }61 }62 return false;63 }64 65 int solve()66 {67 if (goal()) return 0;68 for (int i = 1; i < 9; i++) //最多只需要进行8次dfs即可获得最终状态69 {70 if (dfs(0, i)) return i;71 }72 }73 74 int main()75 {76 //freopen("D:\\txt.txt", "r", stdin);77 int kase = 0;78 while (cin >> n && n)79 {80 memset(a, 0, sizeof(a));81 for (int i = 0; i < n; i++)82 cin >> a[i];83 int ans=solve();84 cout << "Case " << ++kase << ": " << ans << endl;85 }86 }
UVa 11212 编辑书稿（dfs+IDA*）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。