2.2.3 DFS之迭代加深、双向DFS、IDA*

一. DFS之迭代加深(IDDFS)

针对某些分支非常深，但答案却在比较浅的分支的层中，为防止进入深分支的”无底洞“而浪费过多时间，需要设置每次搜索的深度，使用迭代加深的DFS搜索。尤其是某些题目会限制搜索步长，如”10以内搜索不到结果就算无解”。

迭代加深设置一个层数上限max_depth，搜索时如果当前层数大于max_depth后则直接返回。相当于每次把层数大于max_depth的层先全部剪掉，也可以把max_depth看成划定了搜索区域，每次一片区域一片区域的搜，可以有效地减小搜索空间。

2675_69ed07da7c-1

迭代加深和宽搜的区别：

宽搜搜索空间的复杂度每次是指数级别的，每次把该层的节点全部记录到队列中。
迭代加深本质仍是深度优先搜索，每次只会记录当前分支（路径）的信息，空间复杂度是O(n)的，与高度成正比

迭代加深水从存在重复搜索的问题，每次更新max_depth进行搜索时都是从头开始搜索，会对浅层进行重复搜索。如当深度限制为d是，会重复搜索1~d-1层的节点，但是当搜索树节点分支数目较多时，随着层数的深入，每层节点数会呈指数级增长，因此重复的搜索和深层子树的规模相比可以忽略不计。如以满二叉树为例，前n-1层总节点数为$2^1 + 2^2 + \ldots + 2^{n-1} = 2^{n} - 1$，而第n层的节点数为$2^n$，当分支数更多时这种差距更大，所以对于浅层的重复搜索可以忽略不计。

迭代加深后的DFS具有类似BFS性质，当从0开始一层层加深时depth能够记录最小步长。

1. AcWing 170. 加成序列

搜索顺序：

枚举前面的所有数i，j（i可以等于j），填写当前位置的数

剪枝

优化搜索顺序：从大到小枚举i和j
排除等效冗余：不同i和j，X[i]+X[j]可能相等，枚举的组合出现实质冗余，需要判重
可行性剪枝：由于序列一定是严格单调递增的，所以当前节点值 $V_u$ 大于目标值n，或小于等于前一节点值 $V_{u-1}$ 时，直接剪枝

注意由于每个位置的填写都是枚举前面任意两节点值的和，所以是可能出现枚举得到的值$V_{u}$小于等于 $V_{u-1}$ 的，必须要判断并剪枝，不要忽略！

可以注意到分支最短时是第k位取k-1位的两倍，即 $2^u$ ，分支指数增长。而分支最短的是每次加1，第k层大小为u。由此可以发现不同分支为了达到某一数量级的，深度差距很大。同时由于可以是任意两个数的组合，所以分支非常多，且分支数随深度成平方级增长 $(C_u^2)$ 。由此，可以使用迭代加深。

2675_b66a50cb7c-4

进一步优化剪枝

在优化搜索顺序时，除了先枚举较大的数，其实可以发现只需枚举前一层第u-1层与前u-1层所有数字能否组合出合法序列，而不用任意枚举两个数的组合！

且这样枚举一定能保证$V_{u}$大于$V_{u-1}$的，满足单调递增要求。

C++

恢复现场版，慢

// AcWing 170. 加成序列
#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;
const int N = 110;

int n;
int path[N];
bool st[N];

bool dfs(int u, int depth){
    if (u == depth) return path[u - 1] == n;
    // if (u > depth) return false;
    // if (path[u - 1] == n) return true;
    
    for (int i = u - 1; i >= 0; -- i)    
        for (int j = i; j >= 0; -- j){
            int v = path[i] + path[j];
            // 可行性剪枝：由于序列一定是严格单调递增的，所以当前节点值V_u大于目标值n，或小于等于前一节点值V_{u-1}时，直接剪枝
            if (v > n || v <= path[u - 1] || st[v]) continue;
            
            // 剪枝之排除等效冗余：不同i和j，X[i]+X[j]可能相等，枚举的组合出现实质冗余，需要判重
            st[v] = true;
            path[u] = v;
            if (dfs(u + 1, depth)) return true;
            // 恢复现场
            st[v] = false;
        }
    return false;
}

