Encuentra un pedido óptimo

9

Encontré este problema y estoy luchando por encontrar una manera de abordarlo. Cualquier idea sería muy apreciada!

Supongamos que se nos da una matriz {1,0,1}n × k , por ejemplo,

[1010110001011011101110001]

Sin probar cada permutación, encuentre un orden de las columnas ci que maximice el número de filas para las cuales el primer elemento distinto de cero es 1 .

Para el ejemplo anterior, uno de esos ordenamientos (¡no es único!) Es (c3,c4,c1,c2,c5) , es decir,

[1010100101100110111100101]

Aquí, para 4 de 5 filas, el primer elemento distinto de cero es 1 .

haijo
fuente
¿Qué enfoques algorítmicos probaste? ¿Dónde encontraste este problema? ¿Puedes acreditar la fuente original? ¿Puedes compartir algo sobre el contexto o la motivación? Puede encontrar esta página útil para mejorar su pregunta.
DW
1
Quiero sugerir un paso de preprocesamiento: deje que una columna semi-positiva (fila de respuesta) sea una columna (fila de respuesta) con solo 0s y 1s. La sugerencia es eliminar todas las columnas semi-positivas, y también las filas con un 1 en una columna semi-positiva. En su ejemplo, eso eliminaría las filas 1, 3 y 4. Ahora le quedan filas y columnas que contienen -1s. Puede que no ayude, pero podría ser más sencillo razonar.
Pål GD
¿Podemos suponer que el número de filas es mucho menor que el número de columnas? Esto podría facilitar el problema.
Angela Pretorius
1
@ Pål, es posible un procesamiento previo similar con filas y columnas que no contienen 1s. Sin embargo, no creo que haga que sea más fácil razonar: simplemente más pequeño.
Peter Taylor
1
FWIW esta es una publicación cruzada . haijo, si no recibe una respuesta en una pila y cree que otra podría ser mejor, puede marcarla y solicitar una migración. La publicación cruzada no es buena etiqueta porque los respondedores no están al tanto de las respuestas que puede haber recibido en el otro sitio y pueden perder su tiempo repitiéndolas.
Peter Taylor

Respuestas:

4

Este problema, que llamaré CO para ordenar columnas, es NP-hard . Aquí hay una reducción del problema NP-hard Vertex Cover (VC):

Formas de decisión de problemas de VC y CO

Deje que la instancia de VC de entrada sea (V,E,k) . Representa la pregunta: "Dada la gráfica (V,E) , ¿es posible elegir un conjunto de a lo sumo k vértices de V modo que cada borde en E incida en al menos un vértice elegido?" Construiremos una instancia (A,k) de CO que represente la pregunta: "Dada la matriz A con elementos en {1,0,1}, ¿es posible permutar las columnas de A modo que un 1 aparezca antes de un -1 en al menos k filas? "Estos dos problemas se expresan en forma de problema de decisión , por lo que la respuesta a cada uno es SÍ o NO: hablando formalmente , esta forma de problema es NP-complete (o no). No es demasiado difícil ver que la forma de problema de optimización más natural establecida en la pregunta del OP es más o menos equivalente en términos de complejidad: búsqueda binaria en el umbral El parámetro se puede utilizar para resolver el problema de optimización utilizando un solucionador de problemas de decisión, mientras que una sola invocación de un solucionador de problemas de optimización, seguida de una única comparación, es suficiente para resolver el problema de decisión.

Construir una instancia de CO a partir de una instancia de VC

Deje n=|V|y m=|E|. Construiremos una matriz A con (n+1)m+n filas y n+1 columnas. Las filas superiores (n+1)m estarán formadas por m bloques de n+1 filas cada una, con cada bloque representando un borde que necesita ser cubierto . El fondo n las filas contienen "indicadores" de vértice, lo que hará que una columna (correspondiente a un vértice) incurra en un costo fijo si se incluye en el lado izquierdo de la solución de CO (correspondiente a un vértice que se incluye en la cubierta del vértice de la Solución de VC).

