最短的鍵盤距離打字

任何人都可以幫我解決這個問題嗎？例如，我們有一些來自某個特定aplhabet的MxN字符網格，S = {A，B，C，D}。光標定位在（1,1）的位置，並且我們可以使用箭頭鍵移動光標，了，下來，離開，右，並按回車鍵選擇字符（就像在舊遊戲中選擇暱稱）。給定一些來自aplhabet S的輸入字符串，它們加權相同的最小操作成本是多少（例如，向右移動與選擇char相同的代價）？在矩陣中也可以有多個相同字符的出現。最短的鍵盤距離打字

實施例：

字母S = {A，B，C，d}

矩陣：

ABDC CADB ABAA

和輸入字符串ADCABDA。

我的不完整的解決方案是：構建定向網格圖並找到從1,1到結束字符的最短路徑，其中間字符與TSP中的城鎮相似，並且來自最優子路徑使用動態規劃構建最優最終路徑。問題是你可能會結束許多可能的結束字符，而我完全不知道如何從較小的最佳子路徑構建更長的最佳路徑。

來源

2015-04-12 martinerk0

你應該建立一張圖表的節點是這樣的：

 
     A1   A1   A1 
     A2 D1 C1 A2 B1 D1 A2 
Start A3 D2 C2 A3 B2 D2 A3 End 
     A4   A4 B3  A4 
     A5   A5   A5

哪裏有下一列列中的每個節點連接到每個節點的邊緣。 Start是(1,1)和End是任何地方。邊權重是每對密鑰之間的「出租車」距離。

現在這是一個相當直接的動態規劃問題。你可以從任何一端開始;從Start開始在概念上可能更簡單。跟蹤到達每個節點的最低成本。

來源

2015-04-12 22:01:23

您可以使用3D動態編程，其中每個狀態是表示當前位置的（x，y，l） - （x，y），l表示您所處的字母。

進一步解釋。你從位置（0，0，0）開始。第一個字母是「A」。你可以嘗試所有的A，我們知道距離將是曼哈頓距離（http://en.wikipedia.org/wiki/Taxicab_geometry）。（0，0，0）的解決方案將是所有可能性中的最小值。

在每一步重複上述過程。請注意，記住每一步的重要性。在下面的示例代碼備註中充當函數，您可以在實際中使用數組。

下面是示例僞代碼：

f(x, y, l): 
    if memo(x, y, l) != -1: 
    return memo(x, y, l) # Check if already calculated. 
    if l == length(word): 
    return memo(x, y, l) = 0 # Ending condition. 

    memo(x, y, l) = inf 
    next_letter = word[l] 
    for each (x2, y2) in grid that contains next_letter: 
    distance = |x2 - x| + |y2 - y| 
    next_calc = f(x2, y2, l+1) 
    memo(x, y, l) = min(memo(x, y, l), distance + next_calc) 

    return memo(x, y, l) 


Set all memo to -1, so we know that no states are calculated. 

Solution is f(0, 0, 0).

讓我知道哪些步驟，我需要進一步明確。

來源

2015-04-13 08:36:19 Riko

最短的鍵盤距離打字

回答

相關問題