int main(){
    while (scanf("%d", &n), n){
        // 初始化
        memset(st, 0, sizeof st);
        path[0] = 1; // 起始节点一定是1
        
        // 设置迭代加深的最大深度depth
        int depth = 1;
        // 每次搜索失败则加大搜索深度
        while (!dfs(1, depth)) depth ++; 
        for (int i = 0; i < depth; ++ i)
            printf("%d ", path[i]);
        printf("\n");
    }
    return 0;
}

不恢复现场版，速度比恢复现场版快一半多

// AcWing 170. 加成序列
#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;
const int N = 110;

int n;
int path[N];

bool dfs(int u, int depth){
    if (u == depth) return path[u - 1] == n;
    // if (u > depth) return false;
    // if (path[u - 1] == n) return true;
    
    bool st[N] = {0}; // st数组每轮递归都会被重开，避免恢复现场，速度更快
    // 剪枝之优化搜索顺序：从大到小枚举i和j
    for (int i = u - 1; i >= 0; -- i)    
        for (int j = i; j >= 0; -- j){
            int v = path[i] + path[j];
            // 可行性剪枝：由于序列一定是严格单调递增的，所以当前节点值V_u大于目标值n，或小于等于前一节点值V_{u-1}时，直接剪枝
            if (v > n || v <= path[u - 1] || st[v]) continue;
            
            // 剪枝之排除等效冗余：不同i和j，X[i]+X[j]可能相等，枚举的组合出现实质冗余，需要判重
            st[v] = true;
            path[u] = v;
            if (dfs(u + 1, depth)) return true;
            // 这里不需要恢复现场，因为path[u]会被直接覆盖，而st数组每轮递归都会被重开
        }
    return false;
}

int main(){
    while (scanf("%d", &n), n){
        // 初始化
        path[0] = 1; // 起始节点一定是1
        
        // 设置迭代加深的最大深度depth
        int depth = 1;
        // 每次搜索失败则加大搜索深度
        while (!dfs(1, depth)) depth ++; 
        for (int i = 0; i < depth; ++ i)
            printf("%d ", path[i]);
        printf("\n");
    }
    return 0;
}

进一步优化剪枝，速度再次降一半

// AcWing 170. 加成序列
#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;
const int N = 110;

int n;
int path[N];

bool dfs(int u, int depth){
    if (u == depth) return path[u - 1] == n;
    // if (u > depth) return false;
    // if (path[u - 1] == n) return true;
    
    bool st[N] = {0}; // st数组每轮递归都会被重开，避免恢复现场，速度更快
    // 剪枝之优化搜索顺序：从大到小枚举i和j
    for (int i = u - 1; i >= 0; -- i){    
        int v = path[i] + path[u - 1];
        // 可行性剪枝：由于序列一定是严格单调递增的，所以当前节点值V_k大于目标值n，或小于等于前一节点值V_{k-1}时，直接剪枝
        if (v > n || v <= path[u - 1] || st[v]) continue;
        
        // 剪枝之排除等效冗余：不同i和j，X[i]+X[j]可能相等，枚举的组合出现实质冗余，需要判重
        st[v] = true;
        path[u] = v;
        if (dfs(u + 1, depth)) return true;
        // 这里不需要恢复现场，因为path[u]会被直接覆盖，而st数组每轮递归都会被重开
    }
    return false;
}

int main(){
    while (scanf("%d", &n), n){
        // 初始化
        path[0] = 1; // 起始节点一定是1
        
        // 设置迭代加深的最大深度depth
        int depth = 1;
        // 每次搜索失败则加大搜索深度
        while (!dfs(1, depth)) depth ++; 
        for (int i = 0; i < depth; ++ i)
            printf("%d ", path[i]);
        printf("\n");
    }
    return 0;
}

Python

# AcWing 170. 加成序列
def main():
    # u 为当前层数 / path 下标，depth为最大搜索层数
    def dfs(u, depth):
        # 限制搜索层数
        if u == depth:
            return path[u - 1] == n
        vis = [False] * MAX_D
        
        # 优化搜索顺序，先枚举较大的数
        # 且只需枚举第u-1个数字与前u-1个数字能否组合出合法序列
        for x in reversed(path[:u]):
            v = x + path[u - 1]
            if v > n or vis[v]:
                continue
            # 剪枝之排除等效冗余
            vis[v] = True
            path[u] = v
            if dfs(u + 1, depth):
                return True
        return False
    
    MAX_D = 110
    path = [1] * MAX_D 
    # 这里对起始节点path[0]进行了初始化，其一定为1
    
    # 迭代加深像是 「限制层数的广搜」 版本的深搜
    # 优势在于空间复杂度低，代码量低
    while True:
        n = int(input())
        if not n:
            break
        depth = 1
        while not dfs(1, depth):
            depth += 1
        print(" ".join(map(str, path[:depth])))
        
