math - 最短键盘距离打字

Question

谁能帮我解决这个问题？
我们有一个来自某些特定 aplhabet 的 MxN 字符网格，例如 S={A,B,C,D}。
光标位于 (1,1) 位置，我们可以使用箭头键移动光标，向上 , 下 , 左 , 右 , 和 按回车选择角色(就像在旧游戏中选择昵称一样)。给定来自 aplhabet S 的一些输入字符串，在它们权重相同的情况下，操作的最低成本是多少(例如，向右移动与选择字符的成本相同)？矩阵中也可以多次出现相同的字符。

例子:

字母 S={A,B,C,D}

矩阵 :
ABDC
CADB
ABAA
和输入字符串ADCABDA。

我不完整的解决方案是:
构建有向网格图并找到从 1,1 到结束字符的最短路径，中间字符类似于 TSP 中的城镇，并使用动态规划从最优子路径构建最优最终路径。问题是您可能以许多可能的结束字符结尾，而我完全不知道如何从较小的最佳子路径构建更长的最佳路径。

Answer 1

你应该用这样的节点构建一个图:

A1 A1 A1
A2 D1 C1 A2 B1 D1 A2
开始 A3 D2 C2 A3 B2 D2 A3 结束
A4 A4 B3 A4
A5 A5 A5

其中有边将一列中的每个节点连接到下一列中的每个节点。 Start是 (1,1)和 End是哪里。边权重是每对 key 之间的“出租车”距离。

现在这是一个相当简单的动态规划问题。您可以从任一端开始；从 Start 开始可能在概念上更简单.跟踪到目前为止到达每个节点的最低成本。