Separando números com uma diferença mínima

7

Dado é um número inteiro positivo , e os números com para cada . Qual é a complexidade de decidir se existem números inteiros modo que para todos os e para todos os ?na1,b1,,an,bnaibiic1,,cnaicibii|cicj|2i,j

O que pode ser observado é que um algoritmo ganancioso, em que assumimos que e escolhemos acordo com essa ordem, não necessariamente funciona. Por exemplo, podemos ter . Colocando não funciona (que não deixa espaço para ), mas o que funciona é colocar e . O problema é talvez NP-difícil?a1ancia1=1,b1=4,a2=b2=2c1=1c2c1=4c2=2

pi66
fonte
11
Você já pensou em programação dinâmica?
John L.
Sim. O problema é que não sabemos a ordem dos 's, portanto, não conseguimos armazenar, por exemplo, a "melhor" solução usando no lado esquerdo. cic1,,ck
pi66 28/06/19
Você poderia adicionar uma referência ao problema original?
John L.
Eu não tenho uma referência. Eu estaria interessado se alguém conhece um.
pi66 28/06/19

Respostas:

5

Conforme mostrado na resposta anterior, esse problema pode ser modelado como um problema de agendamento com datas de lançamento e vencimento. No entanto, a heurística de Schrage funciona apenas para o casopj=1 (todos os tempos de processamento são 1) ou quando as datas de lançamento e vencimento concordarem (ou seja, há um pedido que r1rn e d1dn)

Para o caso pj=palgoritmos polinomiais foram encontrados por Simons (1978) , Carlier (1981) e Garey et al. (1981) , correndo no tempoO(n2logn), O(n2logn)e O(nlogn), respectivamente.

O algoritmo de Garey et al. agenda tarefas de unidade de tempo, mas permite liberação arbitrária e datas de vencimento. O problema acima pode ser reduzido a essa configuração dividindo todas as datas e tempos de processamento porp. A idéia principal do algoritmo é encontrar um conjunto de regiões proibidas em que nenhuma tarefa tem permissão para iniciar. Eles mostram que a heurística de Schrage, ao respeitar as regiões proibidas, encontra um cronograma possível de produção mínima. Ao construir as regiões proibidas, seu algoritmo também pode detectar inviabilidade.

Para ver como o algoritmo funciona, primeiro observe um problema mais simples: agende n tarefas em tempo de unidade entre uma data de lançamento r e um prazo d respeitando regiões proibidas F=i(ai,bi), onde cada região (ai,bi)é um intervalo aberto. (Observe que não estamos preocupados com a liberação e as datas de vencimento de tarefas individuais.)

Esse problema pode ser resolvido por Backscheduling : defina um horário de início da sentinelasn+1=d, e para i=n,n1,,1 definir hora de início si até a última hora, o mais tardar si+11 isso não é proibido.

Escreva B(r,d,n,F) para uma aplicação de Backscheduling para as entradas acima e defina o valor de retorno como s1, a data de início mais recente possível para agendar o ntarefas. Agora seB(r,d,n,F)<r não há cronograma viável para o ntarefas. Além disso, serB(r,d,n,F)<r+1 nenhuma outra tarefa pode começar em (B(r,d,n,F)1,r) pois, caso contrário, não há novamente um cronograma viável para o n tarefas e, portanto, (B(r,d,n,F)1,r) pode ser declarada uma região proibida.

Acontece que essa lógica é suficiente para encontrar todas as regiões proibidas necessárias para fazer o trabalho heurístico de Schrage. Suponha que as tarefas sejam ordenadas de forma quer1r2rn e escreva n(r,d) para o número de tarefas liberadas e vencidas no intervalo fechado [r,d].

  1. conjunto F=
  2. para tarefas i=n,n1,,1:
  3.   c=min{B(ri,dj,n(ri,dj),F)j:djdi}
  4.   E se c<ri: retornar "sem agenda viável"
  5.   senão se ric<ri+1: definir F=F{(c1,ri)}