if __name__ == "__main__":
    main()

二. 双向DFS

双向DFS原理与双向BFS相同，通过双向搜索来减少搜索空间。使用双向搜索要求题目具有明确的初态和终态，从而从两端开始搜索。

2675_357470bf81-1

1. AcWing 171. 送礼物

问题分析

本题数据范围为：$1 \le N \le 46$，$1 \le W, G[i] \le 2^{31}-1$ ，其中N表示礼物个数，G[i]表示第i个礼物重量，W表示容量上限

这题可以看作背包问题，但DP方法的时间复杂度是O(N*V)，$2^{31}$ 在 $2 \times 10^9$ 级别， $ N * 2^{31} $会超时，因此不能用求解。

但我们发现N相对较小，可以尝试使用暴搜。而直接暴搜的话需要枚举每个物品选或不选，时间复杂度是$2^{46}$，更会超时。由此我们想到使用双向DFS，尝试把时间复杂度降到$C * 2^{23} $ 级别，$ 2^{23} = 8,388,608$ 。

为此我们可以将物品划分成两部分，先将前K件物品能够凑出的所有重量枚举出来并打表。同时为了优化，存储时可以进行排序并判重。然后先将剩余N-K件物品能够凑出的所有重量枚举，并通过直接查表与前一部分的重量进行组合，得到合法方案。同时在两部分组合时可以使用贪心策略，利用二分直接找到与当前后部分重量能够组合的前部分最优重量（满足条件下的最大重量），减少枚举。

需要使用以下方法

双向DFS暴搜
空间换时间的思想，先对前部分的所有情况打表，后面可直接使用而不用再搜索
二分法快速找到集合中满足条件（小于等于某数）的最大的数

注意二分不能用哈希代替，设当前后部分枚举重量为S，我们要做的是在前部分找到小于等于W-S的最大数，而不是确定W-S是否存在

基本思路

将所有物品按重量从大到小排序
先将前K件物品能够凑出的所有重量打表，然后排序判重
搜索剩下的N-K件物品的选择方式，然后在表中二分出不超过W的最大值

进一步剪枝优化

优化搜索顺序

把礼物按照重量降序排序后再分半，搜索。（先搜较大的数，使分支更少）
选取适当的“折半划分点”

当直接对半划分时复杂度为$2^{ \frac{N}{2} } + 2^{ \frac{N}{2} } * \frac{N}{2} $，前后两部分不均衡

由于复杂度分为两部分——前半部分的枚举 $2^k$ ，后半部分的枚举与匹配 $ 2^{N-k} * k $，为了实现两部分的均衡，进一步减少复杂度，需要选取适当的“折半划分点”。
$$
\frac{2^k}{ (2^{N-k} * k) } = \frac{ 2^{2k - N} }{k}
$$
当k取25时，两者之比最接近1

然而实际情况下这种均衡并不好实现，一般还是对半分。例如，本题中$\frac{N}{2} + 2$ 就不一定更均衡。

首先需要处理特殊情况n = 1 造成的内存溢出问题。

其次，由于加大k是为了平衡后半部分DFS时二分的系数，但是这个系数只会在叶子结点出现，由于剪枝的存在，这些点的二分并不一定能使整个DFS时间明显变得更大，这种情况下k加大2反而影响了前半和后半的平衡。
可行性剪枝，不超过上限

2675_3b100ab781-3

C++

// AcWing 171. 送礼物
#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

// 注意爆int
typedef long long LL; 

const int N = 1 << 25; 
// 前半部分物品个数k最大是25， 因此最多可能有2^25种方案

// n表示物品总个数，m表示重量上限，k表示前半部分物品个数
int n, m, k;
int g[50]; // 存储所有物品的重量
int w[N]; // w存储能凑出来的所有组合重量
int cnt; // cnt记录前部分所有组合重量的个数（需去重）
int ans; // 用ans来记录一个全局最大值

// u表示当前枚举到哪个数了，s表示当前重量的和
void dfs_s(int u, int s){
    // 打表
    // 如果我们当前已经枚举完第k个数（下标从0开始的）了， 
    // 就把当前的s加到w数组中去，进行打表
    if (u == k){
        w[cnt ++] = s; // 记录重量
        return;
    }
    
    // 枚举当前不选这个物品
    dfs_s(u + 1, s);
    
    // 枚举选这个物品, 做一个可行性剪枝
    //计算和的时候转成long long防止溢出
    if ((LL)s + g[u] <= m) { 
        dfs_s(u + 1, s + g[u]);
    }
}

