Estoy buscando un algoritmo o una idea para un algoritmo para el siguiente caso de uso:

Un gráfico dirigido consta de múltiples vértices. Algunos de estos vértices están anotados con un valor (como un número) y no tienen vértices principales (predecesores). Todos los demás vértices representan operaciones. Una operación solo se puede realizar si se conocen todos los valores anotados de los vértices principales (predecesores). El resultado o valor de la operación se almacena en el vértice.

Mi idea de solución:

  1. Almacene todos los vértices que tienen al menos un vértice padre (predecesor) en un conjunto
  2. Mientras el conjunto no está vacío:
    1. Obtenga el siguiente vértice del conjunto
    2. Verifique si se conoce el valor de todos los vértices primarios (predecesores)
    3. Si se conocen todos los valores:
      1. Eliminar el vértice del conjunto
      2. Realizar la operación
      3. Almacenar el resultado de la operación en el vértice
      4. Bucle (ir a 2.)
    4. Else: Loop (ir a 2.)

Mi problema: creo que esta idea de solución podría funcionar, pero no es eficiente (especialmente para estructuras de gráficos grandes).

¿Existen enfoques más eficientes para resolver este problema?

2
Marcello90 26 oct. 2017 a las 21:53

3 respuestas

La mejor respuesta

Hay algunas posibilidades que evitan volver a comprobar los vértices sin rumbo, por ejemplo:

  1. Inicialice una matriz de enteros que almacenen, para cada vértice, el número de padres.
  2. Inicialice un conjunto de vértices que tienen 0 padres (se puede hacer al mismo tiempo que el paso 1).
  3. Hasta que ese conjunto esté vacío:
    1. Toma un poco de vértice a de ese conjunto y procésalo.
    2. Por cada borde desde a a un vértice b, disminuya el recuento primario del vértice b. Si el recuento llega a 0, agregue b al conjunto de vértices que están listos para procesar.
2
harold 26 oct. 2017 a las 19:04

Lo que se quiere hacer se llama 'clasificación topológica': en el orden en que procesa los vértices, los predecesores de cada nodo deben aparecer antes de que lo haga: https://en.wikipedia.org/wiki/Topological_sorting

Hay varios algoritmos eficientes. Uno es bastante cercano al tuyo, pero solo pones un vértice en el conjunto cuando no tiene predecesores inacabados. (respuesta de harold)

1
Matt Timmermans 26 oct. 2017 a las 19:31

¿No es esencialmente un tipo de problema transversal de orden de nivel?

Dado que,

Una operación solo se puede realizar si se conocen todos los valores anotados de los vértices principales (predecesores).

Debes comenzar con los vértices que no tienen vértices principales. (Esta parte ya ha sido descubierta por usted).

Luego, en lugar de ponerlos en un conjunto, póngalos en una cola para que el primero en entrar, primero en salir le permita abordar cada vértice en el orden de nivel.

Si no se puede calcular el valor del vértice actual, vuelva a colocarlo en la cola; de lo contrario, coloque el vértice al que se puede acceder desde el vértice actual en la cola. Mantenga disponibles los valores de cálculo para los vértices que tienen el valor de vértices primarios requerido.

Casi puedo argumentar que con algunas optimizaciones, este sería el método más eficiente.

1
displayName 26 oct. 2017 a las 19:38