##  [Explosión del Espacio de Búsqueda](/es/node/61076) 

 Definición

Un crecimiento rápido (a menudo superpolinomial) en el número de estados candidatos, asignaciones o configuraciones que deben considerarse durante razonamiento automatizado, búsqueda o construcción de modelos.

 

 

 

 

 

 





## Principio

Principio

El ramificado combinatoria multiplica las posibilidades; sin restricciones, poda o explotación de la estructura, el número de candidatos crece exponencialmente o peor con el tamaño del problema.

 

 

 

 

 





## Demostración

Demostración

Una fórmula SAT con n variables booleanas no restringidas plantea hasta 2^n asignaciones por considerar; añadir elecciones no restringidas en un problema de planificación multiplica de forma similar el árbol de búsqueda y hace inviable los métodos exhaustivos.

 

 

 

 

## Aplicación incorrecta

Aplicación incorrecta

Aplicar búsqueda exhaustiva no informada o ramificación ingenua a problemas con estructura combinatoria (por ejemplo, enumerar a ciegas permutaciones para programación) que garantiza tiempos de ejecución y uso de recursos imprácticos.

 

 

 

 

 





## Consecuencia

Consecuencia

Reconocer la explosión del espacio de búsqueda motiva heurísticas, quiebre de simetrías, propagación de restricciones, descomposición o algoritmos de aproximación que reducen el ramificado efectivo y restauran la tratabilidad en instancias prácticas.

 

 

 

 

## Inversión

Inversión

Reducción del espacio de búsqueda — introducir restricciones, abstracciones o factorizaciones que reduzcan el conjunto de candidatos y permitan búsqueda eficiente.

 

 

 

 

 





## Límite

Límite

Se aplica a tareas de búsqueda y razonamiento combinatorio donde los recuentos de candidatos crecen por combinatoria; excluye la complejidad puramente aritmética inherente a cálculos en forma cerrada sin ramificación.

 

 

 

 

 





## Tensión semántica

Tensión semántica

Tensión con la explosión de recursos: la explosión describe el crecimiento combinatorio de candidatos, mientras que la explosión de recursos enfatiza las consecuencias (tiempo, memoria); las estrategias de mitigación pueden abordar uno o ambos aspectos.

 

 

 

 

 





## Síntesis

Síntesis

La explosión del espacio de búsqueda es el crecimiento combinatorio de posibilidades en razonamiento automatizado que hace inviable la enumeración ingenua; el manejo práctico requiere explotar la estructura (restricciones, heurísticas, descomposición) para reducir el ramificado y enfocar la búsqueda.