NOI 2001] 聪明的打字员〔搜索〕

2年前发布

[OpenJudge 186/洛谷 P1949/NOI 2001] 聪明的打字员〔搜索〕

题目

总时间限制: 5000ms　内存限制: 65536kB
描述
阿兰是某机密部门的打字员，她现在接到一个任务：需要在一天之内输入几百个长度固定为6的密码。当然，她希望输入的过程中敲击键盘的总次数越少越好。
不幸的是，出于保密的需要，该部门用于输入密码的键盘是特殊设计的，键盘上没有数字键，而只有以下六个键：Swap0, Swap1, Up, Down, Left, Right，为了说明这6个键的作用，我们先定义录入区的6个位置的编号，从左至右依次为1，2，3，4，5，6。下面列出每个键的作用：
Swap0：按Swap0，光标位置不变，将光标所在位置的数字与录入区的1号位置的数字（左起第一个数字）交换。如果光标已经处在录入区的1号位置，则按Swap0键之后，录入区的数字不变；
Swap1：按Swap1，光标位置不变，将光标所在位置的数字与录入区的6号位置的数字（左起第六个数字）交换。如果光标已经处在录入区的6号位置，则按Swap1键之后，录入区的数字不变；
Up：按Up，光标位置不变，将光标所在位置的数字加1（除非该数字是9）。例如，如果光标所在位置的数字为2，按Up之后，该处的数字变为3；如果该处数字为9，则按Up之后，数字不变，光标位置也不变；
Down：按Down，光标位置不变，将光标所在位置的数字减1（除非该数字是0），如果该处数字为0，则按Down之后，数字不变，光标位置也不变；
Left：按Left，光标左移一个位置，如果光标已经在录入区的1号位置（左起第一个位置）上，则光标不动；
Right：按Right，光标右移一个位置，如果光标已经在录入区的6号位置（左起第六个位置）上，则光标不动。
当然，为了使这样的键盘发挥作用，每次录入密码之前，录入区总会随机出现一个长度为6的初始密码，而且光标固定出现在1号位置上。当巧妙地使用上述六个特殊键之后，可以得到目标密码，这时光标允许停在任何一个位置。
现在，阿兰需要你的帮助，编写一个程序，求出录入一个密码需要的最少的击键次数。
输入
仅一行，含有两个长度为6的数，前者为初始密码，后者为目标密码，两个密码之间用一个空格隔开。
输出
仅一行，含有一个正整数，为最少需要的击键次数。
样例输入

123456 654321

样例输出

来源
Noi 01

思路

第一眼：不像是太难的问题，但在 OpenJudge 有半数的五星难度评分，洛谷上还是蓝色 tag.

开始着手：有点像动规，看看样例找思路吧——这是什么鬼样例输入？我怎么无论如何也没法步搞出呢.

怎么办呢——难以偷懒解决的小数据量问题，只好枚举吧.

这是一道搜索好题，也很有难度.

我的解法是一种优化了多次的、有点玄的 IDA* 做法（“玄”是因为它的正确性论述有一部分较琐碎，没想到严格的形式化证明）.

此题的可行状态数太多，搜索树会非常深，我因而考虑用 IDA*.

什么是 IDA* 呢？是一种启发式搜索算法——用估值函数剪枝的迭代加深搜索算法.

什么是迭代加深搜索呢？这是一种设置了递归深度上限的回溯搜索，采用了逐个试验的逻辑寻找最优解（最小的可能深度）. 比如假设最小可能深度为，那么递归时任意分支只要深度超过就剪掉；如果这样没有找到合法解，说明不对，再假定为答案并重新搜，直到找到解.

什么是估值函数呢？这是指在每个状态都估算一下当前状态离目标状态最少还需要几层递归的函数. 很明显，如果 当前深度+估算的值 超过了设定的上限，那么当前的分支也可以直接剪掉. 稍后我们可以发现，估值函数可以起到巨大的优化效果.

因此，我们要做以下两件事：设计搜索算法的逻辑、设计估值函数.

先看看怎么搜索.

主干逻辑是明显的. 此题的一个状态就是当前的位密码以及光标位置，状态间的转移就是一次操作.

但可以想到，每次递归中可以做的剪枝很多，有以下两类：

明显的浪费：如光标在最左边时左移、值为时增加值等.
不必要的修改：可以想象一个位置的值如果此时和目标值一样，就不必做改值/交换操作.

（网络上有剪枝 BFS 题解称左右移操作也可以剪枝，但我测试得到错误答案，没搞懂此题 BFS 的优化逻辑.）

这道题最好玩的是估值函数的设计. 对这个函数的不断优化加深了我对 IDA* 算法的理解.

本题中，估值函数的定义是从一个位密码变化到另一个密码需要的操作数的一个下界. 此外，这个估值效果必须很紧，不然估不出到这种层递归就直接爆炸.

我们把上述的操作数叫做成本，然后把光标移动耗费的叫做移动成本，其它的叫修改成本. 很明显如果跟有位不匹配，那么是移动成本的下界. 关键在于修改成本，我先后使用了三个方式来估计它.

方法一：计算的数字和跟的数字和之差的绝对值 .

其道理是显然的：一次改值操作最多让这个差减小，而交换操作不影响这个差，而我们希望差最终为，所以是正确的下界.

但第一种估计显然是不够用的. 如跟的数字和之差为但修改成本显然比大得多. 稍加观察，我引入第二种估值：

方法二：计算两个密码的直径，其定义为密码的最大三位之和减去最小三位之和，并求出直径之差的绝对值 .

