Localizando a altura de todos os nós em uma floresta

8

Eu tenho uma floresta, ou seja, nós com bordas direcionadas e sem ciclos (direcionados ou não direcionados). Eu defino a altura de um vérticev como 0 se não tiver arestas recebidas ou o número máximo de arestas a serem movidas em ré para alcançar um vértice de altura 0. insira a descrição da imagem aqui

Eu também sei que o grau médio de um nó é uma pequena constante, digamos 2 ou mais. Para encontrar a altura de todos os vértices, posso pensar em dois algoritmos:

Algoritmo de Caminhada

  1. Percorra e marque h=0 0 para vértices sem arestas de entrada.
  2. Para cada vértice com h=0 0, siga as arestas de saída, atualizando a altura de cada vértice encontrado, se a altura anterior for menor.

Algoritmo de Fronteira

  1. Percorra e marque h=0 0 para vértices sem arestas de entrada e marque-os como a fronteira.
  2. Para cada vértice de fronteira, veja se o pai tem filhos na fronteira ou abaixo dela. Se houver, marque o pai como tendo 1mais a maior altura entre seus filhos. Marque os pais como estando na fronteira.
  3. Repita 2 até que não haja nada além da fronteira.

Minhas perguntas:

  1. Existe um nome para esse problema e uma solução mais rápida conhecida?
  2. Eu costumo pensar em simplesmente sair de todas as h=0 0vértices é a solução mais rápida. Estou certo?
alta largura de banda
fonte

Respostas:

7

Antes de tudo, depende um pouco de como você pode acessar seus dados para dizer quais algoritmos funcionam melhor.

Enfim, eu sugeriria determinar as alturas de maneira descendente, em vez de ascendente. Pessoalmente, acho que uma abordagem de cima para baixo é conceitualmente melhor e mais fácil de analisar. Para qualquer vérticev na floresta é verdade que

altura(v)={(maxvocê filho de valtura(você))+1E se você não é uma folha0 0de outra forma.

Assim, você pode procurar por todas as raízes e determinar as alturas dividindo uma conquista. Você tocará todos os vértices no máximo duas vezes (procurando as raízes + percorrendo). Na abordagem que você sugeriu, talvez seja necessário tocar em alguns vértices várias vezes.

Aliás, como você tem uma floresta, possui menos arestas do que vértices; portanto, sabe que possui um grau médio menor que dois (e, portanto, pode testar raízes em tempo linear).

A.Schulz
fonte
+1; soluções recursivas geralmente são mais fáceis de analisar. Também depende se você já possui ponteiros filhos ou não, e se deseja uma solução baseada em loop ou recursiva.
12123 Joe
Eu gosto da análise! Alguém pode ajudar os novatos apontando como converter isso para a forma iterativa também?
highBandWidth
4

Não sei se esse problema tem um nome oficial ou não. Seu título resume bem o suficiente. Subir dos nós de altura 0 será rápido, desde que você tome cuidado para evitar trabalhos duplicados. Suponha que você tenha um nó com muitos filhos e um caminho longo acima desse nó para a raiz. Suponha também que as alturas de cada uma das crianças sejam diferentes. Cada filho pode atualizar a altura do nó em questão. Isso está ok. Mas você deve evitar também atualizar o caminho longo acima desse nó até que todos os seus filhos relatem suas alturas.

O algoritmo resultante será executado em tempo linear, e o pseudo-código seria algo parecido com isto:

initialize a queue Q
initialize all nodes to have a property: maxChildHeight = 0
initialize all nodes of in-degree 0 to have height = 0
Add all nodes of in-degree 0 to Q
while Q is non-empty:
  pop a node v from the front of Q
  subtract 1 from the indegree of the parent of v
  set parent.maxChildHeight = max(height(v), parent.maxChildHeight)
  if the indegree of the parent is 0:
      parent.height =  maxChildHeight + 1
      add the parent to Q
Joe
fonte
3

Um problema tão semelhante que pode ser interessante é "Prefixo paralelo em árvores direcionadas enraizadas". O algoritmo encontra o número de arestas na raiz de cada nó. Portanto, as raízes terminam com o valor 0, enquanto, por exemplo, o nó inferior direito terminaria com o valor dois.

Observe que o algoritmo abaixo resolve o problema mais geral para arestas ponderadas, mas você pode apenas inicializar W (i) para 1 para todos os i. E o sucessor de cada nó i é dado por P (i) = j.

for 1 ≤ i ≤ n do in parallel
    S(i) = P(i)
    while S(i) != S(S(i)) do
        W(i) = W(i) + W(S(i))
        S(i) = S(S(i))

A imagem abaixo ilustra a "metade" dos comprimentos do caminho e facilita o tempo de execução logarítmico. Porém, ele não mostra as alturas dos nós calculadas.

insira a descrição da imagem aqui

(de "Introdução aos algoritmos paralelos", de Joseph Jaja).

Usando vários processadores, é solucionável no tempo O (lg n), mas usa operações O (n lg n). Há um truque para reduzi-lo ao trabalho linear, mas está um pouco envolvido.

The Unfun Cat
fonte
Obrigado! o que S(i)representa?
#BackWidth #
O nó sucessor. Portanto, na iteração, uma das árvores da direita, S (9) = 10, S (10) = 11, S (11) = 12, S (12) = 13 e W (9) = 1, W (10) = 1 , W (11) = 1, W (12) = 1. Na iteração dois, S (9) = 11, S (10) = 12, S (11) = 13, S (12) = 13 e W (9) = 2, W (10) = 2, W (11) = 2, W (12) = 1. Na iteração três, S (9) = 13, S (10) = 13, S (11) = 13, S (12) = 13 e W (9) = 2 + 2, W (10) = 2 + 1, W (11) = 2, W (12) = 1.
The Unfun Cat
Você deve imaginar que todos os S (i) e W (i) são atualizados ao mesmo tempo em que tenta resolver os detalhes. Isso pode ser obscuro, mas eu queria publicá-lo porque é um problema paralelo clássico e muito próximo ao que você descreveu.
The Unfun Cat