Este es el diccionario que estoy usando:

{
    'timar': ['rimar', 'timas'], 
    'lares': ['pares', 'mares', 'laves'], 
    'lomas': ['lamas', 'limas', 'lemas'], 
    'gemas': ['lemas', 'remas', 'gimas'], 
    'lamas': ['lavas', 'latas', 'limas', 'lomas', 'lemas'], 
    'rimar': ['remar', 'timar', 'rimas'], 
    'lavas': ['laves', 'latas', 'lamas'], 
    'rimas': ['rimar', 'remas', 'timas', 'gimas', 'limas'], 
    'lemas': ['lomas', 'lamas', 'remas', 'limas', 'gemas'], 
    'mesas': [], 
    'remas': ['remos', 'rezas', 'remar', 'lemas', 'gemas', 'rimas'], 
    'pares': ['mares', 'lares'], 
    'teñir': ['reñir', 'tañir'], 
    'ceras': [], 
    'regar': ['rogar', 'regir', 'retar', 'rezar', 'remar'], 
    'remos': ['rezos', 'remas'], 
    'moras': [], 
    'regir': ['regar', 'reñir'], 
    'rezar': ['regar', 'rezas', 'retar', 'remar'], 
    'rezos': ['rezas', 'remos'], 
    'broma': [], 
    'lapiz': [], 
    'reñir': ['regir', 'teñir'], 
    'mares': ['pares', 'lares'], 
    'tocas': [], 
    'remar': ['remas', 'regar', 'rezar', 'retar', 'rimar'], 
    'timas': ['timar', 'limas', 'gimas', 'rimas'], 
    'laves': ['lares', 'lavas'], 'tañir': ['teñir'], 
    'bogar': ['rogar'],
    'gimas': ['gemas', 'timas', 'limas', 'rimas'], 
    'latas': ['lavas', 'lamas'], 
    'rogar': ['bogar', 'regar'], 
    'rezas': ['rezar', 'rezos', 'remas'], 
    'retar': ['regar', 'rezar', 'remar'], 
    'limas': ['lamas', 'lomas', 'lemas', 'timas', 'gimas', 'rimas']
}

Y este es el código que estoy usando para encontrar los caminos.

def busqueda(self, start_vertex, end_vertex, path=[]):
    """ find all paths from start_vertex to end_vertex in graph """
    print (start_vertex)
    graph = self.diccionario
    path = path + [start_vertex]
    if start_vertex == end_vertex:
        return [path]
    if start_vertex not in graph:
        return []
    paths = []
    for vertex in graph[start_vertex]:
        if vertex not in path:
            extended_paths = self.busqueda(vertex, end_vertex, path)
            for p in extended_paths: 
                paths.append(p)
    return paths
0
fabian bohorquez 12 dic. 2016 a las 04:12
Así que estás haciendo dfs en el gráfico, por lo general es más fácil hacer esto con una pila. Qué start y end estás usando que entra en un bucle infinito.
 – 
AChampion
12 dic. 2016 a las 04:24
¡Al depurar, intente usar un ejemplo más pequeño!
 – 
Julien
12 dic. 2016 a las 04:25
Lo siento, estoy usando 'mares' y 'tañir' como inicio y final respectivamente
 – 
fabian bohorquez
12 dic. 2016 a las 04:30
¿Está seguro de que está entrando en un bucle infinito? Hay 12012 rutas diferentes a través de su red desde mares a tañir.
 – 
AChampion
12 dic. 2016 a las 04:34

1 respuesta

La mejor respuesta

Encuentro que estos problemas de búsqueda son más fáciles de resolver con una pila que de forma recursiva.
Con gráficos muy conectados, encontrará que el número de caminos aumenta exponencialmente con el número de nodos.

Pero aquí hay una dfs rápida en su gráfico:

def dfs(graph, start, end):
    stack = [[start]]
    while stack:
        path = stack.pop()
        if path[-1] == end:
            yield path
            continue
        for next_state in graph[path[-1]]:
            if next_state in path: # Stop cycles
                continue
            stack.append(path+[next_state])

>>> paths = list(dfs(graph, 'mares', 'tañir'))
>>> len(paths)
12012
>>> paths[0]
['mares', 'lares', 'laves', 'lavas', 'lamas', 'lemas', 'gemas', 'gimas',
 'rimas', 'limas', 'timas', 'timar', 'rimar', 'remar', 'retar', 'rezar',
 'regar', 'regir', 'reñir', 'teñir', 'tañir']
>>> max(paths, key=len)
['mares', 'pares', 'lares', 'laves', 'lavas', 'latas', 'lamas', 'lemas',
 'lomas', 'limas', 'rimas', 'rimar', 'timar', 'timas', 'gimas', 'gemas',
 'remas', 'remos', 'rezos', 'rezas', 'rezar', 'remar', 'retar', 'regar',
 'regir', 'reñir', 'teñir', 'tañir']
2
AChampion 12 dic. 2016 a las 07:40
Bienvenido a stack overflow. Si una respuesta de los campeones resolvió su problema, márquelo como la respuesta aceptada. De esta forma recibe puntos de reputación por sus esfuerzos.
 – 
Nath
12 dic. 2016 a las 05:07
¿Qué pasa si tengo un diccionario muy grande? ¿Cómo puedo encontrar la ruta más larga disponible?
 – 
fabian bohorquez
12 dic. 2016 a las 07:12
max(path, key=len) devolverá la ruta más larga entre el inicio y el final.
 – 
AChampion
12 dic. 2016 a las 07:41
Pero el programa no funciona cuando el diccionario es muy grande
 – 
fabian bohorquez
12 dic. 2016 a las 12:42
Ésta es una forma del problema del viajante y es NP difícil. No existe un algoritmo eficiente para N grandes. Deberá investigar aproximaciones eficientes: en.wikipedia.org/wiki / Problema_de_ruta_mórfica
 – 
AChampion
12 dic. 2016 a las 16:14