Esse problema de viagem é ideal sob prazos NP-difíceis nas árvores?

Um de meus amigos me pergunta o seguinte problema de agendamento na árvore. Eu acho que é muito limpo e interessante. Existe alguma referência para isso?

Problema: existe uma árvore , cada aresta tem um custo de deslocamento simétrico de 1 . Para cada vértice , há uma tarefa que precisa ser executada antes do prazo . A tarefa também é indicada como . Cada tarefa possui o valor uniforme 1. O tempo de processamento é 0 para cada tarefa , ou seja, visitar uma tarefa antes que seu prazo seja igual ao seu término. Sem perda de generalidade, deixe denotar a raiz e assumindo que não há tarefa localizada em . Existe um veículo na no tempo 0. Além disso, assumimos que para cada vértice , $T(V,E)$ $v_i$ $d_i$ $v_i$ $v_0$ $v_0$ $v_0$ $d_i \ge dep_i$ $dep_i$ representa a profundidade de . Isso é evidente, o vértice com prazo inferior à sua profundidade deve ser considerado um erro. O problema pede para encontrar um agendamento que conclua o maior número possível de tarefas. $v_i$

Progresso:

Se a árvore estiver restrita a um caminho, será em através de programação dinâmica. $\mathsf{P}$
Se a árvore for generalizada para um gráfico, ela estará em concluída. $\mathsf{NP}$
Eu tenho um algoritmo ganancioso muito simples, que é acreditado por 3 fatores. Eu não provei isso completamente. Agora, estou mais interessado nos resultados difíceis de NP. :-)

Obrigada pelo Conselho.

ds.algorithms graph-algorithms np-hardness Peng Zhang
fonte

Em um gráfico completo, a tarefa seria fácil, certo? Basta usar um algoritmo guloso simples ...

Joe

@ Joe: Sim. Como toda borda precisa de uma unidade viajando, não há preferência entre "encruzilhadas". Você ainda está interessado neste problema, se sim. talvez possamos conversar por e-mail. :-)

Peng Zhang

E se todos os prazos forem iguais e / ou apenas perguntarmos se todas as tarefas podem ser concluídas?

22612 domotorp

@domotorp: Se pedir para concluir todas as tarefas com um prazo, a resposta é SIM se e somente se o prazo uniforme. Basta pesquisar primeiro a profundidade. Quanto ao problema ideal no caso, Não sei se é fácil. Existem muitas variantes sobre esse problema, como considerar se os prazos receberão valores de um conjunto finito cuja cardinalidade é uma constante? Muito obrigado pelo seu comentário.

d \geq | V |

$d\ge |V|$

d < | V |

$d< |V|$

Peng Zhang

Eu diria que NP-hard vê o zoológico de agendamento , exceto se eu não entendi o seu problema.

Gopi

Respostas:

Não tenho certeza se esta é sua resposta (veja abaixo), mas um pouco demais para os comentários.

Eu pensei que seu problema era algo como: , onde: $(P|tree;p_i=1|\Sigma T_i)$

$P$ significa processadores homogêneos idênticos,
"árvore" significa restrição de precedência na forma de uma árvore,
$p_i=1$ significa que o peso das tarefas é igual a 1 e
$\Sigma T_i$ significa minimizar a soma do atraso (ou seja, o número de tarefas que terminam após o prazo).

Se for esse o caso, seu problema é difícil: você pode vê-lo como uma generalização de Minimizando o atraso total em uma única máquina com restrições de precedência . De fato, este documento afirma que, para várias cadeias lineares, é NP-hard em um único processador. A transformação fácil é levar as árvores da forma uma raiz e cadeias lineares a partir da raiz.

No entanto, estou surpreso porque você parece dizer que, no caso de uma única cadeia linear, você usaria a Programação Dinâmica. Não vejo por que você precisaria de DP, pois me parece que, ao programar uma única cadeia linear, você não tem muita escolha devido às restrições de precedência: apenas uma única opção. Talvez eu tenha entendido mal o seu problema.

Gopi
fonte

Meu problema parece diferente do seu. A minha é: "uma árvore enraizada, com custo unitário de ponta, cada vértice com uma tarefa com seu prazo final, tarefa que não precisa de tempo para recuar. A partir da raiz, quantas tarefas podem ser concluídas?". Portanto, não há precedência, não há tempo necessário para processar uma tarefa. Muito obrigado.

Peng Zhang

@PengZhang, se for uma árvore enraizada, há precedência? Quanto ao custo nas bordas (precedência?) Ou nas tarefas, parece-me a mesma coisa. Realmente não vejo a diferença entre os dois. Finalmente, quantas tarefas podem ser concluídas, se você minimizar o número de tarefas que terminam após o prazo final, isso equivale a maximizar o número de tarefas que podem ser concluídas. Talvez você possa desenhar o que está esperando?

Gopi

