Download Búsqueda en anchura

Algoritmo Primero a lo Ancho BREATH-FIRST
Trabajo presentado por:
LUIS FERNANDO OBANDO
ING
Algoritmo Primero a lo Ancho (BREATH-FIRST)
• Búsqueda en anchura (en ingles BFS - Breadth First Search)
es un algoritmo para recorrer o buscar elementos en
un grafo (usado frecuentemente sobre árboles).
Intuitivamente, se comienza en la raíz (eligiendo algún nodo
como elemento raíz en el caso de un grafo) y se exploran
todos los vecinos de este nodo. A continuación para cada
uno de los vecinos se exploran sus respectivos vecinos
adyacentes, y así hasta que se recorra todo el árbol.
Búsqueda por anchura
• Formalmente, BFS es un algoritmo de búsqueda sin
información, que expande y examina todos los nodos
de un árbol sistemáticamente para buscar una
solución.
El
algoritmo
no
usa
ninguna
estrategia heurística.
Ventajas frente a DFS
• La búsqueda por medio de BFS siempre termina mientras que por
por DFS búsqueda en profundidad puede en ocasiones no terminar.
• La búsqueda que utiliza BFS resulta mas optima ya que recorre
diferentes ramas del árbol y genera una perspectiva mas amplia.
• Este algoritmo tiene como ventaja que, al expandir los nodos de forma
uniforme garantiza encontrar la mejor solución de un problema de
costo uniforme antes que ninguna, de manera que apenas se
encuentre una solución, puede devolverse, porque será la mejor, o bien
expandir todo el nivel en el cual se hubiere encontrado, para obtener
todas las soluciones posibles.
DESVENTAJAS
Su principal desventaja es el alto orden de complejidad
computacional, que hace que, de no mantenerse muy limitados los
parámetros del problema, crezcan rápidamente los requerimientos
y se vuelvan inaceptables y que además requiere de mucha
memoria. Básicamente tiene que guardar la parte completa de la
red que está explorando.
Procedimiento
• Dado un vértice fuente s, Breadth-first
search sistemáticamente explora los vértices de G para
“descubrir” todos los vértices alcanzables desde s.
• Calcula la distancia (menor número de vértices) desde s a
todos los vértices alcanzables.
• Después produce un árbol BF con raíz en s y que contiene a
todos los vértices alcanzables.
• El camino desde s a cada vértice en este recorrido contiene
el mínimo número de vértices. Es el camino más corto
medido en número de vértices.
• Se introduce A como
primer elemento de la lista.
• Se tiene un árbol en un
estado inicial y se cuenta
con una meta: M1.
• Se comprueba que A no es
una meta y se elimina de la
lista.
• Se recorre el árbol de
izquierda a derecha y
manteniendo la
información del recorrido.
Es decir AB y AC.
• AB no muestra ninguna
meta así que se saca de la
lista.
• Luego se continua con AC