Como calcular o caminho crítico de um gráfico acíclico direcional?

Question

O que é o melhor (em relação ao desempenho) maneira de calcular o caminho crítico de um gráfico acíclico direcional quando os nós do grafo tem peso?

Por exemplo, se eu tiver a seguinte estrutura:

            Node A (weight 3)
               /            \
     Node B (weight 4)      Node D (weight 7)
     /               \
Node E (weight 2)   Node F (weight 3)

O caminho crítico deve ser A-> B> F (peso total: 10)

Answer 1

Eu não tenho nenhuma pista sobre "caminhos críticos", mas presumo que você quer dizer este .

Encontrar o caminho mais longo em um grafo acíclico com pesos só é possível percorrer toda a árvore e, em seguida, comparando os comprimentos, como você nunca realmente sabe como o resto da árvore é ponderado. Você pode encontrar mais sobre passagem de árvore em Wikipedia . Sugiro, você vai com percurso pré-ordem, como é fácil e simples de implementar.

Se você estiver indo para consulta, muitas vezes, você também pode querer aumentar as arestas entre os nós com informações sobre o peso de suas sub-árvores na inserção. Isso é relativamente barato, enquanto travessia repetido pode ser extremamente caro.

Mas não há nada de realmente salvá-lo de um percurso cheio se você não fazê-lo. A fim realmente não importa, contanto que você faça um travessia e nunca ir pelo mesmo caminho duas vezes.

Answer 2

Gostaria de resolver isso com programação dinâmica. Para encontrar o custo máximo de S para T:

• Topologicamente tipo os nós do gráfico como S = x_0, x_1, ..., x_n = T. (Ignorar todos os nós que podem atingir S ou ser alcançado a partir de t.)
• O custo máximo de S para S é o peso de S.
• Assumindo que você tenha calculado o custo máximo de S a x_i para todo i

Answer 3

Há um papel que pretende ter um algoritmo para isso: "caminho crítico em uma rede de atividades com limitações de tempo". Infelizmente, eu não poderia encontrar um link para uma cópia gratuita. Menos do que isso, só posso segundo a idéia de modificar http://en.wikipedia.org/ wiki / Dijkstra% 27s_algorithm ou http://en.wikipedia.org/wiki/A *

UPDATE:. Peço desculpas pela baixa qualidade formatação-o motor remarcação do lado do servidor é aparentemente quebrado

Answer 4

A minha primeira resposta por isso, desculpa por qualquer coisa fora do padrão pela cultura do stackoverflow.

Eu acho que a solução é simples. Apenas negar os pesos e executar o caminho mais curto para clássico DAG (modificado para pesos de vértices de curso). Deve funcionar bastante rápido. (Tempo complexidade de O (V + E) talvez)

Eu acho que deve funcionar como quando você vai negar os pesos, o maior deles vai se tornar menor, segunda maior será a segunda menor e assim por diante, como se a > b então -a < -b. Em seguida, executar o DAG deve ser suficiente uma vez que irá encontrar a solução para o menor caminho do um negada e, assim, encontrar caminho mais longo para o original

Answer 5

Experimente o A * método.

A * algoritmo de pesquisa

No final, para lidar com as folhas, apenas fazer todos eles levam a um ponto final, para definir como a meta.