暂无测试数据。

Description

聪明的打字员（clever）

　　阿兰是某机密部门的打字员，她现在接到一个任务：需要在一天之内输入几百个长度固定为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号位置上。当巧妙地使用上述六个特殊键之后，可以得到目标密码，这时光标允许停在任何一个位置。
　　现在，阿兰需要你的帮助，编写一个程序，求出录入一个密码需要的最少的击键次数。

Input

　　输入文件（clever.in）
　　文件仅一行，含有两个长度为6的数，前者为初始密码，后者为目标密码，两个密码之间用一个空格隔开。

Output

　　输出文件（clever.out）
　　文件仅一行，含有一个正整数，为最少需要的击键次数。

Sample Input

123456 654321

Sample Output

11

Limitation

1s, 655360KiB for each test case.

Hint

　　样例说明：
　　初始密码是123456，光标停在数字1上。对应上述最少击键次数的击键序列为：

　
　　最少的击键次数为11。

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

从noi2001两道题看最优化问题BFS与DFS算法的优化

福州一中 林元

【摘要】

　　关于最优化问题的搜索算法优化，下面以NOI2001的两道题为例分别分析。
　　从Clever一题看BFS算法的优化。由于约束条件复杂，我们很难找到好的启发式搜索方法，所以可以确定这题要用BFS算法来解决。状态的过多不但造成了空间的浪费，由于状态数多往往是搜索树节点分支过多造成的，BFS算法的速度也要受到极大的影响。新的状态表示只有区区276480种状态，使用hash表就能够很圆满地解决了。
　　BFS优化总结。相对于DFS来说，BFS更强调理论上的状态总数，对于实际搜索时的状态总数要求不高。最后，BFS算法的一个很大速度依赖来自状态标记数组。在状态能够装得下的条件下，利用快速的数组或hash表访问来提高BFS的速度必不可少。
　　从Cannon一题看DFS算法的优化。对于DFS算法，由于只要求最优解，最重要的优化办法就是定界。剪枝在本题的解决中并未起到最大的作用，但是对于任何一道DFS题不剪枝都将是失败的，所以我们还是需要对本题进行剪枝。众所周知，局部搜索的复杂度相对于全局搜索极小，符合我们的要求。
　　DFS优化总结。从上面的分析可以看出，DFS算法由于其本身的特点，在空间上没有太大的要求，优化主要集中在时间压缩方面。预处理也是DFS算法优化的一个重要方面。

【关键字】
　　最优化问题，BFS，DFS，NOI，状态表示，hash表，队列，搜索树，剪枝，分支定界，局部搜索，预处理，无后效性，时间复杂度，空间复杂度。

【概述】

　　最优化问题在现实生活中意义很大。但由于这些问题的规模往往较大，无法人工解决，常需要借助于计算机程序。在竞赛中，为了较全面地考察选手的素质，最优化问题也经常出现。由于最优化问题没有固定的解法，所以它对选手的分析能力与算法能力都有很高的要求。
　　最优化问题最完美的解决方法当然是将指数级复杂度的工作量降到O（n^p）（p为常数）内。比如经典的动态规划算法、网络流算法、贪心算法等等。但是还有许多最优化问题无法用这些高效率算法解决，或者在赛场上由于时间或其他方面的限制选手无法在特定环境下找到套用这些算法的正确途径，这是搜索算法就成为了正确解决问题的唯一工具。众所周知，搜索算法实际上是穷举所有可能的状态以得到最优解的"笨"算法，伴随着的往往是令人无法忍受的时间或空间复杂度。这时就需要选手举有很强的优化能力，利用强有力的剪枝等技术在不牺牲正确性的条件下提高搜索的效率，以在较短的时间、较小的空间内解决问题。
　　搜索算法主要有BFS与DFS两种，即广度优先搜索与深度优先搜索。两种搜索算法的特点各不相同，优化的角度也各不相同。下面以NOI2001的两道题为例分别分析。

【从Clever一题看BFS算法的优化】

　　BFS算法又称广度优先算法，是按层扫描搜索树来得到最优解的搜索算法。代表题目如NOI2001的Clever。

