Encontre uma encomenda ideal

9

Me deparei com esse problema e estou lutando para encontrar uma maneira de abordá-lo. Qualquer pensamento seria muito apreciado!

Suponha que recebamos uma matriz , por exemplo,{1,0,1}n × k

[1010110001011011101110001]

Sem tentar todas as permutações, encontre uma ordem das colunas que maximize o número de linhas para as quais o primeiro elemento diferente de zero é 1 .ci1

Para o exemplo acima, uma dessas ordens (não é exclusiva!) É , ou seja,(c3,c4,c1,c2,c5)

[1010100101100110111100101]

Aqui, para de linhas, o primeiro elemento diferente de zero é .451

haijo
fonte
Quais abordagens algorítmicas você tentou? Onde você encontrou esse problema? Você pode creditar a fonte original? Você pode compartilhar algo sobre o contexto ou a motivação? Você pode achar esta página útil para melhorar sua pergunta.
DW
11
Quero sugerir uma etapa de pré-processamento: Seja uma coluna semi-positiva (resp. Linha) uma coluna (resp. Linha) com apenas 0s e 1s. A sugestão é remover todas as colunas semi-positivas e também as linhas com um 1 em uma coluna semi-positiva. No seu exemplo, isso removeria as linhas 1, 3 e 4. Agora você tem linhas e colunas que contêm todos os -1s. Pode não ajudar, mas poderia ser mais simples pensar.
Gål GD
Podemos assumir que o número de linhas é muito menor que o número de colunas? Isso pode facilitar o problema.
Angela Pretorius
11
@ Pål, é possível um pré-processamento semelhante com linhas e colunas que não contêm 1s. No entanto, não acho que isso facilite o raciocínio: apenas menor.
Peter Taylor
11
FWIW, este é um post cruzado . haijo, se você não receber uma resposta em uma pilha e achar que outra pode ser melhor, poderá sinalizá-la e solicitar uma migração. A postagem cruzada não é uma boa etiqueta, porque os respondentes não sabem as respostas que você pode ter recebido no outro site e podem perder tempo repetindo-as.
Peter Taylor

Respostas:

4

Esse problema, que chamarei de CO para ordenação de colunas, é difícil para NP . Aqui está uma redução do problema NP-difícil Vertex Cover (VC) para ele:

Formulários de problemas de decisão de VC e CO

Deixe a instância do VC de entrada ser (V,E,k) . Ele representa a pergunta: "Dado o gráfico (V,E) , é possível escolher um conjunto de no máximo k vértices de V modo que toda aresta em E incida em pelo menos um vértice escolhido?" Construiremos uma instância (A,k) de CO que representa a pergunta: "Dada a matriz A com elementos em {1,0,1}, é possível permutar as colunas de A modo que um 1 apareça antes de -1 em pelo menos k linhas? "Esses dois problemas são apresentados na forma de problemas de decisão , em que a resposta para cada um é SIM ou NÃO: formalmente falando , é essa forma de problema que é NP-completa (ou não). Não é muito difícil perceber que a forma mais natural de problema de otimização indicada na pergunta do OP é aproximadamente equivalente em termos de complexidade: pesquisa binária no limiar O parâmetro pode ser usado para resolver o problema de otimização usando um solucionador de problemas de decisão, enquanto uma única chamada de um solucionador de problemas de otimização, seguida por uma comparação única, é suficiente para resolver o problema de decisão.

Construindo uma instância de CO a partir de uma instância de VC

Seja n=|V|e m=|E|. Vamos construir uma matriz A com (n+1)m+n linhas e n+1 colunas. As linhas superiores (n+1)m serão formadas por m blocos de n+1 linhas cada, com cada bloco representando uma aresta que precisa ser coberta . O fundo n linhas contêm "sinalizadores" de vértice, o que fará com que uma coluna (correspondente a um vértice) incorra em um custo fixo se for incluída no lado esquerdo da solução de CO (correspondente a um vértice sendo incluído na capa de vértice da Solução VC).

Para cada vértice vi , crie uma coluna na qual:

  • entre a parte superior (n+1)m linhas, o j bloco -ésimo de n+1 linhas, todos contêm uma 1 quando a orla ej é incidente em vi , e 0 de outro modo, e
  • as n linhas inferiores são todas 0, exceto a i ésima, que é -1.

Crie mais uma coluna "cerca" que consiste em (n+1)m cópias de -1, seguidas por n cópias de +1.

Por fim, defina o limite k para a instância de CO construída: (n+1)m+nk . Em outras palavras, permitimos no máximo k linhas nas quais um -1 aparece antes de um +1. Vamos chamar esse número de linhas violadas de "custo" de uma solução de CO.

Prova

A correspondência entre uma solução para a instância CO e um conjunto de vértices na instância VC original é: Cada coluna à esquerda da cerca corresponde a um vértice que está no conjunto e cada coluna à direita da cerca corresponde a um vértice que não é.

Intuitivamente, os -1s na parte superior da coluna "cerca" forçam a seleção de um subconjunto de colunas a serem colocadas à esquerda, que juntas contêm + 1s em todas essas posições - correspondendo a um subconjunto de vértices que ocorrem em todos os Beira. Cada uma dessas colunas que aparece à esquerda da "cerca" tem -1 em uma linha distinta em algum lugar nas n linhas inferiores , incorrendo em um custo de 1; os + 1s na parte inferior da "cerca" garantem que todas as colunas colocadas à sua direita não ocorram esse custo.