Não vejo a clara relação entre dois problemas. No problema original, o custo de visitar um próximo nó depende de qual nó foi visitado na etapa anterior. No planejamento com restrição de precedência, o custo de um próximo trabalho a ser processado não depende de qual trabalho foi processado na etapa anterior, desde que a restrição de precedência seja atendida.

Yoshio Okamoto

@ Gopi: o custo das bordas não pode ser "transferido" para os nós, tanto quanto eu penso. Se a árvore estiver restrita a um caminho (talvez a cadeia que você referiu), no meu problema, podemos programar dinamicamente da seguinte maneira. Deixe os vértices numerados como da esquerda para a direita. Deixe denotar as tarefas máximas do intervalo de posição no tempo e o veículo está em . Seja o mesmo que exceto que o veículo está em . Então temos que pode ser derivado de . Porque

1, 2, \dots, n

$1,2,\cdots, n$

f (t, l, r)

$f(t,l,r)$

[l, r]

$[l,r]$

t

$t$

l

$l$

g (t, l, r)

$g(t,l,r)$

f (t, l, r)

$f(t,l,r)$

r

$r$

f (t, l, r)

$f(t,l,r)$

{f (\cdot, l + 1, r), g (\cdot, l, r - 1)

$\{f(\cdot,l+1,r), g(\cdot,l,r-1)$

t, l, r

$t,l,r$ são polinomiais, então o dp é polinomial.

Peng Zhang

@PengZhang, ok, acho que entendo melhor o que você quer dizer. Eu ainda acredito que se pode adaptar facilmente o papel que dei, considerando árvores especiais onde os galhos são caminhos (por isso, caminhos enraizados).

Gopi

Para que isso seja verdade, temos que fazer algumas suposições. Veja os comentários abaixo

Para o caso em árvore, acredito que exista um algoritmo de programação dinâmica recursiva em tempo polinomial parametrizado pelo tempo máximo de prazo. Os subproblemas são: se uma subárvore no tempo e da subárvore no tempo , qual é o número máximo de tarefas que podemos concluir na subárvore? Os casos básicos nas folhas são fáceis e memorizamos de baixo para cima. $t_a$ $t_b$

Se realmente parametrizamos pelo prazo máximo de prazo, o algoritmo não seria realmente polinomial no tamanho da árvore. No entanto, o comprimento do caminho mais longo que visita todos os nós da árvore é apenas polinomial em, e nunca precisamos verificar os prazos até depois disso. $|V|$

Joe
fonte

Você pode me mostrar a recorrência? Eu tentei o mesmo que o seu antes, deixe denotar o subproblema de visitar a subárvore enraizada no vértice . Mas existem dois problemas. 1. Como você pode criar sua solução a partir dos subproblemas? Tanto quanto penso, enumerar a ordem dos filhos é inevitável. 2. Você pode entrar e sair de um nó várias vezes. Portanto, durante o intervalo de tempo , você pode visitar outros vértices que não estão na subárvore com raiz em . Muito obrigado. :-)

f [a, t, t^{'}]

$f[a, t, t']$

a

$a$

[t, t^{'}]

$[t,t']$

a

$a$

Peng Zhang

o ponto (1) não é tão problemático quanto o ponto (2). Para que minha ideia funcione como eu a imaginava, é necessário que você não saia e entre novamente em uma subárvore várias vezes. Não é óbvio que a melhor solução não pula por toda a árvore: pega uma folha e algo perto da raiz e caminha até uma folha e depois para outra folha longe dos outros 2, etc. Você pode para explorar o fato de que você obterá todos os nós em qualquer caminho que você percorrer. Em particular, se alguma criança foi visitada, o pai já foi visitado.

8282 Joe

: No meu pensamento, o ponto (1) é realmente um problema . Para o ponto (2), chamei a restrição de "não reinserir" como restrição de "Primeira pesquisa de profundidade". A restrição DFS é comumente adotada nas literaturas. E sob essa restrição, meu problema é de fato polinomial, desde que o grau máximo da árvore seja constante . Então, eu me pergunto, minha pergunta é NP-difícil. Muito obrigado.

Peng Zhang

Em relação à restrição DFS, é fácil construir um exemplo em que a sequência ideal viola essa restrição. Considere uma árvore binária completa e equilibrada com 7 nós. Deixe as 2 folhas na subárvore esquerda com prazos 2 e 12, as 2 folhas na subárvore direita com prazos 8 e 6 e os nós internos com prazos 100. Você pode visitar todos os nós visitando as folhas na ordem 2,6,8 12; qualquer outro pedido viola pelo menos um prazo.

Mhum

O problema de obter uma aproximação constante para este caso ou provar que o NP-Hard ainda está aberto e qualquer resultado seria uma boa publicação. Alguns casos especiais foram resolvidos. Eu, juntamente com outros, tenho alguns resultados parciais que resolvem casos especiais como aranhas, árvores de altura constante. Mas, o problema geral das árvores não está resolvido.

vgta
fonte