题解 | #铁盘整理#

题目链接

题目描述

给定一个包含 $N$ ( $1 \le N \le 16$ ) 个不同半径的铁盘的序列，初始时它们是无序堆叠的。我们定义一种操作为“翻转”，即将最上面的 $k$ 个铁盘（ $k \ge 1$ ）作为一个整体进行上下翻转。目标是找到一个操作序列，使得所有铁盘从上到下按半径从小到大有序排列，并要求这个操作序列的长度（即翻转次数）最短。

解题思路

这个问题是经典的“煎饼排序”（Pancake Sorting）问题，寻找最少翻转次数是一个 NP-hard 问题。对于 $N \le 16$ 这样的数据规模，常规的广度优先搜索（BFS）因状态空间过大（ $16!$ 级别）而会导致超时。

正确的做法是使用 迭代加深 A* (Iterative Deepening A*, IDA*) 算法。IDA* 结合了深度优先搜索（DFS）的低内存消耗和 A* 算法的最优性保证。

其核心思想如下：

有界深度优先搜索：我们进行一系列的深度优先搜索。搜索的边界不是递归深度，而是一个总代价的上限 limit。总代价 $f(n) = g(n) + h(n)$ ，其中：
- $g(n)$ 是从初始状态到当前状态已经花费的步数（翻转次数）。
- $h(n)$ 是一个启发函数，用于估算从当前状态到目标状态至少还需要多少步。
迭代加深：
- 我们从一个初始 limit（通常是起点的 $h$ 值）开始搜索。
- 在 DFS 中，如果任何路径的 $f(n)$ 值超过了当前 limit，就立即剪枝。
- 如果该 limit 内未找到解，就用所有被剪枝路径中最小的那个 $f(n)$ 值作为新的、更大的 limit，重新开始搜索。
- 重复此过程，直到找到解。由于 limit 是递增的，且启发函数给出了真实的下界，因此第一个找到的解就是最优解。

启发函数：断点数 (Breakpoints)

对于煎饼排序问题，一个有效的启发函数 $h(n)$ 是计算 “断点” 的数量。一个断点是指当前序列中相邻的两个铁盘，在最终有序序列中并不相邻。例如，序列 ...4, 1... 中，4 和 1 之间就构成一个断点。由于一次翻转最多只能修复一个断点，因此序列中断点的数量是到达目标状态所需步数的可靠下界。

为了方便计算，我们首先对输入的半径值进行离散化，将它们映射到 $1, 2, ..., N$ 的整数，这样目标状态就统一为 (1, 2, ..., N)。

代码

cpp
java
python

#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>
#include <map>

using namespace std;

int n;
vector<int> target_state;
int max_depth;

// 启发函数：计算断点数
int heuristic(const vector<int>& state) {
    int breakpoints = 0;
    // 如果最大的铁盘不在底部，也算一个断点
    if (state.back() != n) {
        breakpoints++;
    }
    for (int i = 0; i < n - 1; ++i) {
        if (abs(state[i] - state[i + 1]) != 1) {
            breakpoints++;
        }
    }
    return breakpoints;
}

// 翻转函数
vector<int> flip(vector<int> arr, int k) {
    reverse(arr.begin(), arr.begin() + k);
    return arr;
}

// 深度优先搜索
// g: 当前已用步数, prev_flip: 上一次翻转的位置，避免无效操作 (A->B->A)
bool dfs(const vector<int>& state, int g, int prev_flip) {
    int h = heuristic(state);
    if (g + h > max_depth) {
        return false;
    }
    if (h == 0) {
        return true;
    }

    for (int k = 2; k <= n; ++k) {
        if (k == prev_flip) continue;
        vector<int> next_state = flip(state, k);
        if (dfs(next_state, g + 1, k)) {
            return true;
        }
    }
    return false;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n;
    vector<int> start_state_raw(n);
    vector<int> sorted_unique(n);
    for (int i = 0; i < n; ++i) {
        cin >> start_state_raw[i];
        sorted_unique[i] = start_state_raw[i];
    }

    // 离散化
    sort(sorted_unique.begin(), sorted_unique.end());
    map<int, int> val_to_rank;
    for (int i = 0; i < n; ++i) {
        val_to_rank[sorted_unique[i]] = i + 1;
    }
    vector<int> start_state(n);
    for (int i = 0; i < n; ++i) {
        start_state[i] = val_to_rank[start_state_raw[i]];
    }

    // IDA* 主循环
    for (max_depth = heuristic(start_state); ; ++max_depth) {
        if (dfs(start_state, 0, 0)) {
            cout << max_depth << endl;
            break;
        }
    }

    return 0;
}

