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

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

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

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

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

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

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 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

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.