〖题目描述〗
　　给出一个六位数，要求对其进行最少的操作后得到一个新的给出的六位数。一次操作可以是以下六种操作中的一种：将光标（表示六个数字中当前被操作的数的位置）向左或右移动一位；将首数与光标所在的数交换且光标位置不变；将尾数与光标所在的数交换且光标位置不变；将光标指向的数加1或减1。
　　输入原始六位数与目标六位数，输出最少的操作次数。设开始时光标在最左边，操作结束时光标允许在任意位置。

〖基本算法〗
　　本题是典型的搜索题，因为约束条件复杂多样，很难存在什么好的贪心算法；而且存在交换操作，也不存在无后效性与最优子结构性质，无法用动态规划来解决。在这种情况下，我们当机立断地选择了搜索算法。
　　仔细分析一下本题状态数，数字的可能性有10^6种，还有光标的6种可能，共6000000个状态，如果选择DFS算法，在出第一个解之前，我们根据什么决定搜索的深度呢？？总不能说，所有状态都访问过了，所以不搜了--那么搜索深度至少有30000层啊。由于操作复杂，我们也很难找到好的启发式搜索方法，所以可以确定这题要用BFS算法来解决。

　　进一步，由于本题的操作具有明显的可逆性，可以考虑使用效率更高的双向搜索。双向搜索的数据结构与算法流程如下：
　　1．初始化；
　　　分别建立2个空队列A与B，将原始状态（光标置于1）入队A，目标状态下对应光标的6个位置的6种不同末状态入队B。在内存允许的情况下，建1个记录状态是否被2个队访问过的标记数组（每个状态只需要2bit的存储空间），并分别为队A与队B内的状态做标记。清初始步数p为0。
　　2．如果队B内的新状态未被队A访问过，将p加1，扩展BFS搜索树A；
　　　对队A内现在head到tail的所有状态扩展下一步，如果未与前面A内出现过的状态重复，则依次加入到tail后面。完成后将head指向tail后一位，tail指向队尾。另：新状态即队内head到tail的所有状态。
　　3．如果队A内的新状态未被队B访问过，将p加1，扩展BFS搜索树B；否则到第5步；
　　　扩展搜索树B的算法参见第2步。
　　4．回到第2步；
　　5．打印p并结束程序。
　　经测试可以发现，虽然双向搜索可以在题目要求的时间内出解，但是速度极慢，而且空间占用极大，普通的Pascal IDE根本无法满足程序的内存需求。虽然可以进行优化，但无论怎样也无法从根本上改善双向搜索算法的效率。连效率高过BFS算法数倍的双向搜索都如此，看来本题使用普通的搜索架构是无法解决的。我们必须建立一种新的搜索方式。

〖算法优化〗
　　容易看出，本题的状态数太多是造成BFS算法与双向搜索算法效率低下的罪魁祸首。状态的过多不但造成了空间的浪费，由于状态数多往往是搜索树节点分支过多造成的，BFS算法的速度也要受到极大的影响。要提高算法的效率，如何压缩状态是最大的关键。事实上，状态的压缩就是对题目的搜索约束条件的合理简化。所以，我们首先必须对6种操作有一个充分的认识，然后考虑以下的优化。
　　一个简单的剪枝是：对于1个原始数，我们要不不改变它的值--即不对它进行Up或Down操作，要不只改变一次，这一次是指若干次连续的Up或Down操作，此次操作后再也不对它的值进行改变。这个剪枝是很容易想到的，但是作用不够大，因为如果一个数还没有改变过，那么我们在每一次光标移动到它上面是都要决定是否改变，改变成什么值。而且上面的判断会给搜索造成巨大的麻烦，直接后果就是程序难写，痛苦的反复检查大大降低了原本就很慢的速度。

