- Problema del conjunto de cobertura
-
El problema del Set Covering , también conocido por sus siglas SCP pertenece a la familia de los problemas no polinomiales duros, es un problema clásico en las Ciencias de la computación, consiste en encontrar las soluciones que minimicen el problema de cubrir un conjunto de necesidades con el menor costo posible. También se puede entender como el problema de encontrar el mínimo de subconjuntos que contengan todos los elementos de un conjunto dado, con el fin de minimizar algún valor.
Contenido
Definición formal
De una forma más formal se puede definir el problema de la cobertura como dado un universo U, una familia S de subconjuntos de U, una cobertura o solución para el problema es una subfamilia cuya unión de por resultado el mismo U.
Ejemplo
Una estación de bomberos tiene la capacidad de cubrir las emergencias tanto de su comuna como de las comunas adyacentes a ella, por ejemplo una estación construida en la comuna 1 (Figura 1) podrá cubrir las emergencias de todo su vecindario, es decir, de la comuna 1, comuna 2 , comuna 3 y comuna 5. Se necesitan construir tantas estaciones de bomberos sean necesarias para cubrir todas las comunas ante posibles emergencias cuidando que todas las comunas estén cubiertas por al menos una estación (una o más) resguardando que la cantidad de estaciones construidas sea el mínimo.
Modelo matemático
Sujeto a :
Solución
Una solución para este problema seria construir estaciones en la comuna 1, 11 y 12. Con un total de 3 estaciones construidas se lograría cubrir las necesidades de todas las comunas del problema.
Categoría:- Problemas NP-completos
Wikimedia foundation. 2010.