Uma implementação direta, como acima, levaria tempo O(n4). Garey et al. mostre (além da exatidão) que, atualizando os tempos obtidos pelo Backscheduling, juntando regiões proibidas sobrepostas e fazendo consultas "proibidas"O(1) tempo pode ser reduzido a O(n2)e usando estruturas de dados ainda melhores para O(nlogn).

Marcus Ritt
fonte
11
Parece promissor, mas o primeiro e o último link vão para paywalls e o segundo leva a um certificado quebrado e à página "500 Internal Server Error" para mim. Você poderia resumir um dos algoritmos ou fornecer um link acessível publicamente? Obrigado!
Jrandom_hacker 30/06/19
Desculpe, parece difícil encontrar esses artigos. O artigo de Carlier está no Research Gate, mas está em francês. Vou ver se posso fornecer um breve resumo.
Marcus Ritt
Isso seria ótimo, obrigado :)
j_random_hacker
0

Seu problema é conhecido como agendamento não preventivo de máquina única, com prazos e prazos de liberação, com tarefas de duração idêntica, e pode ser resolvido com eficiência usando a heurística gananciosa de Schrage.

Vamos primeiro descrever o problema de maneira mais formal. Nos é dada uma sequência de intervalos de tempo[ri,di] e uma sequência de comprimentos de trabalho pi. Queremos agendar cada trabalho dentro do seu intervalo, para que não haja dois trabalhos cruzados.

No nosso caso ri=ai, di=bi+2e pi=2. O horário de início de cada trabalhoci satisfaz assim aicibi, e dois trabalhos entram em conflito se (ci,ci+2) cruza (cj,cj+2), que é o mesmo que |cicj|<2. (Sem perda de generalidade, todos os trabalhos são agendados em horários inteiros.)

A heurística de Schrage é uma heurística comum que é ótima em alguns casos, embora não necessariamente essa. No entanto, existem outros algoritmos na literatura que resolvem esse problema com eficiência.

Yuval Filmus
fonte
2
A heurística de Schrage é ótima apenas para pj=1 não para pj=p (toma r=(01), d=(53), p=(22)) Algoritmos polinomiais parapj=pforam dados por Simons (1978), Carlier (1981) e Garey et al. (1981), este último emO(nregistron).
Marcus Ritt
@ MarcusRitt Concordo que a heurística não funciona. Você poderia fornecer os links (ou pelo menos os títulos) para suas referências?
pi66 29/06/19
Não vejo como o valor de pentra em cena. Você pode dividir tudoppara obter trabalhos de comprimento unitário.
Yuval Filmus
11
@YuvalFilmus Sim, mas as datas de lançamento e vencimento podem não ser mais inteiras, o que dificulta o problema. Na verdade, Garey et al. (1981) resolvem o problema de tempo unitário com datas não inteiras, e seu algoritmo pode ser aplicado depois de dividir tudo porp.
Marcus Ritt
0

Seja A o menor dos ai. Depois, há duas opções para a primeiraci escolher que obviamente não pode ser melhorado: Primeiro, encontre o i tal que ai=A e bi é o menor possível, então deixe ci=ai. Dois, escolha j de modo queaj=A+1, bj<bie bj o menor possível, então deixe cj=bj(isso pode não ser possível). Em seguida, remova esse item da lista de intervalos, atualize todosaEu ser maior em dois do que o cEu que foi escolhido e verifique se não bEué muito pequeno. A primeira pesquisa profunda e o backtracking encontrarão uma solução.

Há uma boa chance de que isso seja rápido, pois a primeira escolha não é ruim como heurística.

Se houver exatamente k intervalos com umaEu<UMA para alguns A, e encontramos valores de k cEu<=UMA-2 então estes cEusão ideais e o retorno para esses itens k não pode ajudar e nunca será necessário. Por outro lado, se houver muitos valoresbEu muito próximos, que podem ser usados ​​para provar que não há solução.

Finalmente, o problema pode ser abordado a partir do menor umaEuou igualmente bem das maiores bEu.

gnasher729
fonte