Tareas Parcial 3
“Búsquedas no informada”
Martínez Sandoval Guillermo I
Materia: Inteligencia Artificial.
Profesora: M.C. Verónica Rodríguez López.
Carrera: Ingeniería en Electrónica.
Grupo: 902
Heroica Ciudad de Huajuapan de León, Oax. a 12 de Enero del 2011.
Introducción
El algoritmo de recorrido en anchura, en inglés breadth-first search BFS para abreviar, al igual
que el algoritmo de búsqueda en profundidad permite obtener un árbol recubridor donde los
vértices son recorridos por niveles. Al igual que en el caso anterior, si el grafo es conexo se
encuentra el árbol recubridor, el cual no es único, dependerá del vértice de partida el ordenen
que se visitan los vértices adyacentes al vértice activo. El algoritmo puede implementarse
mediante una cola, de tal forma que el vértice activo o a partir del cual se expande el árbol
siempre se encuentra en la cabeza de la cola. En cada paso se introduce en la cola unos de los
vértices adyacentes al vértice activo, añadiéndose al árbol recubridor la arista que une el
vértice activo con dicho adyacente. Los vértices adyacentes son introducidos por el final de a
cola de tal forma que el vértice activo no cambia, hasta que este se queda sin adyacentes, en
este momento el vértice es extraído de la cola y se repite el proceso con el resto de vértices,
hasta que todos los vértices del grafo han sido visitados.
¿Como trabaja?
BFS va formando un árbol a medida que va recorriendo un grafo, veamos el ejemplo de la
siguiente figura 1:
Si observan bien todo parte de un nodo inicial que será la raiz del árbol que se forma, luego ve
los adyacentes a ese nodo y los agrega en un cola, como la prioridad de una cola es FIFO
(primero en entrar es el primero en salir), los siguientes nodos a evaluar serán los adyacentes
previamente insertados. una cosa bastante importante es el hecho de que no se pueden visitar
2 veces el mismo nodo o Estado. ya que sino podriamos terminar en un ciclo interminable o
simplemente no hallar el punto deseado en el menor número de pasos.
Figura 1. Orden de expansión del método BFS.
