Búsqueda en anchura (BFS)
Breadth-first search (BFS)
- Fecha
- 1945 (Zuse, inédito) / 1959 (Moore) · fiabilidad media
- Lugar
- Laboratorios Bell, Murray Hill, Nueva Jersey, Estados Unidos
- Autoría
- Edward F. Moore (con la formulación independiente y anterior, aunque inédita, de Konrad Zuse en 1945)
- Ámbito
- Saber y símbolos
Qué se descubrió
Moore publicó el algoritmo de búsqueda en anchura para hallar el camino más corto en un laberinto, explorando un grafo nivel a nivel desde el nodo de partida. Konrad Zuse había concebido la misma idea en 1945 para componentes conexos de grafos, pero su trabajo permaneció inédito hasta 1972.
Konrad Zuse ideó el mismo algoritmo en 1945 dentro de su tesis sobre el Plankalkül, pero no se publicó hasta 1972, por lo que la comunidad científica atribuye la reinvención pública a Moore.
A qué dio paso
- Algoritmos de enrutamiento de circuitos (C. Y. Lee, 1961)
- Teoría de grafos algorítmica
Se apoya en
- Teoría de grafos de Euler