Processing math: 100%

13 votos

¿Cuál es el nombre de esta clase de problemas (combinatorias)??

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.

3voto

Smylic Puntos 647

Yo no digo un nombre de este tipo de problema, incluso si existe, pero voy a demostrar que el problema acerca de máximo estiramiento de tiempo es NP-duro. Podemos reducir exponencialmente SAT problema a la deseada en el siguiente camino.

En primer lugar yo uso una suposición de que shoter cadena no puede venir ouf de las fronteras de la lonest uno.

Dada una fórmula F m de las diferencias en las variables de x1,x2,,xn, podemos construir el siguiente conjunto de cadenas. Para cada literal x1,¯x1,x2,,¯xn creamos una cadena de longitud 2m+2n como sigue:

  • el símbolo en la posición 2i 1im corresponde a la entrada de la correspondiente literal a ith disyunción, yo. e. es 1 fib literal aparece en ith disyunción;
  • el símbolo en la posición (2m+2j1) 1jn 1 fib de la cadena corresponde a xj o ¯xj;
  • todos los otros símbolos son 0s.

Uno más de la cadena de longitud 2m+2n+1 1 en cada posición impar. Es fácil ver que el tramo de tiempo es 2m+2n+1 si y sólo si F es válido, ya que cada posición (2m+2j) requiere al menos uno de cadena correspondiente a xj ¯xj a ser desplazado por 1 (i. e. requiere este literal para ser falso), mientras que la posición de cada uno 2i es una disyunción que requiere al menos uno de srings correspondientes a los literales de este disyunción a ser desplazado por 0 (i. e. se requiere al menos una verdad literal). Por tanto, el problema acerca de máximo estiramiento de tiempo es NP-duro.


EDIT. Ahora necesitamos que permiten el desplazamiento de toda la cadena. Para ese propósito añadimos 4n(n+m) más símbolos para cada cadena. Para ith cadena, 1i2n estos símbolos se 0s, salvo que las posiciones entre el2i(n+m)+12(i+1)(n+m), e inclusiva, donde sólo 1s se colocan. La última cadena ha 1s en las posiciones 2i(n+m)+1 todos los 2i2n+1 0s en todas las demás posiciones.

No es difícil ver que podemos obtener de estiramiento de tiempo 2(2n+1)(n+m)+1 si y sólo si F es válido. Y los cambios de todas las cadenas deberían ser 0 o 1 hacer tales tramo de tiempo.


Ejemplo.Vamos F=(x1x2)(x1¯x2)(¯x1x2)(¯x1¯x2).

Then corresponding set of strings is the following:

x1:s1= 01010000 1000 111111111111 000000000000 000000000000 000000000000
¯x1:s2= 00000101 1000 000000000000 111111111111 000000000000 000000000000
x2:s3= 01000100 0010 000000000000 000000000000 111111111111 000000000000
¯x2:s4= 00010001 0010 000000000000 000000000000 000000000000 111111111111
y s5= 10101010 1010 100000000000 100000000000 100000000000 100000000000 1

No es difícil ver que no podemos obtener de estiramiento de tiempo 61 por lo tanto F no es válido.

i-Ciencias.com

I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.

Powered by:

X