Búsqueda en anchura

Definición

Estrategia no informada que expande primero los nodos de menor profundidad. Recorre el árbol por capas mediante una cola FIFO.

Propiedades

• Completa si el factor de ramificación $b$ es finito.
• Óptima cuando todos los costos de paso son iguales.
• Tiempo y espacio: $O(b^d)$; algunas convenciones cuentan la capa siguiente y escriben $O(b^{d+1})$.

Distinción clave

BFS minimiza el número de acciones, no el costo total. Si las aristas tienen costos distintos, una ruta más profunda puede ser más barata; en ese caso se usa costo uniforme.

Prueba de meta

Con costos unitarios, la primera vez que se genera una meta se ha encontrado una ruta de profundidad mínima. También es correcta una implementación general que compruebe la meta al extraer el nodo.

Relaciones

• Es una búsqueda no informada.
• IDS conserva su completitud usando menos memoria.