¿Cómo calcular la ruta crítica de un gráfico acíclico direccional?

Question

¿Cuál es la mejor forma (con respecto al rendimiento) de calcular la ruta crítica de un gráfico acíclico direccional cuando los nodos del gráfico tienen peso?

Por ejemplo, si tengo la siguiente estructura:

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

La ruta crítica debe ser A->B->F (peso total:10)

Answer 1

No tengo ni idea de "rutas críticas", pero supongo que te refieres este.

Encontrar la ruta más larga en un gráfico acíclico con pesos solo es posible atravesando todo el árbol y luego comparando las longitudes, ya que nunca se sabe realmente cómo se pondera el resto del árbol.Puede encontrar más información sobre el recorrido de árboles en Wikipedia.Le sugiero que opte por el recorrido de pedido anticipado, ya que es fácil y sencillo de implementar.

Si va a realizar consultas con frecuencia, es posible que también desee aumentar los bordes entre los nodos con información sobre el peso de sus subárboles en el momento de la inserción.Esto es relativamente barato, mientras que el recorrido repetido puede resultar extremadamente caro.

Pero no hay nada que realmente te salve de un recorrido completo si no lo haces.El orden realmente no importa, siempre y cuando hagas un el recorrido y nunca recorrer dos veces el mismo camino.

Answer 2

Resolvería esto con programación dinámica.Para encontrar el costo máximo de S a T:

• Ordene topológicamente los nodos del gráfico como S = x_0, x_1, ..., x_n = T.(Ignore cualquier nodo que pueda llegar a S o ser alcanzado desde T).
• El costo máximo de S a S es el peso de S.
• Suponiendo que ha calculado el costo máximo de S a x_i para todo i < k, el costo máximo de S a x_k es el costo de x_k más el costo máximo para cualquier nodo con una ventaja hacia x_k.

Answer 3

Hay un artículo que pretende tener un algoritmo para esto:"Camino crítico en una red de actividades con limitaciones de tiempo".Lamentablemente, no pude encontrar un enlace a una copia gratuita.Aparte de eso, sólo puedo apoyar la idea de modificar http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm o http://en.wikipedia.org/wiki/A*

ACTUALIZAR:Pido disculpas por el mal formato: el motor de rebajas del lado del servidor aparentemente no funciona.

Answer 4

Mi primera respuesta, así que disculpe cualquier cosa no estándar debido a la cultura de stackoverflow.

Creo que la solución es sencilla.Simplemente niegue los pesos y ejecute la ruta más corta clásica para DAG (modificada para los pesos de los vértices, por supuesto).Debería funcionar bastante rápido.(La complejidad temporal de O(V+E) tal vez)

Creo que debería funcionar ya que cuando niegas los pesos, el más grande se convertirá en el más pequeño, el segundo más grande será el segundo más pequeño y así sucesivamente como si a > b entonces -a < -b.Entonces ejecutar DAG debería ser suficiente, ya que encontrará la solución para la ruta más pequeña del negado y, por lo tanto, encontrará la ruta más larga para el original.

Answer 5

Pruebe el método A*.

A* Algoritmo de búsqueda

Al final, para ocuparnos de las hojas, basta con hacer que todas conduzcan hasta un punto final, que marcaremos como objetivo.