// u表示当前枚举到哪个数了，s表示当前重量的和
void dfs_e(int u, int s){
    // 二分匹配
    // 如果已经找完了n个节点，就得到了后半部分当前的重量组合
    // 那么需要通过二分进行前后部分的匹配
    if (u == n){
        int l = 0, r = cnt - 1;
        while (l < r){
            int mid = (l + r + 1) >> 1;
            // if (w[mid] + (LL)s <= m) 
            if (w[mid] <= m - s)
                l = mid;
            else
                r = mid - 1;
        }
        // 这里需主要由于l从0开始，而w[0] = 0，所以可以解决s恰等于n的情况（只从后半部分选），因而不同单独判断
     	// 且由于前面递归时始终保证了s <= m（否则不会选择物品进行下一层的递归)，所以二分时是一定能找到可行的数的（最极端就是取w[0]=0)，因而循环结束后w[l] + (LL)s <= m一定成立
        ans = max(ans, w[l] + s);
        return;
    }
    
    // 不选择当前这个物品
    dfs_e(u + 1, s);
    
    // 选择当前这个物品
    // 虽然m，s，g[u]在int范围内，但s + g[u]可能会爆int，要转成LL
    if ((LL)s + g[u] <= m)
        dfs_e(u + 1, s + g[u]);
}

int main(){
    scanf("%d%d", &m, &n);
    for (int i = 0; i < n; ++ i) scanf("%d", &g[i]);
    
    // 剪枝之优化搜索顺序，重量从大到小排序后再分组、枚举
    sort(g, g + n, greater<int>());
    // reverse(g, g + n);
    
    // 枚举前k个物品的重量组合并打一个表
    k = n >> 1; // 或者k = n / 2; 需注意防止 n = 1时，出现死循环
    // min((n >> 1) + 2, n - 1)这种策略实际发现并不可行
    dfs_s(0, 0);
    
    // 做完之后，把w数组从小到大排序，从而方便二分
    sort(w, w + cnt);
    
    // 判重，只取不重复的
    // int t = 1;
    // for (int i = 1; i < cnt; ++ i)
    //     if (w[i] != w[i - 1])
    //         w[t ++] = w[i];
    // cnt = t;
    
    // 去重后尾地址减首地址得到个数
    // unique函数可以删除有序数组中的重复元素。
    // 注意：
    // a. 这里的删除不是真的delete，而是将重复的元素放到容器末尾
    // b. unique函数的返回值是去重之后的尾地址（去重后最后一个不重复元素后的元素的地址）
    // c. 一定要先对数组进行排序才可以使用unique函数
    cnt = unique(w, w + cnt) - w;
    // 这里有一点需要格外注意，由于w的空间是大于需要值的，所以数组中实际上含有0
    // 而因此在从小到大排序并去重后，w[0] = 0并不表示物品的重量
    
    // 从k开始后半部分的枚举， 当前的和是0
    dfs_e(k, 0);
    
    printf("%d\n", ans);
    return 0;
}

Python

