21. Algoritmo Primero en anchura (BFS)
El algoritmo Primero en anchura (BFS, por sus siglas en inglés) es una técnica fundamental de búsqueda que, junto al algoritmo Primero en profundidad (DFS), sirve como base para métodos más sofisticados. Su principal característica operativa radica en el cambio de la estructura de datos utilizada para la "agenda": mientras que el DFS emplea una pila (stack), el BFS utiliza una cola. Esto implica que, al extraer elementos, se saca siempre el primero que fue agregado (el que está al frente), a diferencia de la pila donde se extrae el último.
El proceso de ejecución comienza verificando una condición trivial y luego inicializando la agenda con el estado inicial. El algoritmo funciona mediante un ciclo de iteración que continúa hasta alcanzar el objetivo o hasta que la agenda se vacíe; en este último caso, se concluye que no existe una ruta posible. Durante cada paso, el nodo al frente de la cola se extrae, se envía a una lista de estados expandidos y se exploran sus sucesores en el grafo.
Un aspecto importante del BFS es que permite la presencia de estados repetidos en la agenda si provienen de caminos diferentes. Al momento de expandir un nodo, solo se agregan a la cola aquellos sucesores que no han sido expandidos previamente y que no son el objetivo. Si se identifica que un sucesor es la meta, el proceso de búsqueda finaliza.
Para obtener el resultado final, el algoritmo reconstruye la ruta de forma inversa, siguiendo las referencias de los nodos de origen hasta llegar al estado inicial. El resumen destaca que el algoritmo BFS garantiza encontrar la ruta óptima en número de pasos. En etapas posteriores, se analizan los recursos computacionales y la calidad de las soluciones mediante análisis asintótico. relatedInteligencia Artificial