4

我正在尝试解决以下练习（取自“算法设计手册”）

我们希望计算使用两根手指在标准按键电话上拨打给定 n 位数号码的最懒惰方式。我们假设两根手指从 * 和 # 键开始，并且手指从一个按钮移动到另一个按钮所需的努力与它们之间的欧几里得距离成正比。设计一个算法来计算拨号方法，该方法涉及移动手指的最小总距离，其中 k 是键盘上不同键的数量（对于标准电话，k = 16）。尝试使用 O(nk^3) 时间

首先，让 d=d1.d2....dn be the n-digit sequence

我提出的算法使用两个二维（nxk）数组 L,R

- L[a][b]:min cost to type the d[a]-digit with  the left finger and having
   the right finger at button b
 - R[a][b]:same thing but with right and left instead.

为了填充这两个数组，我使用了两个几乎相同的递归函数（因此我只会为 L 发布一个）

首先，

- L[a+1][b]=L[a][b]+cost_from_d[a]_to_d[a+1]

也就是说，我们将右手手指放在按钮上，左手手指从 d[a] 移动到 d[a+1]

然后，如果 b==d[a]（即用右拨的最后一位数字），那么还存在其他“正确”方式，以便通过将右手手指放在 d[ 上来用左手指键入 d[a+1] a] 按钮，然后将左手指从任何位置移动到 d[a+1]。

 - L[a+1][b]=min(L[a+1][b],min(R[a][c]+cost_from_c_to_d[a+1]),)

为此，我首先找到最低成本，以便我们用左边拨 d[a+1] 用右边拨 d[a]。然后我将它与上子弹的值进行比较并保持最小值。

填充数组后，只需找到最小 L/R[n][whatever] 即可找到最小成本

对我来说，这段代码似乎是正确的。然而，考虑到时间复杂度只有 O(nk) 而不是 O(nk^3)，我肯定犯了一些错误......

有没有人知道这些错误在哪里？

4

1 回答 1

1

您对部分解函数（L 和 R）的定义看起来很合理。你的递归关系可能正确也可能不正确——表达式很难理解。尝试整理并扩展理由。你确定你考虑过所有的手指路径吗？前一个键可能是用任何一只手键入的。

一个品味问题：我喜欢对每个集合的元素使用连续的字母组（比如 i 和 j 表示时间，a 和 b 表示键）。使算法更易于阅读。

啊哈！您的递归关系错过了一些路径（同时移动两个手指）。

定义：（和你的一样）

设d[i]为要拨打的电话号码的第 i 个键。

定义L(i, x)为左手指在键 d[i] 结束，右手手指在键 x 结束的第 i 个键的最小成本。

定义R(i, y)为最小成本...右手手指在键 d[i] 结束，左手指在键 y 结束。

递归关系：

L(i+1, x) = min of all

用左手指键入前一个键的路径。右手手指可能在任何键 w

L(i, w) + dist(d[i], d[i+1]) + dist(w, x)
        # left distance      # right distance

用右手手指键入前一个键的路径。左手指可能在任何键 y 上。

R(i, y) + dist(y, d[i+1]) + dist(d[i], x)
          # left distance   # right distance

（类似的关系也适用于函数 R）

那么为什么我们要考虑同时移动两个手指呢？假设三角不等式，除了打字，最佳表盘永远不会移动手指。但是我们需要它来计算我们的部分解决方案。

回顾一下，部分解函数的选择决定了算法。上面，我们被迫考虑从未以最佳解决方案结束的路径。

观察：假设三角不等式，存在一个最佳拨号，其中手指除了打字外从不移动。证明：给定一个手指移动但不打字的拨号，我们可以通过“懒惰”并在需要打字时移动它来降低（或保持相同）成本。

所以

将 j < i <= n定义L(i, j)为在左手键入第 i 个键并且右手最近用于键入第 j 个键的情况下键入前 i 个键的最佳成本。

j < i 的复发

L(i+1, j) =

从 j < i 我们知道左手输入了第 i 个键

L(i, j) + dist(d[i], d[i+1])

其他复发。

L(i+1, i) = min of all

从 j = i 我们知道右手键入了第 i 个键。（以前用左手输入第 k 个键）

R(i, k) + dist(d[k], d[i+1])    over all k < i

哼，看起来像你原来的算法！：/ 这是怎么回事！

于 2013-10-22T18:52:23.103 回答