from bisect import bisect
def main():
    m, n = map(int, input().split())
    # 剪枝之优化搜索顺序，重量从大到小排序后再分组、枚举
    g = sorted([int(input()) for _ in range(n)], reverse=True)
    # 将数组分割成两部分，让两部分计算的时间复杂度尽可能接近
    # k 做特殊处理，当 n = 1 时，k 不能大于 n
    res, k = 0, n >> 1
    w = set()
    # 先使用集合避免重复问题，再排序转成list
    
    # 将两个 DFS 进行合并，使用 lim 值的不同来标记当前是第几次搜索
    # u表示当前枚举到哪个数了，s表示当前重量的和
    def dfs(u, s):
        if u >= lim:
             # lim == k 表示是第一个 DFS
            if lim == k:
                 # 打表，使用 set 记录第一个 DFS 搜索到的组合答案
                w.add(s)
            else:
                # 二分法进行前后匹配，找到一个小于等于m - s的最大值
                nonlocal res
                # bisect.bisect和bisect.bisect_right返回大于x的第一个下标(相当于C++中的upper_bound)
                # bisect.bisect_left返回大于等于x的最左侧第一个下标
                # 当x存在多个时，bisect_left返回最左边的x的索引bisect_right返回最右边的x的索引加1
                # 如果元素不存在，则将其插入到何处
                # eg:l = [1, 4, 5]，bisect_left(l, 4)返回1，bisect_left(l, 2)返回1
                # bisect_left(l, 6)返回3
                pos = bisect(w, m - s) - 1 # 这里要使用bisect而不是bisect_left
                # 因为bisect返回大于x的最左的第一个下标，所以其减一即得到小于等于x的最右侧的数
                res = max(res, s + w[pos])
            return
        
        # 不选择当前这个物品
        dfs(u + 1, s)
        # 选择当前这个物品
        if s + g[u] <= m:
            dfs(u + 1, s + g[u])
        
    lim = k
    dfs(0, 0)
    
    w.add(0) # 这里额外插入0，否则二分后需进行特判找不到元素的情况（即s==n
    # 做完之后，把w数组从小到大排序，从而方便二分
    # 注意虽然set是无序的，但sorted会先进行排序并返回一个列表，此时w变成一个列表
    w = sorted(w)
    
    lim = n
    # 从k开始后半部分的枚举， 当前的和是0
    dfs(k, 0)
    print(res)
    
if __name__ == "__main__":
    main()

三. IDA*

IDA*将估价函数与DFS相结合，一般配合迭代加深一起食用，在每个节点我们都会预估一下当前节点最少需要多少步才能得到答案，如果最小步数多于迭代加深设置的最大层数max_depth，则直接剪枝，提前退出。

其实质是通过启发估计给迭代加深增加一个额外的剪枝：若当前深度+未来估计步数>深度限制，则立即从当前分支回溯

IDA*的核心也在于设计一个估价函数，估算从每个状态到目标状态需要的步数。估价函数需要遵守“估计值不大于未来实际步数”的准则。设计时一般可以采用贪心策略，考虑最理想的情况。

1. AcWing 180. 排书

思路分析

先考虑每一步的决策数量：当抽取长度为 i 的一段时，有 n - i + 1 种抽。对于每种抽法，还剩下n-i本书，一共有n - i + 1个位置可以插入这些书，除去原来的位置，有 n - i 种放法。另外，将某一段向前移动，等价于将跳过的那段向后移动，因此每种移动方式被算了两遍，所以每个状态总共的分支数量是：
$$
\sum _{i=1}^n(n-i) * (n - i + 1) / 2 = (15 * 14 + 14 * 13 + … + 2 * 1) / 2 = 560
$$
这里利用了：
$$
n\times(n-1)+(n-1)\times(n-2)+…+2\times1=\frac{(n-1)\times n\times(n+1)}{3}
$$

考虑在四步以内解决，最多有 $560^4$ 个状态，直接暴搜会超时。可以使用双向 BFS 或者 IDA * 来优化。

我们用 IDA * 来解决此题。

IDA* 与 A*算法的选择：

需要最小字典序时，状态表示很大，指数增长加快，使用IDA*
若状态容易表示，指数增长较慢时，使用A* （注意需要最小字典序时不能使用A* ，因为它不是按照顺序搜索的）。

估价函数设计详解

估价函数需要满足：不大于实际步数。且本题中，在最终状态下，每本书后面的书的编号应该比当前书多 1。
为了确定最小步数，就需要理解每步操作的实质。

首先我们需要理解何为排好序或不排好序，其实只用考察相邻两个数的后继关系是否正确。排好序后n 的后继应该是 n+1。

每部操作的实质就是改变一些数的后继关系，并且每次操作最多会断开三个相连的位置，再重新加入三个相连的位置，因此我们会更改 3 个元素的后继关系，如下图：

也因此，最多会将 3 个错误的连接修正。每次迭代前，我们可以计算出当前有多少个后继关系是不正确的，假设一共有$tot$个后继关系不正确，则修复这些后继需要的最少步数为：
$$
\lceil \frac{tot}{3} \rceil = \lfloor \frac{tot+2}{3} \rfloor
$$
因此当前状态 $s$ 的估价函数可以设计成
$$
f(s) = \lceil \frac {tot }{3} \rceil = \lfloor \frac{tot+2}{3} \rfloor
$$
如果当前层数加上 $f(s)$ 大于迭代加深的层数上限，则直接从当前分支回溯。

搜索顺序

首先枚举移动长度i
只考虑后移操作，对于每段书i枚举被移动的起始位置l和后移后的起始位置k

