IDA*——AcWing 180. 排书

IDA*

定义

IDA*（Iterative Deepening A*）是一种结合了深度优先搜索（DFS）的递归深度限制特性和A搜索的启发式估价函数的搜索算法。它主要用于解决启发式搜索问题，尤其是当搜索空间很大或者搜索成本不确定时。

IDA* 是一种最佳优先搜索算法，其基本思想是在深度优先搜索的基础上，通过逐步增加搜索深度并结合A*算法中的估价函数f(n)=g(n)+h(n)，来找到从初始节点到目标节点的最短路径。其中，g(n)是从初始节点到当前节点的实际代价，h(n)是从当前节点到目标节点的启发式估计代价。

运用情况

1. 内存限制: IDA特别适合那些内存有限制的环境，因为它不像A那样需要维护一个开放列表（open list），而是采用递归的方式逐步深入搜索。
2. 未知或变化的成本: 当搜索空间中节点的移动成本不是预先完全已知或可能变化时，IDA*通过逐步探索来适应这种不确定性。
3. 最优解搜索: 当寻找问题的最优解而非任一解时，IDA*通过其最佳优先的特性保证找到的是从起点到终点的最短路径。
4. 大型或无限状态空间: 对于状态空间非常大或理论上无限的情况，IDA*通过逐步加深搜索深度来逐步逼近解，避免了一次性需要大量内存来存储整个搜索树的问题。

注意事项

1. 启发式函数的选择: h(n)的选择至关重要，它需要保证不大于实际的最小代价，否则算法可能不会终止。理想的h(n)接近实际成本但又易于计算。
2. 深度限制: 初始时设置一个合理的深度限制，随着搜索的进行逐渐增加，直到找到解或达到某个预设的深度上限。
3. 效率: 虽然IDA避免了A中的开放列表维护，但如果启发式不够好或搜索空间极大，递归调用可能会导致大量的重复计算和较慢的收敛速度。
4. 栈溢出风险: 由于使用递归，如果搜索深度过大，可能会导致栈溢出。在实现时可以考虑使用迭代版本来避免这一问题。

解题思路

1. 初始化: 设定初始深度限制d=0，以及一个足够大的上限D作为退出条件。
2. 计算阈值: 使用当前深度限制计算f(n)的阈值，即f_limit = g(start) + d * h(start)，其中g(start)=0，因为是从初始节点开始。
3. 深度优先搜索: 从初始节点开始执行深度优先搜索，只有当节点的f(n)=g(n)+h(n)小于当前的f_limit时才继续扩展该节点的子节点。
4. 递归加深: 如果在当前深度限制下没有找到解，则增加深度限制d=d+1，回到步骤2，继续搜索。
5. 结束条件: 当搜索到目标节点或达到预设的深度上限D时，结束搜索。

AcWing 180. 排书   

题目描述

180. 排书 - AcWing题库

运行代码

