¿Cómo trazar el camino en una Búsqueda de Amplitud Primero?
¿Cómo se traza el camino de una Búsqueda de Amplitud Primero, de tal manera que en el siguiente ejemplo:
Si busca la clave 11
, devuelva la lista más corta que conecta del 1 al 11.
[1, 4, 7, 11]
5 answers
Deberías echar un vistazo a http://en.wikipedia.org/wiki/Breadth-first_search primero.
A continuación se muestra una implementación rápida, en la que utilicé una lista de lista 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 una asignación de cada nodo a su padre, y al inspeccionar el nodo adyacente, registrar su padre. Cuando termine la búsqueda, simplemente haga una traza inversa de acuerdo con la asignación 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 suposición de que no hay ciclos.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2018-02-15 16:41:29
¡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 nodo número 10 al final.
Lo que significa que las rutas del nodo número 10 se verificarán dos veces. En este caso se 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, por lo que el programa no regresará antes de llegar a la segunda ruta con el nodo número 10 al final..Y vamos a volver a comprobarlo..
Todo lo 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)
El la salida del programa será:
[1, 4, 7, 11, 13]
Sin las comprobaciones de unneccecery..
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2014-08-30 15:26:26
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 quieres ciclos puedes añadir esto:
for i, j in for_front: # allow cycles, add this code
if i in graph:
del graph[i]
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2016-08-09 03:46:09
Código muy fácil. Se sigue añadiendo la ruta cada vez que se descubre 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]))
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2018-08-18 23:07:15
Me gusta tanto la primera respuesta de @Qiao como la adición de @Or. En aras de un poco menos de procesamiento me gustaría añadir 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 salga antes de lo que está actualmente. En algún punto del bucle for el current_neighbour
tendrá que ser el end
, y una vez que eso sucede, se encuentra el camino más corto y el programa puede regresar.
Me gustaría modificar el el método de la siguiente manera, prestar mucha atención a la para bucle
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án iguales. 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.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2018-02-11 01:09:05