Estoy escribiendo código python implementando dfs pero no puedo hacerlo funcionar correctamente. Aquí hay un ejemplo estúpido usando dfs para ver si word podría estar formado por 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",""))

Aquí mi lst es ["a", "b"] y obviamente podría formar "ba". Sin embargo, devuelve False. Obtengo el resultado de la palabra que formó cada vez por print(gen):

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

Y pude ver ba en el resultado, entonces, ¿no debería el programa detener la recursión y devolver True una vez que se encuentre con ba? ¿Qué tiene de malo mi código?

0
RioAraki 10 sep. 2018 a las 02:56

3 respuestas

La mejor respuesta

El problema está aquí:

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

Una vez que se encuentra la palabra, devolverá True, pero la persona que llama ignorará el valor True devuelto y terminará generando todas las palabras y devolviendo False en cualquier caso.
Solo necesita agregar un cheque para devolver True cuando encuentre la coincidencia.

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

Además, moviendo alguna línea, su función se puede escribir de una manera más concisa como:

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"))
1
abc 10 sep. 2018 a las 00:42

Debe verificar la salida de la función dfs (if dfs(word, gen+i):), es decir:

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
0
Pedro Lobito 10 sep. 2018 a las 00:17

El programa no "detiene la recursividad" a menos que return de cada función en la pila. 1

Y no estás haciendo eso. No importa lo que devuelva la llamada recursiva a dfs, simplemente ignórela y continúe con su ciclo:

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

... y luego se caen al final del ciclo y la declaración if y:

return False

Por lo tanto, esas llamadas recursivas no tienen ningún efecto, excepto perder el tiempo de la CPU. La única forma en que puede devolver cualquier cosa que no sea False en cualquier nivel es if gen == word: en ese nivel. Entonces, cuando eso no es cierto en el nivel superior, siempre devuelve False.


La solución es simple: cuando una de las llamadas recursivas devuelve True, también desea devolver True: el valor se encuentra si coincide con gen, o si se encuentra en profundidad -primera búsqueda en gen+'a', o si se encuentra en una búsqueda profunda primero en gen+'b'. Entonces:

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

Ahora solo continúa el ciclo y se cae al final si ninguna de las llamadas de respuesta es verdadera.


1. A menos que plantee una excepción no controlada.

0
abarnert 10 sep. 2018 a las 00:18