如何应用回溯算法？

我做在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

如何应用回溯算法？

回答

相关问题