这个方法完美解决了 / 这种情况，因为它反映了两个状态间数据分布的区别.

可以类似第一种估值证明第二种估值是正确的.

验证发现，这两种估计仍然不够用，例如和这种情况下它会炸掉：修改成本应该在左右，但是最好的第一种方案估出来也是，并不理想.

我发挥了点奇思妙想，使用了比较别致的第三种估计：

方法三：先把两个密码升序排序，然后对于里每一位，如果它没在里出现，就求它和排序后 对应项的差的绝对值，结果相加得 .

我的动机是，/ 之所以出状况，就是因为没有被正确处理，它应该跟或求差的绝对值，而不是像第一种方案那样直接减掉本身.

即：这种没有出现在里的数应该拿来求差的绝对值而不是差；而出现在里的数，由于可能有交换操作，交换后可能不需要任何其它修改，故不纳入考虑.

但另一方面，我们也不能直接对应地计算，因为此题存在神奇的交换操作，如果能和交换就会出现更优的 .

这就是我想出这种折衷方案的理由：让比较大的数和比较大的数求差的绝对值，那么一种不错的路子就是对排序后的两个密码里的对应项求差的绝对值.

这样得到的是不是正确的下界呢？不敢说一定是. 但做了一些数学推理后发现，这个估计已经很精了，我有把握说这几乎就是下界. 就算存在 Hack 数据，我们算法的近似度应该也很高.

于是，如果都是修改成本的下界，我们直接取 $max\{C_1,C_2,C_3\}$ 再加上移动成本的下界就完成了估值函数的计算.

就这样，我们的 IDA* 算法设计完了. 代码如下.

#include <bits/stdc++.h>

#define IOS_SPEED std::ios::sync_with_stdio(false)

using std::cin, std::cout;
using std::array;
using std::swap, std::sort, std::abs, std::lower_bound, std::max;

constexpr int len = 6, upper = 9;
array<int, len> code, target, target_o; // xxx_o := 排序后的 xxx
int pos = 0;
int sum_target = 0, diff_target = 0; // sum_xxx := xxx 的数字和, diff_xxx := xxx 的直径

inline int rest_lowerbound(){ // 估值函数
    int answer = 0;
    for(int i=0; i<len; ++i){
        if(code[i]!=target[i]) ++ answer;
    }
    int sum_code = 0, diff_code = 0, dist_sum = 0;
    auto code_o = code;
    sort(code_o.begin(), code_o.end());
    for(int i=0; i<len; ++i){
        sum_code += code_o[i]; diff_code += (i<len/2)? (-code_o[i]): code_o[i];
        auto loc = lower_bound(target_o.begin(), target_o.end(), code_o[i]);
        if(loc==target_o.end()||*loc!=code_o[i])
            dist_sum += abs(code_o[i]-target_o[i]);
    }
    answer += max(max(abs(sum_target-sum_code), abs(diff_target-diff_code)), dist_sum);
    -- answer; if(answer<0) answer = 0;
    return answer;
} // abs(sum_target-sum_code) 即 C_1, abs(diff_target-diff_code) 即 C_2, dist_sum 即 C_3

bool enumerate(int depth, int stop){
    if(depth+rest_lowerbound()>stop) return false;
    if(code==target) return true;
    if(pos>0){
        -- pos; if(enumerate(depth+1, stop)) return true; ++ pos;
    }
    if(pos<len-1){
        ++ pos; if(enumerate(depth+1, stop)) return true; -- pos;
    }
    if(code[pos]>0&&code[pos]!=target[pos]){ // 剪枝
        -- code[pos]; if(enumerate(depth+1, stop)) return true; ++ code[pos];
    }
    if(code[pos]<upper&&code[pos]!=target[pos]){ // 剪枝
        ++ code[pos]; if(enumerate(depth+1, stop)) return true; -- code[pos];
    }
    if(pos>0&&code[pos]!=target[pos]){ // 剪枝
        swap(code[pos], code[0]); if(enumerate(depth+1, stop)) return true; swap(code[pos], code[0]);
    }
    if(pos<len-1&&code[pos]!=target[pos]){ // 剪枝
        swap(code[pos], code[len-1]); if(enumerate(depth+1, stop)) return true; swap(code[pos], code[len-1]);
    }
    return false;
}

int min_presses(){
    target_o = target;
    sort(target_o.begin(), target_o.end());
    for(int i=0; i<len; ++i){
        sum_target += target_o[i]; diff_target += (i<len/2)? (-target_o[i]): target_o[i];
    }
    int attempt = rest_lowerbound();
    while(!enumerate(0, attempt)) ++ attempt;
    return attempt;
}

void interface(){
    IOS_SPEED;
    char new_bit;
    for(int i=0; i<len; ++i){cin >> new_bit; code[i] = new_bit-'0';}
    for(int i=0; i<len; ++i){cin >> new_bit; target[i] = new_bit-'0';}
    cout << min_presses() << "\n"; 
}

int main()
{
    interface();
    return 0;
}

效果拔群！OpenJudge 上用时 4ms（原先没有引入估计方式时超过 2500 ms）；洛谷上以 61ms 成为最快解.

这归功于 rest_lowerbound() 已经对答案给出了很好的估计.

从这个故事中，我们有什么 takeaway 呢？

对大小关系的敏感对于做优化问题极有帮助.
搜索是一类很有技术性的算法.
同一个问题值得反复打磨.
要敢于尝试一些怪点子.
这个打字员确实很聪明.

评分

欢迎为Ta评分