难度：提高+/省选-

本文题解改编自洛谷题解第二篇


        在洛谷上看到了一种新奇的解法，记录一下。

题目描述

        设有n个大小不等的中空圆盘，按从小到大的顺序从1到n编号。将这n个圆盘任意的迭套在三根立柱上，立柱的编号分别为A，B，C，这个状态称为初始状态。
        现在要求找到一种步数最少的移动方案，使得从初始状态转变为目标状态。
        移动时有如下要求:

  • 一次只能移一个盘;
  • 不允许把大盘移到小盘上面。

    输入输出格式

    输入格式:

            文件第一行是状态中圆盘总数;
            第二到第四行分别是初始状态中A，B，C柱上圆盘的个数和从上到下每个圆盘的编号;
            第五到第七行分别是目标状态中A，B，C柱上圆盘的个数和从上到下每个圆盘的编号。

    输出格式:

            每行一步移动方案，格式为：move I from P to Q
            最后一行输出最少的步数。

输入输出样例

Sample input

5
3 3 2 1
2 5 4
0
1 2
3 5 4 3
1 1

Sample output

move 1 from A to B
move 2 from A to C
move 1 from B to C
move 3 from A to B
move 1 from C to B
move 2 from C to A
move 1 from B to C
7

说明

        圆盘总数≤45
        每行的圆盘描述是从下到上的圆盘编号。

题解

        题解用了随机数…竟然A了，这应该是和模拟退火算法类似的一种算法。
        易知大盘要在小盘之前就位，否则小盘最终仍要移动。为了得到最简洁的步骤，应从大到小使各个盘子依次就位。但每一个盘子有两种移动方式:直接就位和先移到辅助位再移到目标位。通常前者更优但后者在某些情况下优于前者。
        每个盘子移动时，比其小的盘子不能出现在原位和要移动的位置上，必须全部放到辅助位上。于是事先要先移动较小盘，这是一个递归过程，模拟这个过程即可。
        一个通俗的做法是每一次都同时考虑这两种情况并进行状态转移。这里采用另一种方法—随机数转移。
        每一次使用后一种(见上文)转移方法时都有一定的概率，这个概率随着时间的推移不断减小(这是模拟退火算法的思想)。也就是说用随机数来判别下一次的状态转移方式。这样做显然偶然性太大，可以使这个过程进行更多次(比如500次)，来获得很高概率的正确性。
        随机数转移法将总路径压缩到一定的值，比起朴素盲目搜索算法大大简化了总状态数。但缺点是具有一定偶然性，可以通过参数调整的方法来尽可能地提高正确率。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include<iostream>
#include<queue>
#include<cstdlib>

using namespace std;
int first[46], last[46];
int first2[46], last2[46];
int n, ans = static_cast<int>(1e8);
int ANS[233333], size = 0;
int an[233333];

void mv(int p, int from, int to) {
    if (from == to)return;//就在目标位上,不用动
    for (int i = p - 1; i >= 1; i--)mv(i, first2[i], 6 - from - to);//小盘全移到辅助位上
    ANS[size++] = p * 100 + from * 10 + to;//记录移动步骤
    first2[p] = to;//修改
}

int main() {
    ios::sync_with_stdio(false);
    cin >> n;
    for (int i = 1; i <= 3; i++) {
        int x, y;
        cin >> x;
        for (int j = 1; j <= x; j++) {
            cin >> y;
            first[y] = i;
        }
    }
    for (int i = 1; i <= 3; i++) {
        int x, y;
        cin >> x;
        for (int j = 1; j <= x; j++) {
            cin >> y;
            last[y] = i;
        }
    }
    srand(23333);//随机种子
    for (int g = 1; g <= 500; g++) {
        size = 0;
        for (int i = 1; i <= n; i++)first2[i] = first[i], last2[i] = last[i];//先复制一遍数据
        for (int i = n; i >= 1; i--) {
            if (rand() % (n - i + 2) == 0)mv(i, first2[i], 6 - first2[i] - last2[i]), mv(i, first2[i], last2[i]);//第二种转移
            else mv(i, first2[i], last2[i]);//第一种转移
        }
        if (ans > size) {//获得更优解,记录
            ans = size;
            for (int i = 0; i < size; i++)an[i] = ANS[i];
        }
    }
    for (int i = 0; i < ans; i++)
        cout << "move " << an[i] / 100 << " from " << char(an[i] % 100 / 10 + 'A' - 1) << " to "
             << char(an[i] % 10 + 'A' - 1) << endl;
    cout << ans;
    return 0;
}