　　那么，在这个剪枝上我们真的没有文章可做了吗？？不是的。再深入地思考一下，我们会发现原来Up与Down操作在整个操作过程中的顺序是无关紧要的。如果在最优方案中某个原始数的值有改变，我们只要保证在最后一次光标停止在它上面的时候一次性进行Up或Down操作，将其变为目标状态中对应的数就行了。这样，我们实际上在一开始就"瞄准"了每一个数最后的位置与大小，我们所要做的就是在该改变大小的原始数均有被光标访问过的前提下将原始的123456的位置关系变为我们"瞄准"的位置关系就行了。比如说将数456789变成987654，最优方案实际上可以描述为：开始"456789"的位置关系被固定地表示为123456，即"4"是第1个数，"5"是第2个数，……最终的"987654"的位置关系为563421，即"9"是原来的第5个数"8"，"8"为原来的第6个数"9"，"7"为原来的第3个数"6"，"6"为原来的第4个数"7"，"5"为原来的第2个数"5"，"4"为原来的第1个数"4"。这样除了最后在第5、6位上的"5"、"4"外，最终数的前4位都经过了变化，即要求光标必须曾经访问过原来的第5、6、3、4个数。
　　现在，我们又有了一个新的状态表示方案：P_XXXXXX_??????。P表示光标的当前位置，XXXXXX表示现在的状态相对于原来6个数的位置关系，??????是一个二进制数，反映当前状态每个位置上的数是（1）否（0）被光标访问过。举个例子，原始状态被固定地表示为1_123456_100000，经过以下2个操作（Right，Swap0）后变成2_213456_110000。大家可以看到，这种状态表示方法忽略了Up与Down操作。这是因为一旦"瞄准"了最终状态，Up与Down操作的最少总次数就已经定了，不需要我们在状态表示中赘述。
　　现在算一算状态数吧：P有6种可能，XXXXXX是6的全排列，共P（6，6）=720种可能，??????是六位二进制数，共2^6=64种方案。状态总数为6*720*64=276480，不到原来状态数的二十分之一！！不要忘记，由于光标访问过的数是有增无减地，所以二进制数??????中1的个数至少是1，随着搜索的进行有增无减，所以实际上有可能出现的状态数只有5605种！！这样，我们只需要用1个BFS算法就能够在不到1s的时间内算出原始状态到所有状态的最短距离了！！而这里却不能使用双向搜索，因为光标访问过的位置的变化是不可逆的。至于这区区276480种状态的标记数组的存储，使用hash表就能够很圆满地解决了。

　　最后，我们来研究最优解的确定。我们知道，目标六位数与原始六位数对应的位置关系只有P（6，6）=720种。而对于每种对应关系，除了光标位置有6种外，由于每个原始数的最终值都确定了，它们的Up或Down的最短编辑距离也就确定了，剩下的就是满足该改的数必须被光标访问过这一条件。其实这很简单，无非是求所有制定的位为1的六位二进制数，复杂度为O（n）。这样，我们用几重循环就能检查目标六位数所可能对应的所有末状态，而检查的过程只不过是对一个hash表的某个制定元素返回值取min，复杂度为O（n）。这样的检查，相对于全面的BFS来，其时间是远远不能相比的。
　　按照此优化重写的程序，速度固定在CII800+fp的1s左右，大大低于题目要求的时限。而且空间占用小，甚至有可能使用640K的内存就能放下（以速度为代价放弃标记数组或按位压缩hash表），时空比俱佳。本题得到了圆满地解决。
　　那么，为什么这样的优化能大大提高算法的效率呢？？很重要的一个原因，就是由于Up与Down操作的剥离，每个节点的分支数从原来的6个减少到了现在的4个，大大缩小了搜索树的体积，提高了速度。还有一点，剥离Up与Down操作也是搜索层数减少了，又大大压缩了搜索树，提高了程序效率。

〖BFS优化总结〗
　　从上面的例子中我们可以看到，BFS算法并非总比不上双向搜索。它具有更大的优化空间，不像双向搜索编程繁琐，优化的空间不大。BFS的优化主要集中在压缩状态与分离约束条件上，hash表是BFS经常使用的优化策略。相对于DFS来说，BFS更强调理论上的状态总数，对于实际搜索时的状态总数要求不高。最后，BFS算法的一个很大速度依赖来自状态标记数组。在状态能够装得下的条件下，利用快速的数组或hash表访问来提高BFS的速度必不可少。
另外，减少每个状态节点的分支是搜索优化中必不可少的一环，不论BFS还是DFS都一样。下面我们再从NOI2001的另一道题Cannon来看看这个优化的重要性。

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

Source

GZOJ 1544