¿Cómo rastrear la ruta en una búsqueda de primer orden?

Question

¿Cómo se traza la trayectoria de una búsqueda primero en amplitud, de tal manera que en el ejemplo siguiente:

Si la búsqueda de clave 11, devuelve la lista más corta de conexión 1 a 11.

[1, 4, 7, 11] 

Answer 1

Primero debe tener en cuenta http://en.wikipedia.org/wiki/Breadth-first_search.

---

A continuación se muestra una implementación rápida, en la que he usado una lista de la lista para representar a la cola de caminos.

# 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 el mantenimiento de una correspondencia de cada nodo para su matriz, y al inspeccionar el nodo adyacente, constancia de su padre. Cuando se realiza la búsqueda, simplemente rastree según el mapeo padre.

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 la suposición de que no hay ciclos.

Answer 2

pensé que iba a tratar este código para la 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 se podría añadir lo siguiente:

for i, j in for_front: # allow cycles, add this code 
    if i in graph: 
     del graph[i] 

Answer 3

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

¿Por qué tenemos que hacerlo?
imaginemos que existe otro número de nodo 13 conectado desde el nodo 11. Ahora nuestro objetivo es encontrar el nodo 13.
Después de un poco de una carrera de 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]] 

Nota que hay DOS rutas con el nodo número 10 al final.
Lo que significa que las rutas del nodo 10 se verificará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í revisaremos ese nodo dos veces sin motivo ...)
Número de nodo 13 isn ' t 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 comprobar ...

Lo único que falta es un conjunto para marcar la visita nodos y no para comprobar de nuevo ..
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.

Answer 4

Me gustan tanto la primera respuesta de @Qiao como la adición de @O. Por un poco menos de procesamiento me gustaría agregar a la respuesta de Or.

En la respuesta de @ Or, el seguimiento del nodo visitado es excelente. También podemos permitir que el programa salga antes de lo que actualmente es. En algún punto del bucle for el 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.

que modificaría el método de la siguiente manera, prestar 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á el mismo. Sin embargo, el código tardará menos tiempo en procesarse. Esto es especialmente útil en gráficos más grandes. Espero que esto ayude a alguien en el futuro.