Как исправить этот поиск 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". Однако это возвращает Ложь. Я получаю вывод слова, которое оно каждый раз формирует, с помощью print(gen):

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

и я мог видеть ba в результате, поэтому не должна ли программа прекратить рекурсию и вернуть True, когда она встретит ba? Что не так с моим кодом?

Answer 1

Вам необходимо проверить вывод функции 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 2

Программа не "останавливает рекурсию", если вы не return от каждой функции в стеке. ¹

И ты этого не делаешь. Независимо от того, что возвращает рекурсивный вызов dfs, вы просто игнорируете его и продолжаете свой цикл:

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

… а затем выпадают из конца цикла и оператора if и:

return False

Итак, эти рекурсивные вызовы не имеют никакого эффекта, кроме как тратить процессорное время. Единственный способ вернуть что-либо кроме False на любом уровне - это if gen == word: на этом уровне. Поэтому, когда это не так на верхнем уровне, вы всегда возвращаете False.

---

Исправление простое: когда один из рекурсивных вызовов возвращает True, вы также хотите вернуть True: значение найдено, если оно соответствует gen, или если оно найдено в поиске в глубину на gen+'a', или если он найден при поиске в глубину на gen+'b'. Итак:

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

Теперь вы продолжаете цикл и прекращаете работу только в том случае, если ни один из повторных вызовов не соответствует действительности.

---

_{1. Если вы не создадите необработанное исключение.}

Answer 3

Проблема здесь:

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

Как только слово найдено, оно вернет True, но вызывающая сторона проигнорирует возвращенное значение True, и вы в конечном итоге создадите все слова и в любом случае вернете False.
Вам просто нужно добавить чек, чтобы вернуть 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"))