文章目录
前言
一、IDA*
二、例题，代码
AcWing 180. 排书
本题解析
AC代码
AcWing 181. 回转游戏
本题解析
AC代码
三、时间复杂度
前言
复习acwing算法提高课的内容，本篇为讲解算法：IDA*，关于时间复杂度：目前博主不太会计算，先鸽了，日后一定补上。
一、IDA*
和A*算法一样，IDA*算法也是利用贪心的思想进行对dfs的优化，其算法思想和A*算法相似，都是利用一个估价函数去进行优化，A*算法见博客：A*。
二、例题，代码
AcWing 180. 排书
本题链接：AcWing 180. 排书
本博客提供本题截图：
本题解析
我们选取的估价函数是有多少个不符合q[i + 1] == q[i] + 1的项，我们知道，在挪动一坨书的时候，我们最多可以改变三组书的前后关系：
所以我们低于有这么cnt组不符合题意的项，我们最小可以通过cnt / 3向上取正的次数去更正它们，我们知道C++中的取整方式是向下取整，所以我们可以通过(cnt + 2) / 3去计算估价函数
AC代码
#include <cstring> #include <iostream> #include <algorithm> using namespace std; const int N = 15; int n; int q[N]; int w[5][N]; int f() { int cnt = 0; for (int i = 0; i + 1 < n; i ++ ) if (q[i + 1] != q[i] + 1) cnt ++ ; return (cnt + 2) / 3; } bool check() { for (int i = 0; i + 1 < n; i ++ ) if (q[i + 1] != q[i] + 1) return false; return true; } bool dfs(int depth, int max_depth) { if (depth + f() > max_depth) return false; if (check()) return true; for (int len = 1; len <= n; len ++ ) //遍历长度 for (int l = 0; l + len - 1 < n; l ++ ) //交换点 { int r = l + len - 1; for (int k = r + 1; k < n; k ++ ) { memcpy(w[depth], q, sizeof q);//因为要恢复现场，所以得备份一下 int x, y; for (x = r + 1, y = l; x <= k; x ++, y ++ ) q[y] = w[depth][x]; for (x = l; x <= r; x ++, y ++ ) q[y] = w[depth][x]; if (dfs(depth + 1, max_depth)) return true; memcpy(q, w[depth], sizeof q); } } return false; } int main() { int T; cin >> T; while (T -- ) { cin >> n; for (int i = 0; i < n; i ++ ) cin >> q[i]; int depth = 0; while (depth < 5 && !dfs(0, depth)) depth ++ ; if (depth >= 5) puts("5 or more"); else cout << depth << endl; } return 0; }
AcWing 181. 回转游戏
本题链接：AcWing 181. 回转游戏
本博客提供本题截图：
本题解析
op数组存储的是那8个操作对应的坐标，cnter数组存储的是中间8个数的坐标，opposite数组存储的是8个操作的逆操作的坐标，本题的估价函数f是计算中间的8个数出现次数，比如我们8个数中有6个数都是1，那么我们的最小操作次数就是2，即把2个非1的数变成两个1，当我们的估价函数返回值为0的时候，证明不需要任何操作了，如何保证字典序：按照ABCD的操作顺序去改变这个#，operation操作函数：执行第x个操作，操作均为把除了第0位，其余全部向前移动一个位置，然后第0位移动至最后，剪枝部分：记录上一次的操作，本次操作避免枚举上一次的逆操作。我们的dfs函数传递三个值：当前层数，最大层数，上一步操作。注意本题的回复现场，即执行一下该操作的逆操作（利用opposite）
AC代码
#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; const int N = 24; int q[N]; int op[8][7] = { {0, 2, 6, 11, 15, 20, 22}, {1, 3, 8, 12, 17, 21, 23}, {10, 9, 8, 7, 6, 5, 4}, {19, 18, 17, 16, 15, 14, 13}, {23, 21, 17, 12, 8, 3, 1}, {22, 20, 15, 11, 6, 2, 0}, {13, 14, 15, 16, 17, 18, 19}, {4, 5, 6, 7, 8, 9, 10} }; int center[8] = {6, 7, 8, 11, 12, 15, 16, 17}; int opposite[8] = {5, 4, 7, 6, 1, 0, 3, 2}; int path[100]; int f() { int sum[4]; memset(sum, 0, sizeof sum); for (int i = 0; i < 8; i ++ ) sum[q[center[i]]] ++ ; int s = 0; for (int i = 1; i <= 3; i ++ ) s = max(s, sum[i]); return 8 - s; } void operation(int x) { int t = q[op[x][0]]; for (int i = 0; i < 6; i ++ ) q[op[x][i]] = q[op[x][i + 1]]; q[op[x][6]] = t; } bool dfs(int depth, int max_depth, int last) { if (depth + f() > max_depth) return false; if (!f()) return true; for (int i = 0; i < 8; i ++ ) { if (opposite[i] == last) continue; operation(i); path[depth] = i; if (dfs(depth + 1, max_depth, i)) return true; operation(opposite[i]); } return false; } int main() { while (scanf("%d", &q[0]), q[0]) { for (int i = 1; i < N; i ++ ) scanf("%d", &q[i]); int depth = 0; while (!dfs(0, depth, -1)) depth ++ ; if (!depth) printf("No moves needed"); for (int i = 0; i < depth; i ++ ) printf("%c", 'A' + path[i]); printf("\n%d\n", q[6]); } return 0; }
三、时间复杂度
关于IDA*的时间复杂度以及证明，后续会给出详细的说明以及证明过程，目前先鸽了。
