A juzgar por el número de preguntas similares, me he encontrado a mí mismo en una situación bastante común: me he encontrado con un problema, encontró en un callejón sin salida y ahora estoy buscando el nombre de el problema con el fin de aprender más sobre él.
Un ejemplo del problema de la siguiente manera:
Supongamos que tenemos un número de cadenas de unos y ceros. Por ejemplo:
s1:01010
s2:0010100
s3:00010001000
Ahora construimos una nueva cadena de H horizontal de desplazamiento de cada secuencia sn por cierta cantidad tn y aplicando la lógica de la disyunción a las columnas. ¿Cuál es la más larga posible secuencia de consecutivas en la cadena resultante, si se nos permite elegir tn? Por búsqueda exhaustiva, una solución a este problema en particular será el 5, el cual es dado por t1=2; t2=2; t3=0 :
s1:000001010
s2:00000010100
s3:00010001000
H:000111110000
Aclaración: cadenas más Cortas, puede extenderse más allá de las más largas, tan largas como el final de la cadena no tiene lagunas. En principio, si todas las cadenas sólo contenía 1's, entonces el máximo estiramiento sería ∑ni=1|si| donde |si| es la longitud de i-ésimo de la cadena.
El más cercano que pude encontrar es la restricción de la Tira que Cubre problema, que es un caso especial de Geométrica Conjunto de Cubierta, pero no es lo que estoy buscando.
Progreso: El problema puede ser expresada en términos de unidades de trabajo del problema de programación:
Supongamos que tenemos un número de empleados que pueden trabajar dentro de un cierto período de tiempo. Dentro de ese lapso de tiempo se puede tomar ciertas lagunas para el ocio. Dado un conjunto de tales empleados, ¿cuál es el máximo estiramiento de tiempo en el que al menos un empleado está trabajando? La distinción entre este problema y el trabajo-problema de programación es importante a pesar de que - la búsqueda de los valores óptimos para tn es NP-Duro, pero tal vez es posible calcular el tiempo máximo sin calcular tn en el polinomio de tiempo.