O que se sabe sobre a complexidade do seguinte problema:
- Dado: números racionais .
- Saída: números inteiros .
- Objetivo: minimizar onde
Ou seja, gostaríamos de arredondar os números racionais para números inteiros para minimizar a soma dos erros em distâncias aos pares. Para cada par , gostaríamos de ter a distância arredondada mais próximo possível da distância real .
Motivação: uma viagem de metrô chata e um pôster que mostra os "locais" das estações na resolução de um minuto do tempo de viagem. Aqui estamos minimizando o erro que as pessoas fazem, se eles usam o cartaz de olhar para cima o tempo de viagem entre as estações e , média sobre todos os pares .
Por exemplo, aqui podemos ler as seguintes aproximações das distâncias em pares entre as quatro estações (usando A, B, C, D por questões de brevidade):
- A – B ≈ 1 minuto, B – C ≈ 2 minutos, C – D ≈ 2 minutos
- A – C ≈ 3 minutos, B – D ≈ 4 minutos
- A – D ≈ 5 minutos
Essa é a melhor aproximação possível? Se você soubesse o tempo real da viagem, poderia encontrar uma solução melhor?
A princípio, isso soou como um exercício simples de programação dinâmica, mas agora parece que é necessário um pouco de pensamento real.
Alguém reconhece esse problema? Ou vê um algoritmo inteligente para resolvê-lo?
Editar: Existem algumas variantes naturais da pergunta que foram mencionadas nos comentários; vamos dar a eles alguns nomes:
versão piso / teto : é necessário que para todos os i .
número inteiro versão: é suficiente que para todos os i .
versão monotônica : é necessário que .
versão não monotônica : podemos ter para i < j .
A pergunta original considera a versão inteira monotônica, mas respostas relacionadas a qualquer uma dessas versões são bem-vindas.
fonte
Respostas:
ESTÁ BEM. O algoritmo DP parece ser desnecessariamente complicado. Depois de ler os comentários, acho que isso pode resolver a versão monotônica do problema (mas não verifiquei todos os detalhes).
Primeiro, assuma que , onde ⌊ x i ⌋ é a parte integrante, { x i } é a parte fracionária. Suponha x i é arredondado para ⌊ x i ⌋ + v i , onde v i é um inteiro não negativo (é claro que, em geral, v i pode ser negativo, mas podemos sempre mudar, de modo que o menor v i é 0).xi=⌊xi⌋+{xi} ⌊xi⌋ {xi} xi ⌊xi⌋+vi vi vi vi
Agora, considere o custo de um par , x j ao fazer esse arredondamento. O custo deve serxi xj
A expressão é complicada por causa dos valores absolutos. No entanto, observe que temos monotonicidade; portanto, as coisas dentro dos dois valores absolutos internos devem ter o mesmo sinal. Como temos um valor absoluto externo, realmente não importa qual é esse sinal, a expressão simplesmente simplifica
A partir de agora, não assumimos que a solução seja monotônica, mas alteramos o objetivo de minimizar a soma do termo acima para todos os pares. Se a solução para esse problema for monotônica, é claro que também é a solução ideal para a versão monotônica. (Pense nisso como: o problema original tem uma penalidade infinita quando a solução não é monotônica, o novo problema tem uma penalidade menor, se uma solução monotônica vence mesmo na nova versão, deve ser a solução para a versão monotônica)
Agora gostaríamos de provar, se , na solução ótima, devemos ter v i ≥ v j .{xi}>{xj} vi≥vj
Suponha que isso não seja verdade, que temos um par mas v i < v j . Mostraremos que, se trocarmos v i v j, a solução ficará estritamente melhor.{xi}>{xj} vi<vj vi vj
Primeiro vamos comparar o prazo entre e j , aqui é muito claro que a troca é estritamente melhor porque na versão não-swap, v i - v j e { x j } - { x i } tem o mesmo sinal, o absoluto value será a soma dos dois valores absolutos.i j vi−vj {xj}−{xi}
Agora, para qualquer , comparamos a soma dos pares ( i , k ) e ( j , k ) . Ou seja, precisamos comparark (i,k) (j,k)
e | v j - v k - ( { x i } - { x k } ) | + ||vi−vk−({xi}−{xk})|+|vj−vk−({xj}−{xk})| .|vj−vk−({xi}−{xk})|+|vi−vk−({xj}−{xk})|
Uso , B , C , D para denotar as quatro condições no interior do valor absoluto, é evidente que A + B = C + D . Também está claro que | A - B | ≥ | C - D | . Pela convexidade do valor absoluto, sabemos | Um | + | B | ≥ | C | + | D | . Assuma a soma de todos os x kA B C D A+B=C+D |A−B|≥|C−D| |A|+|B|≥|C|+|D| xk sabemos que a troca só pode ser melhor.
Observe que agora já temos uma solução para a versão monotônica de piso / teto: deve haver um limite, quando for maior sempre arredondado, quando for menor sempre arredondado, quando for igual arredondado alguns e outros enquanto a qualidade da solução depende apenas do número. Enumeramos todas essas soluções e escolhemos a que tem a menor função objetiva. (Todas essas soluções são necessariamente monotônicas).{xi}
Finalmente, gostaríamos de ir para a versão inteira monotônica do problema. Na verdade, podemos provar que a solução ideal é a mesma da versão monotônica de piso / teto.
Como assumimos, o menor é 0. Grupo todo o x i 's de acordo com sua v i ' s, e chamá-los grupo 0 , 1 , 2 , . . . , max { v i } . Primeiro provaremos que não há grupos vazios, mas isso é simples, se o ésimo grupo estiver vazio, pois qualquer deixe . É fácil ver que a função objetivo sempre melhora (basicamente porque ).vi xi vi 0,1,2,...,max{vi} v i > k v i = v i - 1 | { x i } - { x j } | < 1k vi>k vi=vi−1 |{xi}−{xj}|<1
Agora vamos provar que a média de no grupo é pelo menos a média de no grupo mais . Se isso não for verdade, basta deixar para todos os , o cálculo novamente mostra que a função objetivo melhora.k + 1 { x i } k 1 / 2 v i = v i - 1 v i > k{xi} k+1 {xi} k 1/2 vi=vi−1 vi>k
Como a média de está no intervalo , realmente existem no máximo dois grupos, o que corresponde à versão de piso / teto.[ 0 , 1 ){xi} [0,1)
fonte
Apenas um comentário prolongado ... (talvez trivial e / ou errado :)
Se e é o múltiplo menos comum dos s, então podemos nos livrar dos racionais: . M b i x ′ i = M ∗ x ixi=ai/bi M bi x′i=M∗xi
Se (restrição de piso, teto), podemos usar variáveis binárias para expressar usando sua distância de ( ou ):v i y ' i x ' i L i = x ' i - M * ⌊ x i ⌋ R i = x ' i - M * ⌈ x i ⌉yi∈{⌈xi⌉,⌊xi⌋} vi y′i x′i Li=x′i−M∗⌊xi⌋ Ri=x′i−M∗⌈xi⌉
E o problema original deve (?!?) Ser equivalente a encontrar o que minimiza:vi
comvi∈{0,1},Di∈Z
fonte
Outro comentário estendido ... Pode estar errado.
Também estou considerando o caso com restrições de piso / teto, e estou tentando resolvê-lo usando programação dinâmica (não posso, mas talvez funcione quando o divisor comum é pequeno).
Seja a parte fracionária de , consideramos as coisas do menor ao maior. Suponha que o maior seja e, como estamos fazendo programação dinâmica, já sabemos "alguma coisa" (explicarei o que é isso) sobre a solução ideal para todo o resto, exceto .{xi} xi {xi} {xk} xk
Agora considere a diferença na função objetivo quando arredondarmos cima ou para baixo. Se originalmente algum é arredondado, então a diferença é simplesmente 1 (não foi verificado com muito cuidado, mas parece que é esse o caso, é realmente importante que não importa se esteja à esquerda ou à direita de , a diferença é sempre o mesmo); se originalmente algum for arredondado para baixo, a diferença será . Portanto: sabemos qual decisão tomaremos se as três quantidades a seguir forem conhecidas:x i x i x k x i 2 { x k } - 2 { x i } - 1xk xi xi xk xi 2{xk}−2{xi}−1
OK, 1 e 2 são essencialmente os mesmos, podemos permitir que f [N, Ndown, Sdown] seja a solução ideal para os primeiros N pontos (quando os pontos são classificados em ordem crescente de ), o número de O arredondamento de é Ndown, e a soma de para os arredondados é Sdown. Então não é difícil escrever como ir de f [N-1] para f [N].x i { x i }{xi} xi {xi}
O problema é claro, Sdown pode ter muitos valores exponencialmente. Mas funciona quando o divisor comum é pequeno ou podemos arredondar tudo para um ponto de grade primeiro e obter um FPTAS (se o programa dinâmico acima estiver correto ...)
fonte