如下图：

优化

上述操作实际进行了优化，进行了排除等效冗余。可以发现，由于对称性，将前面一段后移就等价于将对应后面一段前移。因此我们排除冗余，只考虑搜索后移的情况即可。

时间复杂度

理论上最多搜索 $560^4$ 个状态，使用 IDA * 后实际搜索的状态数量很少。

C++

// AcWing 180. 排书
#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 17;

int n;
int q[N]; // 书的编号
int w[5][N]; // 用于存储操作前当前的序列，恢复现场使用
// 这里需要理解为什么需要开5个，因为每层递归都需要恢复现场，且浅层要在深层后恢复
// 而最多五层，所以开5个

// 估价函数
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 check(){
    for (int i = 0; i + 1 < n; ++ i)
        if (q[i + 1] != q[i] + 1)
            return false;
    return true;
}

// u: 当前迭代深度; depth: 迭代加深最大深度
bool dfs(int u, int depth){
    // IDA*剪枝
    // 若当前深度+未来估计步数>深度限制，则立即从当前分支回溯
    if (u + f() > depth) return false;
    if (u == depth && check()) return true; // 这里不要判断
    
    // 先枚举长度len
    for (int len = 1; len <= n; ++ len)
        // 然后枚举移动前左端点l
        for (int l = 0; l + len - 1 < n; ++ l){
            int r = l + len - 1; // 减1别忘了
            // 再枚举后移后插入的右端点k，
            // 剪枝之排除等效冗余，只考虑后移操作
            for (int k = r + 1; k < n; ++ k){
                memcpy(w[u], q, sizeof q); // 拷贝当前序列，用于恢复现场
                // 后移操作需要两步，首先将移动段落右端点后到后移插入的起始端点中间的部分前移
                // 然后再将移动段落插入
                int x, y; // x使用记录移入数的位置，y始终记录要修改位置
                // 将当前移动段落后面的序列前移，即将上图中绿色部分移动到红色部分
                // 注意k是插入的右端点
                for (x = r + 1, y = l; x <= k; x ++, y ++) q[y] = w[u][x];
                // 移动段落插入
                for (x = l; x <= r; x ++, y ++) q[y] = w[u][x];
                if (dfs(u + 1, depth)) return true;
                // 恢复现场
                memcpy(q, w[u], sizeof q);
            }
        }
    
    // 另一种枚举防止，直接枚举左端点，右端点，插入点（插入的右端点），更简单
    // for (int l = 0; l < n; l ++ )
    //     for (int r = l; r < n; r ++ )
    //         for (int k = r + 1; k < n; k ++ ){
    //             memcpy(w[u], q, sizeof q);
    //             int x, y;
    //             for (x = r + 1, y = l; x <= k; x ++, y ++ ) q[y] = w[u][x];
    //             for (x = l; x <= r; x ++, y ++ ) q[y] = w[u][x];
    //             if (dfs(u + 1, depth)) return true;
    //             memcpy(q, w[u], sizeof q);
    //         }
    
    return false;
}

int main(){
    int t;
    scanf("%d", &t);
    while(t --){
        scanf("%d", &n);
        for (int i = 0; i < n; ++ i) scanf("%d", &q[i]);
        
        int depth = 0; // 注意depth要从0开始，以处理原本就有序的特殊情况
        while (depth < 5 && !dfs(0, depth)) depth ++;
        if (depth >= 5)
            puts("5 or more");
        else
            // 由于我们使用了迭代加深，所以depth恰好等于最少需要操作次数
            printf("%d\n", depth);
    }
    return 0;
}

Python

# AcWing 180. 排书
def main():
    # 估价函数：不连续的数对数量除三，向上取整
    f = lambda: (sum(int(q[i + 1] != q[i] + 1) for i in range(n - 1)) + 2) // 3
    # 检查是否排好
    check = lambda: all(q[i + 1] == q[i] + 1 for i in range(n - 1))
    # check = lambda: all(arr[i] == i + 1 for i in range(n))
    
    def IDAstar(level):
        # IDA*剪枝
        # 若当前深度+未来估计步数>深度限制，则立即从当前分支回溯
        if level + f() > depth:
            return False
        if level == depth and check():
            return True
        # 枚举左端点，右端点，插入点（插入的右端点）
        for L in range(n):
            for R in range(L, n):
                for K in range(R + 1, n):
                    # 后移操作
                    # 这里使用 Python 的切片来进行数组中 [L, R] 和 [R + 1, K] 两段的交换
                    length, fst, sec = K - R, q[L:R+1], q[R+1:K+1]
                    # 注意这里切片范围
                    q[L:L+length], q[L+length:K+1] = sec, fst
                    if IDAstar(level + 1):
                        return True
                    # 恢复现场
                    q[L:R+1], q[R+1:K+1] = fst, sec
            
    
    T = int(input())
    for _ in range(T):
        n, depth = int(input()), 0
        q = list(map(int, input().split()))
        # 迭代加深 + IDA* 优化
        while depth < 5 and not IDAstar(0): depth += 1
        print("5 or more" if depth >= 5 else depth)

