En nuestro grupo de investigación estamos trabajando en la aplicación de métodos heurísticos al problema de iluminación inversa (es decir, dada una serie de restricciones sobre las condiciones de iluminación en una escena, encontrar los lugares donde se deben colocar las fuentes de luz y sus intensidades en para cumplir con las restricciones y minimizar el costo). Nos gustaría justificar el uso de métodos heurísticos demostrando que el problema es NP-duro y hemos encontrado que está estrechamente relacionado con la "solución de peso mínimo para ecuaciones lineales" (MWSLE) NP-complete problema de Garey y Johnson " Computadoras e intratabilidad ", con la particularidad de que, dado que las emisiones de la fuente de luz no pueden ser negativas, la solución al sistema de ecuaciones lineales debe estar formada solo por valores no negativos. Resumiendo, el problema es el siguiente:
SOLUCIÓN POSITIVA DE PESO MÍNIMO A ECUACIONES LINEALES.
INSTANCIA: Conjunto finito de pares ( → x , b ) , donde → x es una m-tupla de enteros no negativos yb es un entero no negativo, y un entero positivo K ≤ m .
PREGUNTA: ¿Hay una m-tupla de entradas racionales no negativas de modo que → y tenga como máximo K entradas distintas de cero y tal que → x ⋅ → y = b para todos ( → x , b ) ∈ X ?
Garvey y Johnson afirman que la completitud NP de MWSLE puede demostrarse a partir del problema de "cobertura exacta por 3 series", pero no dan más detalles. La cobertura exacta por 3 conjuntos es una generalización natural del problema de coincidencia perfecta para las hipergrafías G = (V, E) con todos los bordes e∈E que contienen 3 vértices (en lugar de 2) y | V | es divisible por 3. El problema es encontrar un subconjunto de las hipertensiones de modo que cada vértice incida exactamente en una de las hipertensiones seleccionadas.
Estamos tratando de demostrar que el problema restringido todavía es NP completo, pero no vemos la forma de hacerlo. ¿Alguna pista?
Gracias por adelantado
Esteve
Respuestas:
fuente