用最少的移动次数打开锁

Question

考虑一个由轮子系统组成的锁。每个轮子都有26个字母表中的字母，每个轮子都用'a'初始化。如果向上移动一个滚轮，则该滚轮的显示将移动到字母表的下一个字母；另一方面，如果向下移动一个滚轮，则会将显示切换到字母表的前一个字母。例如：

['a'] ->  UP  -> ['b']
['b'] -> DOWN -> ['a']
...
['z'] ->  UP  -> ['a']
['a'] -> DOWN -> ['z']

只需轻拍一下，就可以在同一方向上移动任何相邻的轮子序列。这与以该方式移动子序列的所有轮子具有相同的效果，只需一次运动。例如，如果目标字符串是'zzzzzzzzz'，只需移动一次，将'a'更改为'z'，就会将整个轮子序列从'a'更改为'z'，从而到达目标字符串--打开锁。

如何确定打开锁的最小移动次数？这个问题有没有动态的解决方案？该算法必须产生以下结果：

           Target string         | # moves
   ______________________________ __________
1 | abcxyz                       |    5
2 | abcdefghijklmnopqrstuvwxyz   |   25
3 | aaaaaaaaa                    |    0
4 | zzzzzzzzz                    |    1
5 | zzzzbzzzz                    |    3

案例1，目标abcxyz

aaa[aaa] -> DOWN -> aaazzz
aaa[zz]z -> DOWN -> aaayyz
aaa[y]yz -> DOWN -> aaaxyz
a[aa]xyz ->  UP  -> abbxyz
ab[b]xyz ->  UP  -> abcxyz

案例5，目标zzzzbzzzz

[aaaaaaaaa] -> DOWN -> zzzzzzzzz
zzzz[z]zzzz ->  UP  -> zzzzazzzz
zzzz[a]zzzz ->  UP  -> zzzzbzzzz

Answer 1

这个问题可能会被重述为：

把一个字符串S，变成一个只包含'a‘的字符串的最小移动次数是多少？

定义

将相邻子序列视为字符串中相等字符的序列。最小的邻接子序列自然是单个字符。如果规格化较小的子序列，自然会得到更大的子序列，最终到达单个子序列--整个字符串。

要规范化到的内容

一个人只能向上或向下移动一个角色，所以，一个角色本身就是一个上下移动的序列。字符表示的最坏情况是字母表中间的字母，这至少需要描述len(alphabet) / 2动作。在字母表{a..z}中，最糟糕的情况是'm'和'n'。

因为我们想要最小化移动的数量，所以我们需要拉下字母C <= m，然后拉出这些C >= n。因此，为了最小化归一化过程，我们必须找到需要相等归一化移动的最大子序列。例如，如果我们有一个目标zzzzbzzzz，我们知道最小方向是UUUUDUUUU -- U表示向上，D表示向下。

归一化

对于每次移动，计数器都会递增，从而产生转换字符串所需的最少移动次数。考虑到上面的例子，我们可以采取以下步骤：

# = 0 | zzzzbzzzz | UUUUDUUUU  (choose the smallest subsequence to normalize)
# = 1 | zzzzazzzz | UUUUDUUUU  (since 'a' is the base character, we choose
                              the move that increases the largest subsequence;
                              if 'a' was the first or last character,
                              moving it would simply be overhead)
# = 2 | zzzzzzzzz | UUUUUUUUU  (choose the subsequence to normalize)
# = 3 | aaaaaaaaa | _________  (choose the subsequence to normalize)

另一个示例，使用目标字符串abcxyz

# = 0 | abcxyz | _DDUUU  (choose the smallest subsequence to normalize)
# = 1 | aabxyz | __DUUU  (choose the smallest subsequence to normalize)
# = 2 | aaaxyz | ___UUU  (choose the smallest subsequence to normalize)
# = 3 | aaayza | ___UU_  (choose the smallest subsequence to normalize)
# = 4 | aaazaa | ___U__  (choose the smallest subsequence to normalize)
# = 5 | aaaaaa | ______  (choose the smallest subsequence to normalize)

编辑

正如@user1884905，this solution所指出的，正如所提出的，不是最佳的。在目标字符串mn的情况下，该算法不会导致最优解：

# = 0  | mn | DU  (choose the smallest subsequence to normalize)
# = 1  | ln | DU  (choose the smallest subsequence to normalize)
# = 2  | kn | DU  (choose the smallest subsequence to normalize)
...
# = 12 | an | _U  (choose the smallest subsequence to normalize)
# = 13 | ao | _U  (choose the smallest subsequence to normalize)
# = 14 | ap | _U  (choose the smallest subsequence to normalize)
...
# = 24 | aa | __  (choose the smallest subsequence to normalize)

这并不是最优的，因为以下步骤需要的移动次数较少：

#0    #1    #2    ...    #12
mn -> mm -> ll -> ... -> aa

也许贪婪算法的最优子结构在于减少字符与字符串之间的全局距离，而不是关注字符与基本情况('a')之间的差异。

Answer 2

由于这只是一些额外的信息和一些优化，这应该是对Rubens的答案的评论，但在答案中我可以更好地解释它，它也可以对提问者有用。

我还使用了Rubens这个伟大的反向想法。

因此，我认为不存在需要将a旋转到其他对象的情况。如果这是正确的(我没有反例)，就不存在我们应该将某些东西旋转到错误方向的情况(我没有数学证明，但这可能是正确的)。

因此，Us和Ds的每个子序列都将通过一次运动进行旋转。该算法不需要O(n^2)时间。下面是算法：

让我们将Rubens的字符串称为direction string

1. 将计数器设置为0
2. 计算方向字符串
3. 扫描方向字符串。
4. 如果找到U或D字母的连续子序列，则在朝向a的位置旋转目标字符串并递增计数器(每次执行任何操作时，请返回步骤2

该算法将每个轮子旋转到a，它将在至多k/2扫描之后完成，其中k是字母表元素的计数，因此这可能是一个线性时间运行的解决方案。

也许有一个操作更少的解决方案。这只是一个想法，通过寻找递增、递减或“山形”的子序列并提取最大value.For示例:我们可以说，不需要计算，求解的成本

• abcde，
• ecb，
• abceeddcb

等于求解单个e的成本

编辑：我见过user1884905的反例。所以我的算法不会找到最优解，但它可以用来找到正确的算法，所以我还没有删除它。

EDIT 2:使用样本目标字符串的另一个想法:可以计算出一个平均字母。它是与目标字符串的字母的距离之和最小的一个。用上面的算法在这里旋转每个字母，然后整个字符串就可以旋转成aaaaaaaaaa。由于字母表是循环的，所以可能有多个平均字母(如问题中的第二个示例)，在这种情况下，我们应该选择与a距离最小的一个。