¿Cómo trazar la ruta en una búsqueda en amplitud primero?

104

¿Cómo se rastrea la ruta de una búsqueda en amplitud, tal que en el siguiente ejemplo:

Si busca una clave 11, devuelva la lista más corta conectando 1 a 11.

[1, 4, 7, 11]
Christopher Markieta
fuente
6
En realidad, era una tarea antigua en la que estaba ayudando a un amigo hace meses, basada en la Ley Kevin Bacon. Mi solución final fue muy descuidada, básicamente hice otra búsqueda de Breadth-first para "rebobinar" y retroceder. No quiero encontrar una mejor solución.
Christopher Markieta
21
Excelente. Considero que revisar un viejo problema en un intento por encontrar una mejor respuesta es un rasgo admirable en un ingeniero. Te deseo lo mejor en tus estudios y carrera.
Peter Rowell
1
Gracias por el elogio, creo que si no lo aprendo ahora, me enfrentaré al mismo problema nuevamente.
Christopher Markieta

Respuestas:

194

Primero debería echar un vistazo a http://en.wikipedia.org/wiki/Breadth-first_search .


A continuación se muestra una implementación rápida, en la que utilicé una lista de listas para representar la cola de rutas.

# graph is in adjacent list representation
graph = {
        '1': ['2', '3', '4'],
        '2': ['5', '6'],
        '5': ['9', '10'],
        '4': ['7', '8'],
        '7': ['11', '12']
        }

def bfs(graph, start, end):
    # maintain a queue of paths
    queue = []
    # push the first path into the queue
    queue.append([start])
    while queue:
        # get the first path from the queue
        path = queue.pop(0)
        # get the last node from the path
        node = path[-1]
        # path found
        if node == end:
            return path
        # enumerate all adjacent nodes, construct a new path and push it into the queue
        for adjacent in graph.get(node, []):
            new_path = list(path)
            new_path.append(adjacent)
            queue.append(new_path)

print bfs(graph, '1', '11')

Otro enfoque sería mantener un mapeo de cada nodo a su padre y, al inspeccionar el nodo adyacente, registrar su padre. Cuando termine la búsqueda, simplemente retroceda según el mapeo principal.

graph = {
        '1': ['2', '3', '4'],
        '2': ['5', '6'],
        '5': ['9', '10'],
        '4': ['7', '8'],
        '7': ['11', '12']
        }

def backtrace(parent, start, end):
    path = [end]
    while path[-1] != start:
        path.append(parent[path[-1]])
    path.reverse()
    return path


def bfs(graph, start, end):
    parent = {}
    queue = []
    queue.append(start)
    while queue:
        node = queue.pop(0)
        if node == end:
            return backtrace(parent, start, end)
        for adjacent in graph.get(node, []):
            if node not in queue :
                parent[adjacent] = node # <<<<< record its parent 
                queue.append(adjacent)

print bfs(graph, '1', '11')

Los códigos anteriores se basan en el supuesto de que no hay ciclos.

