Imaginemos que tenemos una instancia de cobertura de conjunto. Tenemos un conjunto U, el “universo”, y otro conjunto S, que contiene subconjuntos de U. Queremos elegir la menor cantidad posible de estos subconjuntos, sin dejar de golpear todos los elementos en U.
Ahora, pensemos en lo que la programación entera nos permite hacer, y aplíquelo a nuestro problema. Podemos definir un conjunto de variables x_i y especificar algunas restricciones lineales sobre ellas. Bajo esas restricciones, podemos pedir que se minimice una suma ponderada particular de x_i.
Lo que queremos minimizar es la cantidad de elementos de S que elegimos, así que usemos las variables para indicar si elegimos o no cada elemento. En particular, si numeramos los elementos de S, podemos dejar que x_i denote si incluimos el elemento i en nuestra selección. Si x_i = 1, incluimos el subconjunto i; si x_i = 0, no lo hacemos. Luego, podemos establecer todos los pesos en uno, y pediremos que nuestro tamaño de selección se minimice.
- ¿Cómo ayuda la máquina de Turing a comprender la mente?
- Cómo usar el pecado y dónde usar cos en vectores
- ¿Cómo obtengo un límite superior para T (n) = T (n / 2) + n?
- ¿Es posible tomar la construcción del producto para DFA con diferentes idiomas?
- ¿Cuál es la complejidad computacional de la satisfacción de resolución de restricciones sobre enteros? He leído que es polinomial para las igualdades y NP-duro para las desigualdades, pero, ¿no puedes convertir siempre una restricción de desigualdad en una igualdad agregando vars de holgura?
La otra cosa que debemos hacer es asegurarnos de que alcancemos todos los elementos de U. Podemos hacer uso de las restricciones lineales para lograr esto. Escribiremos una ecuación por elemento: si el elemento e de U está presente en k elementos diferentes j_1, j_2, …, j_k de S, le pediremos que x_ {j_1} + x_ {j_2} + … + x_ {j_k }> = 1. Es decir, le pediremos que seleccione al menos uno de esos k subconjuntos.
Para mantener las cosas cuerdas, también incluiremos algunas condiciones límite. Necesitamos x_i> = 0, y necesitamos x_i <= 1, para todo i.
Es fácil ver desde aquí que hemos codificado correctamente el problema dado como una instancia de programación entera. Cualquier solución a las ecuaciones lineales puede interpretarse como una solución a nuestra instancia de cobertura establecida, y viceversa.
