用最少的步数打开锁

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

第五个案例，目标为zzzzbzzzz:

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

- Leonardo

---

你想要什么不够清楚吗？你在寻找一个算法吗？ - BraveNewCurrency

为什么zzzzbzzzz需要三步才能到达？不能用aaaaaaaaa => zzzzzzzzz => zzzzbzzzz（2 步）的方法吗？ - John Dvorak

@JanDvorak：我认为中间的 z 首先回到 a。 - jxh

为了澄清您的问题，我进行了一些编辑，并考虑了上面的评论，增加了一些示例。如果有任何不正确的地方，请编辑它。 - Rubens

我认为这个问题足够有建设性，可以重新开放回答。它是一个编程问题，正确地被标记为“算法”，虽然一开始的表述有点混乱，但我真的认为当前的版本已经简明扼要，可以接受回答。 - Rubens

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所指出的那样，这个解决方案，就其提出的方式而言，并不是最优解。对于目标字符串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'）之间的差异。

- Rubens

---

好的回答！我有一个问题：是否存在必须将轮子旋转到相反方向的情况？例如：当一个 d 应该变成一个 e 以解决最小步骤的问题时。或者，我认为这是同样的问题：如果一个轮子显示 a，是否存在我们应该更改它的情况？您的第一个示例可以在将 zzzz 序列旋转而不是将 a 旋转到 z 的情况下在3个步骤中解决。稍后我会尝试制作一个棘手的目标字符串并发布它，如果您不介意的话。 - user1300630

@Rubens 谢谢您。我会尝试递归实现，并将结果保存在表中，以满足动态规划的要求。顺便说一下，我们在同一所大学学习过。 - Leonardo

在你的zzzzbzzzz示例中，我不明白为什么你把zzzzazzzz移到了zzzzzzzzz。我知道这样可以一次性将整个字符串移动到a，但这是更复杂的逻辑。我认为一旦一个字符在正确的位置上，就不应该再动它，这意味着zzzzbzzzz -> zzzzazzzz -> aaaaazzzz -> aaaaaaaaa将是操作序列，这也需要3步移动。这种逻辑更简单，仍然可以最优地得到答案（即使z是其他字符，比如w，两种方法所需的步数相同-9）。 - SirGuy

@Rubens，我喜欢你把问题转化并考虑将字符串转换为a的问题，这使得思考更容易。然而，将字母表分成两部分，将下半部分向下转动，将上半部分向上转动，并不总是会产生最优解。想想那些字母接近字母表中间的字符串。作为一个简单的例子，我们可以考虑字符串mn，在这里很明显我们不应该将m向上转动，将n向下转动，我们应该使用一次移动将它们组合起来，然后将它们一起移回到aa。 - user1884905

@gkovacs90，抱歉我只有这些案例。 - Leonardo

Answer 2

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

我还使用了Rubens的反向思路。

因此，我认为没有必要将a旋转到其他东西。如果这是正确的（我没有反例），则没有情况需要将某些东西旋转到错误的方向（我没有数学证明，但这可能是正确的）。

因此，每个U和D的子序列都会随着一个动作每次旋转一次。该算法不会花费O(n^2)的时间。以下是算法：

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

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

此算法将使每个轮子旋转到a，并且最多经过k/2次扫描后就完成了，其中k是字母表元素的计数，因此这可能是线性时间运行的解决方案。

---

也许有一种解决方案可以进行更少的操作。这只是一个想法，通过查找递增，递减或“山形”子序列并提取最大值来实现。例如：我们可以说，不需要计算，解决以下问题的成本相同

• abcde,
• ecb,
• abceeddcb

等于解决单个e的成本

编辑：我看到了user1884905的反例。因此，我的算法将无法找到最优解，但它可用于找到正确的算法，因此我尚未删除它。

第二次编辑：另一个适用于示例目标字符串的想法：可以计算出平均字母。它是字母距离目标字符串字母之和最小的字母。每个字母都应在此处使用上面的算法旋转，然后可以将整个字符串旋转到aaaaaaaaaa。由于字母表是循环的，因此可能会有多个平均字母（例如问题中的第二个示例），在这种情况下，我们应选择距离a最小的那一个。

- user1300630

---

根据我发布的答案中的评论，我的方法存在一些特殊情况（例如mn），按照我提出的步骤并不能得到最优解。请尝试运行此用例以及其他一些用例，使用您的算法，以便我们可以得到正确的答案。至于第二部分，我实际上是在尝试通过那个规范化过程来达到一些重叠情况，以使解决方案更加动态。 - Rubens

@Rubens 我在考虑尽可能朝一个方向旋转，并计算该部分的旋转次数。例如，abcxyz，bc我会向上旋转，然后向下旋转xyz。我想使用快速排序或其他算法对我需要向上或向下旋转的序列进行排序，并将计算出的值存储在表中。这将是动态规划吗？一个子问题是尝试尽可能朝一个方向旋转吗？ - Leonardo

在动态规划中，子问题通常是一些已经计算过的内容，你不需要再次计算，因为你已经有了它的结果。我并没有真正理解你的想法：你不会打破最初的顺序限制来排序这个序列吗？ - Rubens

我找到了关于动态规划的解释，链接为http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=dynProg。我打算通过类比来解决问题。我想用旋转上下的次数代替硬币。我不知道这是否正确，但我会尝试一下。 - Leonardo

@gkovacs90 向上或向下的更大旋转可以解释为最优子结构吗？ - Leonardo