Tengo un bosque, es decir, nodos con bordes dirigidos y sin ciclos (dirigidos o no dirigidos). Defino la altura de un vértice como 0 si no tiene bordes entrantes, o el número máximo de bordes para atravesar en reversa para alcanzar un vértice de altura 0.
También sé que el grado promedio de un nodo es una constante pequeña, digamos 2 más o menos. Para encontrar la altura de todos los vértices, puedo pensar en dos algoritmos:
Algoritmo Caminante
- Pase y marque para vértices sin bordes entrantes.
- Para cada vértice con , siga los bordes salientes, actualizando la altura de cada vértice encontrado si su altura anterior es menor.
Algoritmo de frontera
- Pase y marque para vértices sin bordes entrantes, y márquelos como la frontera.
- Para cada vértice fronterizo, vea si su padre tiene hijos en o debajo de la frontera. Si lo tiene, marque al padre como teniendo más la altura más grande entre sus hijos. Marque al padre como estando en la frontera.
- Repita 2 hasta que no haya nada más allá de la frontera.
Mis preguntas:
- ¿Hay un nombre para este problema y una solución más rápida y conocida?
- Tiendo a pensar que simplemente caminar desde todos los vértices es la solución más rápida. Estoy en lo cierto?
fuente
No sé si este problema tiene un nombre oficial o no. Tu título lo resume bastante bien. Subir desde los nodos de altura 0 será rápido, siempre que tenga cuidado de evitar el trabajo duplicado. Suponga que tiene un nodo con muchos hijos y una ruta larga sobre este nodo a la raíz. Supongamos también que las alturas de cada uno de los niños son diferentes. Cada niño puede actualizar la altura del nodo en cuestión. Está bien. Pero también debe evitar actualizar la ruta larga por encima de ese nodo hasta que todos sus hijos hayan informado sus alturas.
El algoritmo resultante se ejecutará en tiempo lineal, y el pseudocódigo se vería así:
fuente
Un problema tan similar que podría ser de interés es "Prefijo paralelo en árboles direccionados enraizados". El algoritmo encuentra el número de aristas a la raíz de cada nodo. Entonces las raíces terminan con un valor 0, mientras que, por ejemplo, el nodo inferior derecho terminaría con un valor de dos.
Tenga en cuenta que el siguiente algoritmo resuelve el problema más general para los bordes ponderados, pero puede inicializar W (i) en 1 para todo i. Y el sucesor de cada nodo i viene dado por P (i) = j.
La imagen a continuación ilustra la "reducción a la mitad" de las longitudes de ruta y hace que el tiempo de ejecución logarítmico sea fácil de entender. Sin embargo, no muestra las alturas de nodo calculadas.
(de "Introducción a los algoritmos paralelos" de Joseph Jaja).
Usando múltiples procesadores, es solucionable en tiempo O (lg n), pero usa operaciones O (n lg n). Hay un truco para llevarlo al trabajo lineal, pero está ligeramente involucrado.
fuente
S(i)
representa