ALGORITMO DE B SQUEDA POR NCHURA

Algoritmo de
búsqueda de por
Anchura



 es un algoritmo para recorrer o buscar elementos en
un grafo usado frecuentemente sobre árboles



se comienza en la raíz (eligiendo algún nodo comoelemento raíz en el caso de un grafo



se exploran todos los vecinos de este nodo



cada uno de los vecinos se exploran sus respectivos
vecinos adyacentes, y así hasta que se recorra todo el
árbol.

 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

• Se tiene unárbol en un estado
inicial y se cuenta con cuatro
metas: M1, M2, M3 y M4.

• Se introduce A como primer
elemento de la lista.

• Se comprueba que A no es
una meta y se elimina de la
lista.
• Seintroducen los hijos de
A en la lista recorriendo 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 lalista.
• Se analizan los hijos de B
y se introducen al final de
la lista como ABD y ABE.

• AC tampoco es una meta y
es eliminado de la lista.
• Se introducen los hijos de C
al final de la lista.

• Sesiguen sacando de la
lista aquellos nodos que no
dan como resultado una
meta.
• En este caso se introducen
al final de la lista los hijos
de D.
• Los
nuevos
nodos
introducidos a la lista son
H e I.

•ABE no muestra ninguna
meta y se elimina de la
lista.
• Al introducir los hijos de E
al final de la lista se puede
ver que ha aparecido uno
de los nodos meta. En este
caso el nodo es M1

• Se sigueneliminando los
nodos que no son estados
meta y agregando a los
hijos al final de la lista.

• En este punto se elimina
ABEJ y se introducen los
hijos de J al final de la lista
y al frente quedaABEM1 lo
que da como resultado el
éxito.

• Se encuentra la meta M1 y
se detiene el algoritmo al
haber alcanzado el éxito.

• Se traza el camino desde
el origen hacia la meta:
• A  B  E  M1
• El...