import java.util.*;

public class Main {
    private static int n;
    private static int maxDepth;

    // 启发函数：计算断点数
    private static int heuristic(List<Integer> state) {
        int breakpoints = 0;
        // 如果最大的铁盘不在底部，也算一个断点
        if (state.get(n - 1) != n) {
            breakpoints++;
        }
        for (int i = 0; i < n - 1; i++) {
            if (Math.abs(state.get(i) - state.get(i + 1)) != 1) {
                breakpoints++;
            }
        }
        return breakpoints;
    }

    // 翻转函数
    private static List<Integer> flip(List<Integer> list, int k) {
        List<Integer> newList = new ArrayList<>(list);
        Collections.reverse(newList.subList(0, k));
        return newList;
    }

    // 深度优先搜索
    private static boolean dfs(List<Integer> state, int g, int prevFlip) {
        int h = heuristic(state);
        if (g + h > maxDepth) {
            return false;
        }
        if (h == 0) {
            return true;
        }

        for (int k = 2; k <= n; k++) {
            if (k == prevFlip) continue;
            List<Integer> nextState = flip(state, k);
            if (dfs(nextState, g + 1, k)) {
                return true;
            }
        }
        return false;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        List<Integer> startStateRaw = new ArrayList<>();
        int[] sortedUnique = new int[n];
        for (int i = 0; i < n; i++) {
            int val = sc.nextInt();
            startStateRaw.add(val);
            sortedUnique[i] = val;
        }
        
        // 离散化
        Arrays.sort(sortedUnique);
        Map<Integer, Integer> valToRank = new HashMap<>();
        for (int i = 0; i < n; i++) {
            valToRank.put(sortedUnique[i], i + 1);
        }
        List<Integer> startState = new ArrayList<>();
        for (int val : startStateRaw) {
            startState.add(valToRank.get(val));
        }

        // IDA* 主循环
        maxDepth = heuristic(startState);
        while (true) {
            if (dfs(startState, 0, 0)) {
                System.out.println(maxDepth);
                break;
            }
            maxDepth++;
        }
    }
}

import sys

# 设置足够大的递归深度
sys.setrecursionlimit(2000)

n = 0
max_depth = 0

def heuristic(state):
    """启发函数：计算断点数"""
    breakpoints = 0
    # 如果最大的铁盘不在底部，也算一个断点
    if state[n-1] != n:
        breakpoints += 1
    for i in range(n - 1):
        if abs(state[i] - state[i+1]) != 1:
            breakpoints += 1
    return breakpoints

def flip(arr, k):
    """翻转元组的前k个元素"""
    return tuple(reversed(arr[:k])) + arr[k:]

def dfs(state, g, prev_flip):
    """深度优先搜索"""
    h = heuristic(state)
    if g + h > max_depth:
        return False
    if h == 0:
        return True

    for k in range(2, n + 1):
        if k == prev_flip:
            continue
        next_state = flip(state, k)
        if dfs(next_state, g + 1, k):
            return True
    return False

def solve():
    global n, max_depth
    
    n = int(input())
    start_state_raw = list(map(int, input().split()))
    
    # 离散化
    sorted_unique = sorted(start_state_raw)
    val_to_rank = {val: i + 1 for i, val in enumerate(sorted_unique)}
    start_state = tuple(val_to_rank[val] for val in start_state_raw)
    
    # IDA* 主循环
    max_depth = heuristic(start_state)
    while True:
        if dfs(start_state, 0, 0):
            print(max_depth)
            break
        max_depth += 1

solve()

算法及复杂度

算法：迭代加深 A* (Iterative Deepening A*)
时间复杂度：难以精确分析，因为它高度依赖于启发函数的质量和问题的具体实例。在最坏情况下，它仍然可能需要探索大量的节点。然而，对于煎饼排序问题，一个好的启发函数（如断点数）可以有效地剪枝，使其在实践中远快于朴素的 BFS。其性能通常用有效分支因子 $b^*$ 和解的深度 $d$ 来描述，约为 $O((b^*)^d)$ 。
空间复杂度：由于 IDA* 本质上是深度优先搜索，其空间复杂度由递归栈的深度决定，为 $O(N \cdot d)$ ，其中 $N$ 是铁盘数， $d$ 是最少翻转次数。这与 BFS 的指数级空间复杂度相比是一个巨大的优势。