Programação Dinâmica em Árvores

A ideia para resolver qualquer problema com Programação Dinâmica (PD) consiste de, em sua raiz, dividir o problema em problemas menores. E podemos dividir esses problemas menores e problemas ainda menores e assim seguimos recursivamente. Após resolvermos os menores problemas, os juntamos para resolver problemas progressivamente maiores.

Seguimos com esse procedimento para resolvermos nosso problema inicial. Mas como poderíamos aplicar PD numa árvore?

Para ilustramos bem a situação, vamos resolver o seguinte problema (é necessário conhecimento prévio de grafos):

Um reino possui \(N\) cidades conectadas entre si por \(N-1\) rotas bidirecionais, onde se é possível viajar de qualquer cidade a qualquer outra. Preocupada com a segurança das rotas, a rainha decidiu instalar postos de seguranças em algumas cidades. O objetivo é que, para toda rota, exista um posto de segurança em ao menos uma das cidades conectadas por essa rota. Também preocupada com as finanças do reino, a rainha lhe contratou para selecionar achar o número mínimo de cidades em que é preciso construir um posto de segurança de forma a satisfazer as condições necessárias.

Claramente, podemos construir um grafo onde as cidades são os vértices e as rotas são as arestas. Como esse grafo é conexo, possuindo \(N\) vértices e \(N-1\) arestas, concluímos que ele é uma árvore. Então, temos que escolher um conjunto mínimo de vértices de forma que todas as arestas conecte pelo menos um desses vértices.

Esse problema é conhecido, em inglês, como Vertex Cover. No caso, resolveremos o Vertex Cover em uma Árvore.

Por simplicidade, vamos numerar os vértices de \(1\) a \(N\) e definirmos o vértice \(1\) como a raiz da árvore. Também, vamos considerar o vértice como “colorido” se, e somente se, ele foi incluído no conjunto da resposta.

Agora, para resolvermos o problema com PD, precisamos pensar em como dividir o problema em problemas menores.

Uma boa maneira de fazer isso seria, para cada vértice, resolver o problema considerando apenas a sub-árvore gerada por ele (lembrando que o vértice \(1\) é a raiz da árvore). Assim, resolver o problema para o vértice \(1\) equivale a resolver o problema para o grafo inteiro.

Também, para resolvermos o problema em um vértice, podemos primeiro resolver o problema para seus filhos (que serão os problemas menores). Dividimos o problema consecutivamente em problemas menores até chegarmos às folhas, que são o caso trivial (ignorando a possibilidade do vértice \(1\) ser uma folha).

Já o estado da nossa PD consistirá de, nesse caso, duas informações: o vértice que estamos agora e o fato de seu pai ter sido colorido ou não. Digamos que o vértice que estamos calculando agora é o vértice \(X\). Se o pai de \(X\) foi colorido, podemos escolher se queremos colorir \(X\) ou não e resolver o problema para seus filhos com essa nova informação. Se o pai de \(X\) não foi colorido, temos que colorir \(X\), e então resolvemos o problema para seus filhos. Assim, nossa PD fica:

Estado = \([X][PaiColorido]\)

  • Caso escolhamos colorir \(X\), \(caso1 = 1 + \sum PD[V][True]\), para todos \(V\) que são filhos de \(X\). Somamos \(1\) porque colorimos \(X\).

  • Caso escolhamos não colorir \(X\), \(caso2 = \sum PD[V][False]\), para todos \(V\) que são filhos de \(X\)

  • Se \(PaiColorido = True \Rightarrow PD[X][PaiColorido] = min(caso1, caso2)\).

  • Se \(PaiColorido = False \Rightarrow PD[X][PaiColorido] = caso1\). Nesse caso, somos obrigados a colorir \(X\) porque seu pai não foi colorido. Se não o coloríssemos, a aresta que liga \(X\) a seu pai estaria conectando dois vértices não-coloridos, o que não podemos permitir.

O código para isso fica bem simples:

            int VertexCover(X, pai_colorido){
                if(PD[X][pai_colorido] != -1)
                    return PD[X][pai_colorido]; // se já calculamos esse caso, retornamos o valor para evitar recálculo
                                                // não se esqueça de, não função main, inicializar todos os valores de PD como -1.
                int caso1 = 1, caso2 = 0;
                for(int i = 0;i < (int)vizinhos[X].size();i++){ // percorremos todos os vizinhos de X

                    int V = vizinhos[X][i];

                    if(V == pai[X]) continue; // checamos se V é o pai de X

                    // agora, sabemos que V é um filho de X
                    pai[V] = X; // definimos o pai de V como sendo X
                    caso1 += VertexCover(V, true);  // caso escolhamos colorir X
                    caso2 += VertexCover(V, false); // caso escolhamos não-colorir X
                }
                if(pai_colorido == true) PD[X][pai_colorido] = min(caso1, caso2);// caso o pai de X esteja colorido, escolhemos o melhor caso
                if(pai_colorido == false) PD[X][pai_colorido] = caso1;           // caso o pai de X não seja colorido, escolhemos o caso1
                return PD[X][pai_colorido]; // retornamos o valor da resposta
            }

A resposta final seria, então, \(VertexCover(1, true)\), porque podemos assumir que o “pai” do vértice \(1\) é colorido, já que ele é a raiz da árvore.

Essa ideia recursiva é válida para resolver diversos problemas de PD em árvores – com cada um deles tendo uma ligeira variação quando se trata de “juntar as respostas” dos filhos de um vértice.

Back to top