qiao
fuente
2
¡Esto es excelente! Mi proceso de pensamiento me llevó a creer en la creación de algún tipo de tabla o matriz, todavía tengo que aprender sobre gráficos. Gracias.
Christopher Markieta
También intenté usar un enfoque de rastreo hacia atrás, aunque esto parece mucho más limpio. ¿Sería posible hacer un gráfico si solo conociera el inicio y el final, pero ninguno de los nodos intermedios? ¿O incluso otro enfoque además de los gráficos?
Christopher Markieta
@ChristopherM No entendí tu pregunta :(
qiao
1
¿Es posible adaptar el primer algoritmo para que devuelva todas las rutas de 1 a 11 (suponiendo que haya más de una)?
Maria Ines Parnisari
1
Se recomienda utilizar collections.deque en lugar de una lista. La complejidad de list.pop (0) es O (n) mientras que deque.popleft () es O (1)
Omar_0x80
23

¡Me gustó mucho la primera respuesta de qiao! Lo único que falta aquí es marcar los vértices como visitados.

¿Por qué tenemos que hacerlo?
Imaginemos que hay otro nodo número 13 conectado desde el nodo 11. Ahora nuestro objetivo es encontrar el nodo 13.
Después de un poco de ejecución, la cola se verá así:

[[1, 2, 6], [1, 3, 10], [1, 4, 7], [1, 4, 8], [1, 2, 5, 9], [1, 2, 5, 10]]

Tenga en cuenta que hay DOS rutas con el número de nodo 10 al final.
Lo que significa que las rutas desde el nodo número 10 se comprobarán dos veces. En este caso, no se ve tan mal porque el nodo número 10 no tiene hijos ... Pero podría ser realmente malo (incluso aquí comprobaremos ese nodo dos veces sin ninguna razón ...) El
nodo número 13 no está en esas rutas para que el programa no regrese antes de llegar a la segunda ruta con el nodo número 10 al final ... y lo volveremos a verificar ...

Lo único que nos falta es un conjunto para marcar los nodos visitados y no volver a comprobarlos.
Este es el código de qiao después de la modificación:

graph = {
    1: [2, 3, 4],
    2: [5, 6],
    3: [10],
    4: [7, 8],
    5: [9, 10],
    7: [11, 12],
    11: [13]
}


def bfs(graph_to_search, start, end):
    queue = [[start]]
    visited = set()

    while queue:
        # Gets the first path in the queue
        path = queue.pop(0)

        # Gets the last node in the path
        vertex = path[-1]

        # Checks if we got to the end
        if vertex == end:
            return path
        # We check if the current node is already in the visited nodes set in order not to recheck it
        elif vertex not in visited:
            # enumerate all adjacent nodes, construct a new path and push it into the queue
            for current_neighbour in graph_to_search.get(vertex, []):
                new_path = list(path)
                new_path.append(current_neighbour)
                queue.append(new_path)

            # Mark the vertex as visited
            visited.add(vertex)


print bfs(graph, 1, 13)

La salida del programa será:

[1, 4, 7, 11, 13]

Sin las comprobaciones innecesarias.

O Kazaz
fuente
6
Puede ser útil usar collections.dequefor queueas list.pop (0) incurrir en O(n)movimientos de memoria. Además, por el bien de la posteridad, si desea hacer DFS, simplemente configure, path = queue.pop()en cuyo caso la variable queuerealmente actúa como un archivo stack.
Sudhi
11

Codigo muy facil. Sigues agregando la ruta cada vez que descubres un nodo.

graph = {
         'A': set(['B', 'C']),
         'B': set(['A', 'D', 'E']),
         'C': set(['A', 'F']),
         'D': set(['B']),
         'E': set(['B', 'F']),
         'F': set(['C', 'E'])
         }
def retunShortestPath(graph, start, end):

    queue = [(start,[start])]
    visited = set()

    while queue:
        vertex, path = queue.pop(0)
        visited.add(vertex)
        for node in graph[vertex]:
            if node == end:
                return path + [end]
            else:
                if node not in visited:
                    visited.add(node)
                    queue.append((node, path + [node]))
SeasonalShot
fuente
2
Encuentro su código muy legible, en comparación con otras respuestas. ¡Muchas gracias!
Mitko Rusev
8

Pensé en intentar codificar esto por diversión:

graph = {
        '1': ['2', '3', '4'],
        '2': ['5', '6'],
        '5': ['9', '10'],
        '4': ['7', '8'],
        '7': ['11', '12']
        }

def bfs(graph, forefront, end):
    # assumes no cycles

    next_forefront = [(node, path + ',' + node) for i, path in forefront if i in graph for node in graph[i]]

    for node,path in next_forefront:
        if node==end:
            return path
    else:
        return bfs(graph,next_forefront,end)

print bfs(graph,[('1','1')],'11')

# >>>
# 1, 4, 7, 11

Si desea ciclos, puede agregar esto:

for i, j in for_front: # allow cycles, add this code
    if i in graph:
        del graph[i]
Robert King
fuente
después de haber construido el next_for_front. Una pregunta de seguimiento, ¿qué pasa si el gráfico contiene bucles? Por ejemplo, ¿si el nodo 1 tuviera un borde que se conectara a sí mismo? ¿Qué pasa si el gráfico tiene múltiples aristas entre dos nodos?
robert king
1

Me gusta la primera respuesta de @Qiao y la adición de @ Or. En aras de un poco menos de procesamiento, me gustaría agregar a la respuesta de Or.

En la respuesta de @ Or, hacer un seguimiento del nodo visitado es genial. También podemos permitir que el programa se cierre antes de lo que está actualmente. En algún punto del bucle for current_neighbour, tendrá que ser el end, y una vez que eso suceda, se encontrará la ruta más corta y el programa podrá regresar.

Modificaría el método de la siguiente manera, preste mucha atención al bucle for

graph = {
1: [2, 3, 4],
2: [5, 6],
3: [10],
4: [7, 8],
5: [9, 10],
7: [11, 12],
11: [13]
}


    def bfs(graph_to_search, start, end):
        queue = [[start]]
        visited = set()

    while queue:
        # Gets the first path in the queue
        path = queue.pop(0)

        # Gets the last node in the path
        vertex = path[-1]

        # Checks if we got to the end
        if vertex == end:
            return path
        # We check if the current node is already in the visited nodes set in order not to recheck it
        elif vertex not in visited:
            # enumerate all adjacent nodes, construct a new path and push it into the queue
            for current_neighbour in graph_to_search.get(vertex, []):
                new_path = list(path)
                new_path.append(current_neighbour)
                queue.append(new_path)

                #No need to visit other neighbour. Return at once
                if current_neighbour == end
                    return new_path;

            # Mark the vertex as visited
            visited.add(vertex)


print bfs(graph, 1, 13)

La salida y todo lo demás será igual. Sin embargo, el código tardará menos en procesarse. Esto es especialmente útil en gráficos más grandes. Espero que esto ayude a alguien en el futuro.

Darie Dorlus
fuente