AcWing 180 排书
一、解题思路
算法 (\(IDA*\))
\(O(560^4)\)
先考虑每一步的决策数量：
当抽取长度为 \(i\) 的一段时，有 \(n?i+1\) 种抽法，对于每种抽法，有 \(n?i\) 种放法。另外，将某一段向前移动，等价于将跳过的那段向后移动，因此每种移动方式被算了两遍，所以每个状态总共的分支数量是：\(\sum_{i=1}^{n-1}(n?i)?(n?i+1)/2=(15?14+14?13+…+2?1)/2=560\)。
考虑在四步以内解决，最多有 \(560^4\) 个状态，会超时。
可以使用\(A*\)或者\(IDA*\)来优化。
我们知道，估价函数的值是不会超过当前状态离目标状态的真实距离的，所以一旦已搜索的深度u加上估价函数的值超过了设定的深度，就不必继续搜索了。如果每次只能移动一个元素，我们可以用每个元素离最终位置的距离作为估价函数，但是现在是批量移动元素。比如1 2 3 4 5，将2 3移动到4的后面得到1 4 2 3 5，可以发现1的后继、4的后继、3的后继都改变了，而其它元素的后继未变，实际上，每次移动最多能改变三个元素的后继，所谓的后继就是这个元素的下一个元素。
我们要实现的最终状态是每个元素的后继都比当前元素多1，就说明有序了。
设估价函数为错误后继的对数，注意这里的错误后继与逆序对并不是一个概念。只要一个元素的后一个元素不是比它大1的元素，就应该记入错误后继。既然因此移动只能改变3个元素的后继，那么当前错误后继对数为cnt时，至少需要cnt / 3上取整次移动才能将序列恢复为有序。
估价函数\(f\)就等于\((cnt + 2) / 3\)，这里加上\(2\)是为了上取整。\(\left \lfloor cnt/3 \right \rfloor\)
下面要做的，就是在\(dfs\)里枚举每次取的序列的长度，起点位置以及移动到哪个位置后，比如 1 2 3 4 5，长度为1时，起点是下标为0的位置，也就是元素1，将它移动到下标为3的后面就得到了2 3 4 1 5,。长度为1的序列移动规律可能不太明显，来看个更长的序列，1 2 3 4 5 6 7 8移动2 3 4到6的后面得到1 5 6 2 3 4 7 8，可以发现只是将2 3 4右移了2个位置。这里我使用了一种常见的移动元素的策略，就是先将2 3 4反转，再将5 6反转，最后将这个5个元素所在区间的所有元素反转，即1 2 3 4 5 6 7 8到1 4 3 2 5 6 7 8到1 4 3 2 6 5 7 8到1 5 6 2 3 4 7 8，也就实现了将序列右移的目的。
另外，需要注意的是，每次\(dfs\)后要恢复数列的状态，需要用个备份数组back，而且由于back是全局变量，所以不同深度的\(dfs\)必须使用不同的back，否则就会出错，因此back定义为二维数组。
黄海注：这里我使用了一个三次翻转还原的办法，实现了回溯，也是上面一样的思路，只不过不需要使用二维数组进行备份还原了。性能更快，代码更好理解。骗你的，这个反向的三句话前两句也不太好推式子~
时间复杂度
理论上最多搜索 \(560^4\) 个状态，使用\(IDA*\)后实际搜索的状态数量很少。
二、预备知识
1、计算操作次数上限
#include
using namespace std;
int main() {
// 计算 15*14 + 14*13 + 13*12 +...+...+ 2*1
int n = 15;
int s = 0;
while (n >= 1) {
s += n * (n - 1);
n--;
}
cout << s / 2 << endl;
return 0;
}
2、向上取整
#include
using namespace std;
int main() {
// 上取整的办法
int cnt = 2;
cout << ceil((1.0 * cnt) / 3) << endl;
// 常见写法
// 公式： int((A + B - 1) / B)
// 比如：
cout << (cnt + 3 - 1) / 3 << endl;
//也就是
cout << (cnt + 2) / 3 << endl;
return 0;
}
3、数组序列右移
#include
using namespace std;
int main() {
// 将数组中一段234移动到6的后面去
// 学习一下常见的移动元素的策略,实现了将序列右移的目的。
int a[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
int s = 3;
int len = 4;
int k = 7;
//(1)将234反转
reverse(a + s, a + s + len); //参数：开始的数组索引，开始数组索引+要翻转的长度
//这是一个前闭后开的区间[)
//(2)将56反转
reverse(a + s + len, a + k + 1);
//(3)将23456反转
reverse(a + s, a + k + 1);
for (int i = 0; i < 10; i++) cout << a[i] << " ";
cout << endl;
//输出：0 1 5 6 2 3 4 7 8
//与预期结果一致
//尝试再反转回来,这个反转回来真是费了我一小时的时间，真是笨啊
// 0 1 5 6 2 3 4 7 8
// 0 1 6 5 2 3 4 7 8 (1)
// 0 1 6 5 4 3 2 7 8 (2)
// 0 1 2 3 4 5 6 7 8 (3)
// int s = 2, len = 3,k = 6;
// k s+len
int x = k - s - len + 1;
reverse(a + s, a + s + x);
reverse(a + s + x, a + k + 1);
reverse(a + s, a + k + 1);
for (int i = 0; i < 10; i++) cout << a[i] << " ";
cout << endl;
return 0;
}
三、IDA*
1、数组翻转+反翻转
#include
using namespace std;
const int N = 16; // 1≤n≤15
int a[N]; //记录书的排列情况
int n; //书的数量
int depth; //最少的操作步数
//估值函数
//这个函数也是在计算不同状态时的估价函数的，不要被它表象蒙蔽！
//这个函数中a数组是在被dfs不断修改的，所以也是在实时计算未来的最少步数
//这个IDA*的估价函数，本质上与A*的是一样的意思，都是在每个状态下可以获取到最短的步数
int f() {
int cnt = 0;
//计算前后非+1递增的 错误后继的对数
for (int i = 0; i < n - 1; i++)
if (a[i] + 1 != a[i + 1]) cnt++;
//每次移动，最多能解决三个错误后继，如果现在有cnt个错误后继，最少需要 ?cnt/3?次操作
return (cnt + 2) / 3;
}
// u:正在操作的步数
bool dfs(int u) {
int t = f(); //计算估价函数
//剪枝掉预期不符的
if (u + t > depth) return false; //如果迭代加深的深度达到，没有找到结果，返回
if (!t) return true; //已经没有不合格的，返回完成
for (int len = 1; len < n; len++) { //枚举抽取长度
// 枚举每次抽取的开始索引下标,注意一下开始索引+长度不能超过n-1,即> T;
while (T--) {
cin >> n; //表示书的数量
for (int i = 0; i < n; i++) cin >> a[i];
//最少操作次数,因为可能书本来天生就是有序，即每本书n后面都是n+1，完全合格的顺序，这时不用调整，最少操作数为0
//需要从0开始查询最少操作次数
depth = 0;
while (depth < 5 && !dfs(0)) depth++; //有层数限制的dfs，这是迭代加深
if (depth >= 5) //最少操作次数大于或等于5次
cout << "5 or more" << endl;
else
cout << depth << endl; //最少操作次数
}
return 0;
}
2、数组翻转+备份还原
#include
using namespace std;
const int N = 16; // 1≤n≤15
int a[N]; //记录书的排列情况
int n; //书的数量
int depth; //最少的操作步数
/*
每次dfs后要恢复数列的状态，需要用个备份数组back，而且由于back是全局变量，
所以不同深度的dfs必须使用不同的back，否则就会出错，因此back定义为二维数组
*/
int back[5][N];
//估值函数
//这个函数也是在计算不同状态时的估价函数的，不要被它表象蒙蔽！
//这个函数中a数组是在被dfs不断修改的，所以也是在实时计算未来的最少步数
//这个IDA*的估价函数，本质上与A*的是一样的意思，都是在每个状态下可以获取到最短的步数
int f() {
int cnt = 0;
//计算前后非+1递增的 错误后继的对数
for (int i = 0; i < n - 1; i++)
if (a[i] + 1 != a[i + 1]) cnt++;
//每次移动，最多能解决三个错误后继，如果现在有cnt个错误后继，最少需要 ?cnt/3?次操作
return (cnt + 2) / 3;
}
// u:正在操作的步数
bool dfs(int u) {
int t = f(); //计算估价函数
//剪枝掉预期不符的
if (u + t > depth) return false; //如果迭代加深的深度达到，没有找到结果，返回
if (!t) return true; //已经没有不合格的，返回完成
for (int len = 1; len < n; len++) { //枚举抽取长度
// 枚举每次抽取的开始索引下标,注意一下开始索引+长度不能超过n-1,即> T;
while (T--) {
cin >> n; //表示书的数量
for (int i = 0; i < n; i++) cin >> a[i];
//最少操作次数,因为可能书本来天生就是有序，即每本书n后面都是n+1，完全合格的顺序，这时不用调整，最少操作数为0
//需要从0开始查询最少操作次数
depth = 0;
while (depth < 5 && !dfs(0)) depth++; //有层数限制的dfs，这是迭代加深
if (depth >= 5) //最少操作次数大于或等于5次
cout << "5 or more" << endl;
else
cout << depth << endl; //最少操作次数
}
return 0;
}
四、A*(优化版本bfs)
#include
using namespace std;
typedef unsigned long long ULL; //自动溢出的ULL，看来是要计算整数数组的HASH值了
const int INF = 0x3f3f3f3f;
const int B = 17; // 17进制，用于HASH计算，这是大于15的第一个质数
const int N = 15;
int n;
//用于检测一个状态是否已经访问过了
unordered_set b;
struct Node {
int v[N]; //当前的状态
int step; //步数
int f; //当前估计值（答案）
//重载小于号
bool operator<(const Node &x) const {
return x.f < f;
}
} x;
//优先队列(注意一下这个依赖关系，没有Node，就没有q,有先后)
priority_queue q;
//检测是否到了目标状态
bool check(Node x) {
for (int i = 0; i < n; i++)
if (x.v[i] != i + 1) return false;
return true;
}
// 计算数组状态的hash值
ULL get(Node x) {
ULL res = 0;
for (int i = 0; i < n; i++) res = res * B + x.v[i];
return res;
}
//估值函数
int f(Node x) {
int res = 0;
for (int i = 1; i < n; i++)
if (x.v[i] - 1 != x.v[i - 1]) res++;
return (res + 2) / 3;
}
// AStar
int bfs() {
while (q.size()) {
//取出当前状态
Node u = q.top();
q.pop();
if (u.f >= 5) return INF; //当前状态无法在5步之内到达终点，返回无结果
if (check(u)) return u.step; //如果检查成功，返回当前步数
for (int len = 1; len < n; len++) { //枚举长度
// 枚举每次抽取的开始索引下标,注意一下开始索引+长度不能超过n-1,即> T;
while (T--) {
//清空Hash表
b.clear();
//清空优先队列,清空优先队列的一个小技巧
q = {};
cin >> n;
//初始状态入队列
for (int i = 0; i < n; i++) cin >> x.v[i]; //当前的数组状态
x.step = 0; //步数为0
x.f = f(x); //估值
q.push(x); //对象入优化队列
b.insert(get(x)); //记录此状态已使用
int res = bfs(); //返回搜索结果
if (res >= 5)
puts("5 or more");
else
cout << res << endl;
}
return 0;
}