Arredondamento para minimizar a soma dos erros em distâncias aos pares

25

O que se sabe sobre a complexidade do seguinte problema:

  • Dado: números racionais x1<x2<<xn .
  • Saída: números inteiros y1y2yn .
  • Objetivo: minimizar
    1i<jne(i,j),
    onde
    e(i,j)=|(yjyi)(xjxi)|.

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 i,j , gostaríamos de ter a distância arredondada yjyi mais próximo possível da distância real xjxi .


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 i e j , média sobre todos os pares i<j .

mapa de rotas

(fonte)

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 .yi{xi,xi}i

  • número inteiro versão: é suficiente que para todos os i .yiZi

  • versão monotônica : é necessário que .y1y2yn

  • versão não monotônica : podemos ter para i < j .yi>yji<j

A pergunta original considera a versão inteira monotônica, mas respostas relacionadas a qualquer uma dessas versões são bem-vindas.

Jukka Suomela
fonte
O DP funciona para o caso quando você se importa apenas com medições adjacentes?
Suresh Venkat
1
@SureshVenkat: Na verdade, nesse caso, o problema se torna muito simples: basta selecionar a melhor distância integral para cada i . Ou seja, você pode minimizar cada e ( i - 1 , i ) independentemente. yiyi1ie(i1,i)
Jukka Suomela
4
Este relatório de Estie Arkin parece relacionado: ams.sunysb.edu/~estie/papers/beautification.pdf Está provado que minimizar o número de distâncias interpontos distintas na saída é difícil para NP. Essa não é a soma total de turnos, como nessas perguntas, mas talvez os dispositivos de dureza no relatório possam sugerir uma prova de dureza para esse problema.
val
2
Tenho a sensação de que esse problema certamente deve ser solucionado usando técnicas conhecidas. Vamos ver se a recompensa é suficiente para motivar as pessoas a resolver isso. :)
Jukka Suomela
1
@vzn: Estou interessado na complexidade computacional deste problema. Se você puder provar que existe uma abordagem de pesquisa local em tempo polinomial que garante o melhor global, a recompensa é sua.
Jukka Suomela 28/08/12

Respostas:

9

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}xixi+vivivivi

Agora, considere o custo de um par , x j ao fazer esse arredondamento. O custo deve serxixj

||vivj+xixj||{xi}{xj}+xixj||

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

|vivj({xi}{xj})|

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 iv j .{xi}>{xj}vivj

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<vjvi 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.ijvivj{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 } ) | + ||vivk({xi}{xk})|+|vjvk({xj}{xk})|.|vjvk({xi}{xk})|+|vivk({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 kABCDA+B=C+D|AB||CD||A|+|B||C|+|D|xksabemos 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 ).vixivi0,1,2,...,max{vi}v i > k v i = v i - 1 | { x i } - { x j } | < 1kvi>kvi=vi1|{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}k1/2vi=vi1vi>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)

Rong Ge
fonte
1

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/biMbixi=Mxi

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 iR i = x ' i - M * x iyi{xi,xi}viyixiLi=xiMxiRi=xiMxi

yi=xi+Livi+Ri(1vi)=xi+(LiRi)vi+Ri=xi+Divi+Ri

E o problema original deve (?!?) Ser equivalente a encontrar o que minimiza:vi

1i<jn|DiviDjvj|

comvi{0,1},DiZ

Marzio De Biasi
fonte
expandindo seu último somatório usando o erro idéia acima, poderia ser mostrado que o ideal é realmente apenas a escolha em que cada variável binária piso / teto está mais próxima de ? portanto, resta apenas o caso de como arredondar para no formato que é um número inteiro. x n x n m n + 1e(i,j)xnxn mmn+12m
vzn
1
@ vzn: Eu acho que isso é um contra-exemplo. Se arredondarmos usando os critérios de arredondamento , obtemos que tem um erro de , mas tem um erro de (o resultado é o mesmo se eliminamos os racionais multiplicando pelo LCM). (0,1.4,8.7)xi(0,1,9)1.4(0,2,9)1.2
Marzio De Biasi
ok, no entanto, nova idéia. considere novamente. expanda a soma. isso reduzirá a muitos termos com e também . mas o último é igual a ! portanto, reduz-se a um problema na forma de minimizar que é um vetor de linha 0/1 e é um vetor de coluna constante . verdade? então isso é trivial e apenas selecione o modo que seja 1 se o elemento correspondente em for negativo e 0 se for positivo .... QED? e(i,j)vivi2viXDXDXD
vzn
1
@vzn: se você usar o para eliminar a função de valor absoluto, obterá termos como ; como você lida com eles na minimização? ((yiyj)(xixj))22DiDjvivj
Marzio De Biasi
oops! você respondeu antes que eu tivesse a chance de excluir esse comentário depois de perceber isso ... mesmo assim ainda parece reduzir a algum problema de otimização de matriz quase linear? também com um termo onde é um vetor de coluna ...? VVTV
vzn
1

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 } - 1xkxixixkxi2{xk}2{xi}1

  1. quantas coisas são arredondadas
  2. quantas coisas são arredondadas
  3. qual é a soma de entre os que são arredondados para baixox i{xi}xi

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 ...)

Rong Ge
fonte
DiDivi(N1)DkDivi
Di|Divi|Ndown|Dk|+NupDkDivivjvj
xi=1.1xk=1.9xixkxk
Jukka Suomela 29/08/2012
1
{xi}{xi}
1
{xi}<{xj}{xk}{xi}{xj}{xk}xixjxjxi
Rong Ge