Claramente, uma solução de VC usando no máximo k vértices produz uma solução para a instância de CO construída com custo no máximo k : basta ordenar que as colunas correspondentes aos vértices no vértice cubram arbitrariamente, seguidas pela coluna fence, seguida por todas as colunas restantes em qualquer ordem .

Resta mostrar que uma solução para a instância de CO com custo no máximo k corresponde a uma cobertura de vértice com no máximo k vértices.

Suponha que, ao contrário, exista uma solução para a instância de CO com custo no máximo k que deixe alguma linha nas linhas superiores (n+1)m com -1 antes de +1. Esta linha pertence a um bloco de (n+1) linhas correspondentes a uma aresta específica uv . Cada linha neste bloco na instância original A é idêntica por construção; colunas permutadoras podem alterar essas linhas, mas não afetam o fato de serem idênticas. Assim, cada uma dessas n+1 linhas idênticas tem -1 antes de +1 na solução, implicando um custo de pelo menosn+1 . Maskn<n+1 : contradição.

Como cada um dos m blocos de linhas nas linhas superiores (n+1)m tem +1 antes de -1, cada uma das arestas correspondentes é coberta por um vértice correspondente a uma coluna à esquerda da cerca: isto é , esse subconjunto de vértices constitui uma cobertura de vértice. Como nenhuma das linhas superiores (n+1)m tem -1 antes de +1, o único local em que o custo pode acumular-se na solução é nas n linhas inferiores , das colunas colocadas à esquerda da cerca. Cada uma dessas colunas custou exatamente 1, portanto, dado que o custo é no máximo k , deve haver no máximo kcolunas e, portanto, no máximo k vértices na capa.

Finalmente, é claro que a instância CO pode ser construída em tempo polinomial a partir da instância VC, o que significa que, se um algoritmo de tempo polinomial existisse para resolver CO, qualquer instância VC também poderia ser resolvida em tempo polinomial construindo primeiro uma instância CO, conforme descrito acima e depois resolvê-lo. Como VC é NP-difícil, CO também é.

j_random_hacker
fonte
Sempre que há uma resposta tão boa, me faz pensar se as "Perguntas sobre a rede quente" devem ser substituídas ou associadas a algo como "Respostas valiosas à rede".
John L.
Você poderia esclarecer como encontrar a resposta? Isso deve ser ainda mais esclarecedor do que a resposta em si.
John L.
11
@ Apass.Jack: Obrigado! :) Não tenho uma estratégia especial e posso passar muito tempo andando na direção errada. Por exemplo, passei muito tempo pensando que poderia reduzir o ciclo Hamiltoniano (que é semelhante no que diz respeito a ordenar elementos) antes de perceber que minha construção permitiria configurações correspondentes aos subtores e, portanto, não funcionaria. Como regra, eu sempre tento reduções de Vertex Cover ou Partition, então talvez Clique. "Valuable Rede de Respostas" soa como uma grande idéia :)
j_random_hacker
11
@ Apass.Jack: Uma idéia geral útil é pensar em como você pode "escalar" uma instância de problema-alvo sem alterar sua resposta - por exemplo, se o problema-alvo (o que estamos tentando provar com seriedade) for Vertex Cover, fazendo qualquer positivo número inteiro cópias separadas do gráfico e também multiplicar o limite k por r deixam a resposta inalterada. Geralmente, você deseja que certas violações (soluções de destino que não correspondem a soluções de origem válidas) "superem" outras e, nesse caso, você pode "multiplicar" os gadgets que correspondem à violação mais importante. rkr
Jrandom_hacker 28/03/19
11
Para a redução na minha resposta, queremos codificar uma instância de um problema em que haja duas "forças": tente cobrir todas as arestas e tente usar o menor número possível de vértices. A primeira é mais importante aqui, então eu "multipliquei" as linhas correspondentes às arestas: agora uma única violação de aresta custa , o que significa que é pior perder uma única aresta do que incluir todos os vértices. E agora percebi que deveria editar a resposta para deixar explícito que estamos lidando com as versões do problema de decisão desses dois problemas, nas quais os parâmetros de limite fazem parte da instância do problema ...n+1
j_random_hacker
2

Não sei se existe realmente uma solução polinomial. No entanto, com base no comentário de Pål GD, você pode criar uma função de simplificação. A matriz inicial é simplificated como a construir a sequência de saída 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

Então você deve fazer uma exploração completa da combinatória usando iterativamente a seleção de função:

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

Depois de cada escolha, você pode fazer uma simplificação para reduzir o número de possibilidades a explorar. Sugiro explorar avidamente começando com a coluna com menos -1, assim você pode alcançar um limite inferior, fazendo um critério de parada.

No exemplo dado, a primeira simplificação fornece (como Pål GD explicou no comentário)

  • S[0]=c3 , remova r1, r3
  • S[1]=c4 , remova r4
  • S[2]=c2 isso permite uma matriz simples para explorar.
    [1111]

[110000110000001100001100000011000011]

No entanto, a simplificação ainda poupa cerca de metade das etapas de exploração. E esse tipo de matriz pode ser dividido em várias sub-matrizes independentes.

Optidad
fonte
11
@ Apass.Jack eu editei para ser mais preciso. Sim, eu quis dizer a posição da coluna na sequência de saída.
Optidad 19/03/19
Promovido como etapa de simplificação pode ser bom o suficiente para fins práticos (como exercícios de programação on-line?).
John L.
Obrigado, na verdade, eu estava interessado em estimar o custo do tempo amortizado, mas realmente não sei como fazer. Isso é possível ? Ou é muito dependente de problemas?
Optidad 19/03/19
2
ijijjij
11
ijijijijikk