如何應用回溯算法？

我做在Python過程中的一些excercises，其中一人在那裏我被困低於：如何應用回溯算法？

Given a digit sequence that represents a message where each uppercase letter 
is replaced with a number (A - 1, B - 2, ... , Z - 26) and space - 0. 
Find the number of the initial messages, from which that sequence 
could be obtained. 

Example: 12345 - 3 (ABCDE, LCDE, AWDE) 
     11 - 2 (AA, K)

天真的解決方案是容易的，它是簡單的暴力破解的算法：

import string 

def count_init_messages(sequence): 
    def get_alpha(seq): 
     nonlocal count 

     if len(seq) == 0: 
      count += 1 
      return 

     for i in range(1, len(seq) + 1): 
      if seq[:i] not in alph_table: 
       break 
      else: 
       get_alpha(seq[i:]) 

    alphabet = " " + string.ascii_uppercase 
    # generate dictionary of possible digit combination 
    alph_table = {str(n): alph for n, alph in zip(range(len(alphabet)), alphabet)} 
    # counter for the right combination met 
    count = 0 
    get_alpha(sequence) 

    return count 

def main(): 
    sequence = input().rstrip() 
    print(count_init_messages2(sequence)) 

if __name__ == "__main__": 
    main()

但因爲輸入序列的長度可能長達100個字符，並且可能會有很多重複，所以我遇到了一個時間限制。例如，其中一個示例輸入是2222222222222222222222222222222222222222222222222222222222222222222222 (possible messages number is 308061521170129)。由於我的實現過多重複，處理這種輸入需要很長時間。我想到使用回溯算法，但我還沒有意識到如何實現成功的成果。

如果能夠指出我如何打破這一任務，我會很高興。

來源

2016-10-01 vpetrigo

你必須解決（其中s是一串數字，並a和b爲單數）的遞推關係是這樣的：

S("") = 1 
S(a) = 1 
S(s + a + b) = S(s+a) + (S(s) if ab is between 10 and 26)

可使用動態編程，而不是回溯計算。如果你做得對，它的時間複雜度爲O（1），而O（1）空間複雜度高。

def seq(s): 
    a1, a2 = 1, 1 
    for i in xrange(1, len(s)): 
     a1, a2 = a1 + (a2 if 9 < int(s[i-1:i+1]) < 27 else 0), a1 
    return a1 

print seq('2222222222222222222222222222222222222222222222222222222222222222222222')

來源

2016-10-01 22:38:00

它似乎破壞了'12345'輸入 – Ashot

@Ashot - 謝謝，你說得對。索引被關閉了[[i-1：i]'應該是'[i-1：i + 1]'。現在修復。 –

@PaulHankin，謝謝你的想法，但它不會用於輸入'11101'。你的代碼給出輸出'2'，而我的正確答案是'5'。是否應以不同方式積累總和？ – vpetrigo

查找表中最大的數字是26，因此您永遠不需要查找長度大於2的字符串。相應地修改for循環。這可能足以使暴力成爲可能。

來源

2016-10-01 22:24:13 David

我試圖修復get_alpha函數中的'for'循環，並得到順序不超過兩位數字，但它在這裏不起作用。 – vpetrigo

'seq [：i]'表示「列表直到並不包括'seq [i]'」。例如，當你進入'10'時，程序會產生'seq [1:10]'。只有seq [i]'和seq [i：i + 1]' – David

'如果seq [：i]不在alph_table中似乎是罪魁禍首。嘗試類似'if seq [i]不在alph_table && seq [i：i + 1]不在alph_table：' – David

您可能也已將308061521170129識別爲第71個斐波納契數。這種關係符合斐波那契數列給出了「解決某些枚舉問題的方法，最常見的問題是計算1和2的總和的數目，總和爲n：有Fn + 1種方法可以做到這一點「（https://en.wikipedia.org/wiki/Fibonacci_number#Use_in_mathematics）。

字符串中的每個連續的子序列可以分爲單個或兩個數字代碼，代表了這樣的一個n，其具有多種可能的1s和2s的組合;因此，對於字符串內的每個這樣的子序列，結果必須乘以（子序列的長度+ 1）斐波那契數（在70 2的情況下，我們只乘以第71個斐波納契數）。

來源

2016-10-02 04:05:42

如何應用回溯算法？

回答

相關問題