if __name__ == "__main__":
     main()

2. AcWing 181. 回转游戏

问题分析

本题采用 IDA* 算法，即迭代加深的 A* 算法。

在这题中，每次操作循环移动一格，不断的移动可能导致某些子树的深度很深，但是根据直觉，最优解的操作步数不会处于太深的位置，所以可以用迭代加深来做，再通过题目本身可以构造一个估价函数，即可以使用 IDA* 算法求解。

显然本题属于外部搜索（最小步数模型），需要搜索状态图，因此本题真的核心难点时状态存储和操作表示。

如何保证答案的字典序最小？

由于最短操作步数是一定的，因此每一步枚举时先枚举字典序小的操作即可。

状态存储与操作表示——打表法

可以使用编码的技巧实现存储与表示。

位置编码：由于图为 # 形，为了将其存入数组中，我们可以对每个位置设定一个编号，进行手动打表。寻找元素值时只需查表即可。
操作编码：八种操作虽然操作对象不同，但是本质上都是进行循环移动——将头元素放到末尾，同时其他元素前移。同样，我们也可以给每个操作设定一个编号，并把其对应的位置操作用位置编号表示处理，并进行存储打表。使用操作时也只用查表即可。

具体编号见下图：

61813_fe1427dc8a-image-20210321172207678

估价函数

为了得到估价函数，我们同样需要理解操作的实质影响，并利用贪心思想等得到理想情况下的最优解。

可以发现，我们的目标是中心区域，而每次拉动操作，只会改变中心区域内的一个值，其他都保持不变。为了最快使最中间的 8个格子里的数字相同，可以使用以下贪心策略：先找出这个区域内个数最多的数字，记个数为k，那么理想情况下（接下来每步操作都是有效的），至少还需要8-k步操作来去除其他数字。由此当前状态 $s$ 的估价函数可以设计成
$$
f(s) = 8 - k
$$

总结一下：

统计中间 8 个方格中出现次数最多的数出现了多少次，记为 $k$ 次。
每次操作会从中间 8 个方格中移出一个数，再移入一个数，所以最多会减少一个不同的数。
因此估价函数可以设为 $8 - k$。

搜索框架

整个框架是IDA*，从0开始枚举层数，然后在每一层搜索时计算估价函数

如果当前层加上估价函数大于目前最优解则return
否则遍历8个操作进行状态转换，并递归搜索

剪枝

排除等效冗余：记录上一次的操作，本次操作避免枚举上一次的逆操作。

可以发现相对的两个操作互为逆操作，两者作用相反。如果两者接连使用，效果会抵消，导致无效操作甚至死循环。为此，需要进行打表，记录每个操作对应的逆操作。当使用某操作后，下一个操作一定不能是其逆操作。

为了记录上一层的操作，使用传入形参last

时间复杂度

假设答案最少需要 $k$ 步，每次需要枚举 $7$ 种不同操作（除了上一步的逆操作），因此最坏情况下需要枚举 $7^k$ 种方案。但加入启发函数后，实际枚举到的状态数很少。

C++

// AcWing 181. 回转游戏
/* 打表——进行位置编码和操作编码
           A(0)  B(1)
           0     1
           2     3
H(7) 4  5  6  7  8  9  10 C(2)
           11    12
G(6) 13 14 15 16 17 18 19 D(3)
           20    21
           22    23
           F(5)  E(4)
*/
#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 24;

int q[N]; // 存储当前状态图

// 8个方向操作对应的数据编号
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 opposite[8] = {5, 4, 7, 6, 1, 0, 3, 2};
// 中心八个数据的位置编号
int center[8] = {6, 7, 8, 11, 12, 15, 16, 17};

int path[100]; // path用于存储方案

