Ordenação topológica positiva

Suponha que eu tenha um gráfico acíclico direcionado com pesos em número real em seus vértices. Quero encontrar uma ordem topológica do DAG em que, para cada prefixo da ordem topológica, a soma dos pesos não seja negativa. Ou, se você preferir a terminologia teórica da ordem, tenho uma ordem parcial ponderada e desejo uma extensão linear de modo que cada prefixo tenha um peso não negativo. O que se sabe sobre esse problema? É NP completo ou solucionável em tempo polinomial?

Esse problema parece ser muito semelhante ao SEQUENCING PARA MINIMIZAR O CUSTO CUMULATIVO MÁXIMO, problema [SS7] na Garey & Johnson . A saber:

INSTÂNCIA: Defina de tarefas, ordem parcial em , um "custo" para cada (se , pode ser visto como um "lucro") , e uma constante .$T$$\prec$$T$$c(t) \in Z$$t \in T$$c(t) < 0$$K \in Z$

PERGUNTA: Existe uma programação um processador para que obedece às restrições de precedência e que possui a propriedade de que, para cada tarefa , a soma dos custos de todas as tarefas com é no máximo ?$\sigma$$T$$t \in T$$t'$$\sigma(t') \leq \sigma(t)$$K$

Estou incerto se o problema permanece NP-completo quando é fixado a 0. G & J menção de que o problema permanece NP-completo se para todos os .$K$$c(t) \in \{-1,0,1\}$$t \in T$

Bem, minha resposta é minha pergunta, da qual se conclui que se você pudesse resolver esse problema em P, também poderia resolver outro problema em aberto: ordenação topológica positiva, faça 3

Editar: esse problema também se mostrou NP-completo, portanto seu problema já está NP-completo se o seu DAG tiver apenas dois níveis, ou seja, se não houver caminhos direcionados com duas arestas.

Se eu entendi o problema corretamente, acho que o problema de planejamento de máquina única com restrição de precedência para minimizar a soma ponderada dos tempos de conclusão (1 | prec | \ sum wc) pode ser reduzido ao problema que você está interessado. No problema 1 | prec | \ sum wc, temos n trabalhos, cada um com um peso não negativo e um tempo de processamento, um poset nos trabalhos e queremos uma extensão linear dos trabalhos, de modo que a soma ponderada dos tempos de conclusão dos trabalhos seja minimizado. O problema é NP-completo, apesar de assumirmos que o tempo de processamento de cada trabalho é igual a 1. Faz algum sentido?

E se sempre pegarmos o elemento máximo (na ordem parcial) com o menor peso. Depois de esgotarmos os elementos, devolvemos-os em ordem inversa à saída.

Esse problema me lembra muitas árvores de decisão. Eu consideraria esse tipo de solução, que tenta sempre escolher o caminho mais promissor, mas olhando para todo o subgráfico:

A partir dos nós do coletor, trabalhe em direção às fontes, um nível de cada vez. Enquanto você faz isso, dê um peso a cada borda. Esse peso deve representar o valor mínimo que você terá que "pagar" ou "ganhará" atravessando o subgráfico a partir do nó para o qual a borda aponta. Suponha que estejamos no nível i + 1 e subamos para o nível i. Isto é o que eu faria para atribuir um peso para uma borda apontando para um nó do nível i:

1. edge_weight = apontar_nome_peso.
2. Encontre a borda começando no "nó apontador" com o peso máximo. Deixe esse peso ser next_edge_weight.
3. edge_weight + = next_edge_weight

Em seguida, crie a ordem da seguinte maneira:

1. Seja S a fronteira da pesquisa, ou seja, o conjunto de nós para selecionar a seguir.
2. Selecione o nó para que (node_weight + maximum_edge_weight) seja maximizado.
3. Remova o nó do gráfico e S. Adicione os "filhos" do nó a S.
4. Se o gráfico não estiver vazio, vá para a etapa 1.
5. Pare.

A idéia é atravessar os subgráficos que darão o maior ganho possível primeiro, para poder suportar o custo dos subgráficos de peso negativo posteriormente.