Para cada vértice vi , cree una columna en la que:

  • entre las filas superiores (n+1)m , el bloque j -ésimo de n+1 filas contiene un +1 cuando el borde ej incide en vi , y 0 en caso contrario, y
  • las n filas inferiores son todas 0 excepto la i -ésima, que es -1.

Cree una columna "cerca" más que consista en (n+1)m copias de -1, seguido de n copias de +1.

Finalmente, establezca el umbral k para la instancia de CO construida: (n+1)m+nk . En otras palabras, permitimos a lo sumo k filas en las que aparece un -1 antes de un +1. Llamemos a este número de filas infractoras el "costo" de una solución de CO.

Prueba

La correspondencia entre una solución para la instancia de CO y un conjunto de vértices en la instancia de VC original es: cada columna a la izquierda de la cerca corresponde a un vértice que está en el conjunto, y cada columna a la derecha de la cerca corresponde a un vértice que no lo es.

n

kk

kk

k(n+1)m(n+1)uvAn+1n+1kn<n+1

m(n+1)m(n+1)mnkkk

Finalmente, está claro que la instancia de CO puede construirse en tiempo polinómico a partir de la instancia de VC, lo que significa que si existiera un algoritmo de tiempo polinomial para resolver CO, cualquier instancia de VC también podría resolverse en tiempo polinomial construyendo primero una instancia de CO como se describe arriba y luego resolverlo. Como VC es NP-hard, CO también lo es.

j_random_hacker
fuente
Cada vez que hay una respuesta tan agradable, me pregunto si las "Preguntas de la red activa" deben reemplazarse o unirse por algo como "Respuestas valiosas de la red".
John L.
¿Podría arrojar algo de luz sobre cómo encontrar la respuesta? Eso debería ser aún más esclarecedor que la respuesta misma.
John L.
1
@ Apass.Jack: ¡Gracias! :) No tengo una estrategia especial, y puedo pasar mucho tiempo vagando en la dirección equivocada. Por ejemplo, aquí pasé mucho tiempo pensando que podría reducir el Hamiltonian Cycle (que es similar en la medida en que se trata de ordenar elementos) antes de darme cuenta de que mi construcción permitiría configuraciones correspondientes a subtours, y por lo tanto no funcionaría. Como regla, siempre intento reducciones de Vertex Cover o Partition, luego quizás Clique. "Valioso Answers" suena como una gran idea :)
j_random_hacker
1
rkr
1
n+1
2

S

function simplification:
while(true)
    if any row i$ has no 1 or no -1 left, remove it
    if any column j has no -1 then,
       remove it and put j on the leftmost available position in S,
       remove all rows where column j has 1.
    if any column j has no 1 then, 
       remove it and put j on the rightmost available position in S.
    if no modification has been done on this loop, break

Luego tienes que hacer una exploración completa de la combinatoria usando iterativamente la función pick:

function pick(k):
    put column k on the leftmost available position in S
    remove any row where column k is -1 or 1

Después de cada selección, puede hacer una simplificación para posiblemente reducir el número de posibilidades para explorar. Sugiero explorar con avidez comenzando con la columna que tiene menos -1, por lo que puede llegar a un límite inferior haciendo un criterio de detención.

En el ejemplo dado, la primera simplificación da (como explicó Pål GD en el comentario)

  • S[0]=c3
  • S[1]=c4
  • S[2]=c2
    [1111]

[110000110000001100001100000011000011]

Sin embargo, la simplificación aún ahorra aproximadamente la mitad de los pasos de exploración. Y este tipo de matriz se puede dividir en varias submatrices independientes.

Optidad
fuente
1
@ Apass.Jack que edité para ser más preciso. Sí, me refería a la posición de la columna en la secuencia de salida.
Optidad
Votado como el paso de simplificación podría ser lo suficientemente bueno para fines prácticos (como ejercicios de programación en línea?).
John L.
Gracias, de hecho, estaba interesado en estimar el costo del tiempo amortizado, pero realmente no sé cómo hacerlo. Es posible ? ¿O depende mucho el problema?
Optidad
2
ijijjij
1
ijijijijikk