递归路径计数

Question

例如，如果我有给定的指令，我会尝试使用递归函数来计算路径

instructions = {
 1: (('bot', 3), ('bot', 4)), 
 2: (('bot', 4), ('output', 0)), 
 3: (('output', 5), ('bot', 5)), 
 4: (('bot', 5), ('bot', 6)), 
 5: (('output', 1), ('bot', 7)), 
 6: (('bot', 7), ('output', 4)), 
 7: (('output', 2), ('output', 3))
}

`

如下图所示

​

在这个示例中，有来自bot 5 (5-1, 5-7-2, 5-7-3)的3路径。有来自bot 4 (4-5-1, 4-5-7-2, 4-5-7-3, 4-6-7-2, 4-6-7-3, 4-6-4)的6路径。

这就是我到目前为止所做的尝试，但没有成功。

def count_path(bot, instructions):
    counter = 0
    b = "bot"
    outp = "output"
    while True:
        for x, y in instructions[bot]:
            if x == b:
                count_path(y, instructions)
            elif x == outp:
                counter += 1
    return counter

Answer 1

为了清楚起见，我将名称从bot更改为node -表示向前连接到其他点的点，并将输出更改为end -表示不向前连接的点

instructions = {1: (('node', 3), ('node', 4)),
            2: (('node', 4), ('end', 0)),
            3: (('end', 5), ('node', 5)),
            4: (('node', 5), ('node', 6)),
            5: (('end', 1), ('node', 7)),
            6: (('node', 7), ('end', 4)),
            7: (('end', 2), ('end', 3))}

def count_path(current_node, instructions):

    connections = instructions[current_node]

    paths = 0

    for connection in connections:

        if connection[0] == "node":
            paths += count_path(connection[1])
        elif connection[0] == "end":
            paths += 1

    return paths

基本上，递归的工作原理是检查连接到当前点的点是"node"还是"end"，如果它们是节点，则创建新的堆栈(即。函数被再次调用)，但是从连接到新的当前节点的节点开始，它然后检查连接到新节点的那些点是否也是节点。

这将一直持续到到达"end"为止。发生这种情况时，会将它的1添加到paths中。将当前堆栈中到达的路径数返回给上面的堆栈。

递归可能很难可视化，但本质上，当您到达端点并沿堆栈向上移动时，您将返回该方向上的端点总数，因此顶部堆栈将返回端点总数(相当于路径总数)。

Answer 2

您需要添加count_path的返回值并移除while = true。

def count_path(bot, instructions):
counter = 0
b = "bot"
outp = "output"
for x, y in instructions[bot]:
    if x == b:
        counter += count_path(y, instructions)
    else:
        counter += 1
return counter

在递归中，你有一个基本情况，在你的例子中是当你遇到死胡同时，也就是output元素。

假设你在bot a，如果下一个元素是bot b，那么

no. path from bot a += no. of paths from bot b

否则，如果下一个元素是输出，则添加1，因为这是您正在计数的路径之一的终止。

Answer 3

这是一个简单但有效的解决方案。然而，它只计算路径，而不收集它们。

instructions = {
 1: (('bot', 3), ('bot', 4)),
 2: (('bot', 4), ('output', 0)),
 3: (('output', 5), ('bot', 5)),
 4: (('bot', 5), ('bot', 6)),
 5: (('output', 1), ('bot', 7)),
 6: (('bot', 7), ('output', 4)),
 7: (('output', 2), ('output', 3))
}

def count_paths(bot):
    n_paths = 0
    entry = instructions[int(bot)]
    for path_type, bot_number in entry:
        if path_type == 'output':
            n_paths += 1
        elif path_type == 'bot':
            n_paths += count_paths(bot_number)

    return n_paths


if __name__ == '__main__':
    bot = input("Count path for: ")
    paths = count_paths(bot)
    print("For bot {bot} there are {paths} paths".format(bot=bot, paths=paths))