// 估价函数
int f(){
    // 由于只有三种数字1，2，3，所以可以统计每个数字的次数，然后取最大值
    int s[4] ={0}; // 注意初始化为0
    
    // static int sum[4]; // 静态数组，不用每次重开浪费空间时间
    // memset(sum, 0, sizeof sum); // 需要每次memset重新赋值
    
    for (int i = 0; i < 8; ++ i) s[q[center[i]]] ++; // 计算1 2 3出现次数
    int maxv = 0;
    for (int i = 1; i < 4; ++ i) maxv = max(maxv, s[i]); // 统计出现最多的次数，不用管具体是哪个数字
    
    return 8 - maxv;
}

// 进行对应的操作
void operate(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;
}

// u: 当前迭代深度, depth: 迭代加深最大深度, last: 上一次操作
bool dfs(int u, int depth, int last){
    // IDA*剪枝
    // 若当前深度+未来估计步数>深度限制，则立即从当前分支回溯
    if (u + f() > depth) return false;
    // 估价函数为0，表明格子内数全部相同
    if (!f()) return true;
    
    // 枚举八个操作
    for (int i = 0; i < 8; ++ i)
        // 剪枝之排除等效冗余，避免逆操作相互抵消
        if (opposite[i] != last){ // 由于初始时last=-1，所以不使用oppsite[last] != i的写法
            operate(i);
            path[u] = i; // 深度恰好对应操作数
            if (dfs(u + 1, depth, i)) return true;
            // 回溯恢复现场
            operate(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; // 注意depth要从0开始，以处理原本就满足要求的特殊情况
        
        while (!dfs(0, depth, -1)) depth ++;

        if (!depth) printf("No moves needed");
        else{
            // 迭代加深的depth能够记录最小步长
            for (int i = 0; i < depth; ++ i) printf("%c", 'A' + path[i]);
        }
        printf("\n%d\n", q[6]);
    }
    return 0;
}

Python

# AcWing 181. 回转游戏

# 打表——进行位置编码和操作编码
#           A(0)  B(1)
#           0     1
#           2     3
# H(7) 4  5  6  7  8  9  10 C(2)
#           11    12
# G(6) 13 14 15 16 17 18 19 D(3)
#           20    21
#           22    23
#           F(5)  E(4)

from sys import stdin
import copy 

def main():
    op = ((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))
    
    oppo, center = (5, 4, 7, 6, 1, 0, 3, 2), (6, 7, 8, 11, 12, 15, 16, 17)
    
    log = {i: ch for i, ch in enumerate("ABCDEFGH")} # 用于输出
    
    # 估价函数：中心元素数 - 中心区域频次最高的元素数量
    def f():
        cnt = [0] * 4
        for x in center:
            cnt[q[x]] += 1
        return 8 - max(cnt)
    # 需注意这里不能压行使用lambda函数，会超时
    # f = lambda: 8 - Counter(arr[x] for x in mid).most_common(1)[0][1]
    
    # 额外递归函数速度会慢很多，直接在IDAstar中实现
    # 进行对应的操作
    # def helper(idx):
    #     temp = q[op[idx][0]]
    #     for i in range(6):
    #         q[op[idx][i]] = q[op[idx][i + 1]]
    #     q[op[idx][6]] = temp
 
    def IDAstar(level, pre):
        nonlocal q
        assume = f()
        # 当前深度+未来估计步数>深度限制，则立即从当前分支回溯
        # 找到答案返回 True
        if level + assume > depth or not assume:
            return assume == 0
        
        # 枚举8个操作
        for i in range(8):
            if pre != oppo[i]:
                tmp = copy.copy(q) # 用于恢复现场，比使用逆操作速度更快
                
                # 进行对应的操作
                # helper(i)
                temp = q[op[i][0]]
                for j in range(6):
                    q[op[i][j]] = q[op[i][j + 1]]
                q[op[i][6]] = temp
                
                path[level] = i # 记录当前的操作
                if IDAstar(level + 1, i):
                    return True
                    
                # helper(oppo[i])
                q = copy.copy(tmp) # 恢复现场
        return False
    
    path = [0] * 100
    # 输入和输出优化
    for line in stdin:
        if line[0] == '0': break
        q, depth = list(map(int, line.split())), 0
        while not IDAstar(0, -1): depth += 1
        print(f"{''.join(log[x] for x in path[:depth])}" if depth 
        else "No moves needed")
        print(q[6])

if __name__ == "__main__":
    main()