如何更正此 python dfs 搜索？

Question

我正在编写 python 实现 dfs 的代码，但我无法使其正常工作。这是一个愚蠢的例子，使用 dfs 查看 word 是否可以由 lst:

组成

def dfs(word, gen):
    print(gen)
    if len(gen) <= len(word):
        if gen == word:
            return True
        lst = ["a","b"]
        for i in lst:
            dfs(word, gen+i)
    return False

print(dfs("ba",""))

这里我的 lst 是 ["a", "b"] 显然可以形成 "ba"。然而它 returns 错误。我得到它每次形成的单词的输出 print(gen):

a
aa
aaa
aab
ab
aba
abb
b
ba
bb
bba
bbb

并且我可以在结果中看到 ba，所以程序是否应该停止递归并且一旦遇到 ba 就 returns True？我的代码有什么问题？

Answer 1

问题出在这里：

for i in lst:
    dfs(word, gen+i)

一旦找到单词，它将 return True，但调用者将忽略 True 值 returned，您最终将生成所有单词在任何情况下 returning False。
当您找到匹配时，您只需要添加一个检查以 return True。

for i in lst:
    if dfs(word, gen+i):
        return True

此外，移动一些行，您的函数可以更简洁地编写为：

def dfs(word, gen):
    if len(gen) > len(word):
        return False
    elif gen == word:
        return True
    else:
        return any(dfs(word, gen+i) for i in ("a","b","c"))

Answer 2

您需要检查 dfs 函数 ( if dfs(word, gen+i): ) 的输出，即：

def dfs(word, gen):
    print(gen)
    if len(gen) <= len(word):
        if gen == word:
            return True
        lst = ["a","b"]
        for i in lst:
            if dfs(word, gen+i):
                return True
    return False

print(dfs("ba",""))

a
aa
aaa
aab
ab
aba
abb
b
ba
True

Answer 3

程序不会"stop recursion"，除非你从堆栈上的每个函数return。¹

而你并没有这样做。无论对 dfs returns 的递归调用是什么，您只需忽略它并继续循环：

for i in lst:
    dfs(word, gen+i)

… 然后在循环和 if 语句的末尾掉落并且：

return False

因此，那些递归调用除了浪费 CPU 时间外没有任何效果。在任何级别，除了 False 之外，您可以 return 的唯一方法是在该级别 if gen == word:。所以，当在顶层不是这样时，你总是 return False.

修复很简单：当其中一个递归调用 returns True 时，您还想 return True：如果找到值匹配 gen，或者如果它是在 gen+'a' 的深度优先搜索中找到的，或者如果它是在 gen+'b' 的深度优先搜索中找到的。所以：

for i in lst:
    if dfs(word, gen+i):
        return True

现在，如果递归调用的 none 为真，您就只能继续循环并退出结尾。

_{1.除非你引发未处理的异常。}

如何更正此 python dfs 搜索？

How to correct this python dfs search?

python

algorithm

depth-first-search