#include <iostream>
#include <cstring>
#include <algorithm>
const int N = 15;  // 书的数量上限
using namespace std;
int n;  // 实际的书的数量
int q[N];  // 存储书的初始排列
int w[5][N]; // 辅助数组，用于在搜索过程中保存中间状态 
// 估价函数：计算当前状态与目标状态的差异，返回还需要多少步才能达到目标状态
int f() { int tot = 0;for (int i = 0; i + 1 < n; ++i) {if (q[i + 1]!= q[i] + 1) {++tot;}}return (tot + 2) / 3;
} 
// 深度优先搜索函数
bool dfs(int depth, int max_depth) { if (depth + f() > max_depth) { // 如果当前深度加上估计的剩余深度超过了限制深度，进行剪枝return false; }if (f() == 0) { // 如果估价函数为0，说明已经达到目标状态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 y = l; for (int x = r + 1; x <= k; x++, y++) { // 将连续段插入到指定位置q[y] = w[depth][x]; }for (int 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; // 迭代加深搜索，从深度0开始，每次增加1，直到找到解或者深度达到5while (depth < 5 &&!dfs(0, depth)) { depth++; }if (depth >= 5) {cout << "5 or more" << endl; } else {cout << depth << endl; }}return 0; 
}

代码思路

• 估价函数 f()：用于估计从当前状态到达目标状态（书按照 1∼n 的顺序依次排列）还需要的最少操作次数。通过计算当前排列中顺序不正确的后继关系的数量 tot ，然后返回 (tot + 2) / 3 作为估计值。这是因为每次移动一个连续段最多可以改变 3 个元素的后继关系。
• dfs(int depth, int max_depth) 函数：进行深度优先搜索。
  • 参数 depth 表示当前搜索的深度（即已经进行的操作次数）。
  • max_depth 是限制的最大深度。如果在当前深度 depth 下，加上估计的还需要的最少操作次数 f() 超过了 max_depth ，就意味着即使后面按照最优方式操作也无法在限制深度内达到目标状态，此时进行剪枝（直接返回 false ，不再继续搜索该路径）。
  • 通过三重循环来枚举移动连续段的长度、起始位置和插入位置，模拟进行抽取连续段并插入到其他位置的操作。
  • 在每次尝试一种可能的操作后，递归调用 dfs(depth + 1, max_depth) 搜索下一层。如果找到解（即达到目标状态），则返回 true ，否则恢复原来的状态（通过 memcpy(q, w[depth], sizeof q); ），继续尝试其他可能的操作。
• 主函数中的迭代加深搜索：从深度 0 开始，每次增加 1，调用 dfs(0, depth) 进行搜索。如果在深度小于等于 4 时找到了解，就输出对应的操作次数；如果直到深度达到 5 还没有找到解，就输出 "5 or more" 。

改进思路

1. 优化内存使用：可以减少使用的辅助数组数量，或者使用更高效的数据结构来存储中间状态。
2. 改进剪枝策略：可以进一步优化估价函数，使其更加准确，从而增强剪枝效果，减少不必要的搜索。
3. 优化循环结构：对于一些循环的边界条件和步长进行优化，以减少不必要的计算。

改进代码

#include <iostream>
#include <cstring>
#include <algorithm>const int N = 15;  // 书的数量上限int n;  // 实际的书的数量
int q[N];  // 存储书的初始排列// 估价函数：计算当前状态与目标状态的差异，返回还需要多少步才能达到目标状态
int f() { int tot = 0;for (int i = 0; i + 1 < n; ++i) {if (q[i + 1]!= q[i] + 1) {++tot;}}return (tot + 2) / 3;
} // 深度优先搜索函数
bool dfs(int depth, int max_depth) { if (depth + f() > max_depth) { // 如果当前深度加上估计的剩余深度超过了限制深度，进行剪枝return false; }if (f() == 0) { // 如果估价函数为0，说明已经达到目标状态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) { // 枚举要插入的位置（连续段的结束位置的后面）int temp[N];memcpy(temp, q, sizeof(q));  // 复制当前状态int y = l; for (int x = r + 1; x <= k; x++, y++) { // 将连续段插入到指定位置q[y] = temp[x]; }for (int x = l; x <= r; x++, y++) {q[y] = temp[x]; }if (dfs(depth + 1, max_depth)) { // 递归搜索下一层return true; }memcpy(q, temp, sizeof(q)); // 如果不成功，恢复当前状态 }}}return false; 
} int main() { int T; std::cin >> T; while (T--) { std::cin >> n; for (int i = 0; i < n; ++i) {std::cin >> q[i]; }int depth = 0; // 迭代加深搜索，从深度0开始，每次增加1，直到找到解或者深度达到5while (depth < 5 &&!dfs(0, depth)) { depth++; }if (depth >= 5) {std::cout << "5 or more" << std::endl; } else {std::cout << depth << std::endl; }}return 0; 
}