22. Análisis asintótico de DFS BFS
El branching factor (o factor de ramificación) es un concepto fundamental en búsqueda en grafos y árboles, especialmente en inteligencia artificial y algoritmos de búsqueda.
En términos simples, el branching factor indica cuántos hijos genera, en promedio, cada nodo durante la expansión del espacio de búsqueda.
Desde un punto de vista formal, el branching factor bbb se define como el número medio de sucesores que tiene un nodo. Si un nodo puede generar kkk nuevos nodos al expandirse, entonces su branching factor es kkk. En la práctica, se suele trabajar con un valor promedio.
Este concepto es clave porque determina qué tan rápido crece el espacio de búsqueda. Por ejemplo, si desde cada nodo se generan bbb nodos nuevos, el número total de nodos a profundidad ddd es aproximadamente:
Esto muestra que incluso valores pequeños de bbb producen un crecimiento exponencial cuando la profundidad aumenta.
En algoritmos como BFS y DFS, el branching factor tiene un impacto directo en:
-
Complejidad temporal:
BFS tiene complejidad O(bd)O(b^d)O(bd), donde ddd es la profundidad de la solución. -
Complejidad espacial:
BFS también requiere O(bd)O(b^d)O(bd) memoria, mientras que DFS usa menos memoria, aproximadamente O(b⋅d)O(b \cdot d)O(b⋅d).
En problemas de inteligencia artificial, como búsqueda de rutas, juegos o planificación, el branching factor determina la viabilidad del algoritmo. Un branching factor alto puede hacer que la búsqueda sea intratable incluso para profundidades pequeñas.
relatedInteligencia Artificial