Diferencias

Muestra las diferencias entre dos versiones de la página.

--- algoritmos-oia:grafos:arboles:programacion-dinamica-en-arboles [2017/12/08 21:38]
sebach creado
+++ algoritmos-oia:grafos:arboles:programacion-dinamica-en-arboles [2017/12/26 19:13] (actual)
sebach ↷ Links adapted because of a move operation
@@ Línea 1: / Línea 1: @@
 ====Prerrequisitos====
-[[algoritmos-oia:arboles|Árboles]]
+[[algoritmos-oia:grafos:arboles|Árboles]]
+Noción de [[algoritmos-oia:programacion-dinamica|programación dinámica]]
 ===== Programación Dinámica en árboles =====
@@ Línea 11: / Línea 12: @@
 Para resolver esto vamos utilizar programación dinámica.
-Lo podemos hacer de dos maneras escencialmente:
+**De arriba para abajo**
-**De abajo para arriba:**
+Vamos a empezar en la raíz y usar la misma fórmula que arriba, con la excepción de que ahora no tenemos todavía la información de abajo. Entonces usaremos recursión. Para saber el tamaño del subárbol de la raíz (que en realidad es la cantidad de nodos pero igualmente empezamos por acá para recorrer todo el árbol), llamamos a la función que calcula el tamaño de un subárbol para cada uno de sus hijos. Y una vez que ya tenemos esos datos, los sumamos y luego sumamos $1$.
-Empezar en las hojas, marcando como que sus subárboles tienen tamaño $0$, y a partir de ahí ir a sus padres, y sabemos que sus subárboles tienen $cantidad_de_hijos_del_nodo + 1$, en este caso.
-Y en general, si vamos subiendo, sabemos que el tamaño de un subárbol es la suma de los tamaños de los subárboles de sus hijos, más $1$.
-Si tenemos un nodo $raiz$, un $vector< vector<int> > grafo$ y un $vector<int> tamanio$ que en la posición $i$ vaya a quedar el tamanio del subárbol del nodo $i$, el código quedaría:
+El código quedaría:
 <code cpp>
-vector<int> tamanio(V, -1);
+map<int,int> tamanioDeNodo;
-queue<int> nodosQueYaPasePorSusHijos;
+int tamanio(int nodo, int padre){
-forn(i, V){
+    int miTamanio=1;
-    if(esHoja(i)){
+    for(int i=0; i<grafo[nodo].size(); i++){ // Los casos base de esta recursión serían las hojas, ya que no tienen nodos adyacentes distintos del padre y el if no pasa y entonces no se llama a la función recursiva
-        tamanio[i]=1;
+        if(grafo[nodo][i]!=padre){
-        nodosQueYaPasePorSusHijos.push(i);
+            miTamanio+=tamanio(grafo[nodo][i], nodo);
-    }
-}
-while(!nodosQueYaPasePorSusHijos.empty()){
-    int nodo = nodosQueYaPasePorSusHijos.front();
-    nodosQueYaPasePorSusHijos.pop();
-    int miTamanio=1; // Por el nodo "raiz del subarbol"
-    int padre=-1;
-    forn(i, grafo[nodo].size()){
-        if(tamanio[grafo[nodo][i]]!=-1){ // Para no mirar el padre que todavia no sabemos el tamanio
-            miTamanio+=tamanio[grafo[nodo][i]];
-        }else{
-            padre=grafo[nodo][i]
         }
     }
-    tamanio[nodo]=miTamanio;
+    tamanioDeNodo[nodo]=miTamanio;
-    if(padre!=-1){
+    return miTamanio;
-        nodosQueYaPasePorSusHijos.push(padre);
-    }
 }
+tamanio(raiz, -1);
 </code>
-Algo que hay que tener en cuenta es cómo implementar la función "esHoja" utilizada acá. Una manera de encontrar las hojas, es empezar en la raíz, ir recorriendo un bfs/dfs, y cuando desde un nodo no hay vecinos a los que ir, es porque su vecino es su padre y no tiene hijos, entonces es hoja.
-**De arriba para abajo**
+===== Problema de ejemplo =====
-Vamos a empezar en la raíz y usar la misma fórmula que arriba, con la excepción de que ahora no tenemos todavía la información de abajo. Entonces usaremos recursión. Para saber el tamaño del subárbol de la raíz (que en realidad es la cantidad de nodos pero igualmente empezamos por acá para recorrer todo el árbol), llamamos a la función que calcula el tamaño de un subárbol para cada uno de sus hijos. Y una vez que ya tenemos esos datos, los sumamos y luego sumamos $1$.
-El código quedaría:
+==== Enunciado ====
+Dado un árbol de $N$ nodos, el nodo $i$ tiene $M_i$ monedas. Tenés que seleccionar un conjunto de nodos, de manera que no haya dos que sean adyacentes de ese conjunto, tal que la suma de las monedas de los nodos seleccionados sea la mayor posible.
+==== Solución ====
+Pensemos qué pasa si vamos recorriendo el árbol desde la raíz hacia abajo (seteando primero alguna raíz), y obteniendo información sobre subárboles. Lo que podemos pensar es que si estamos mirando un nodo, podemos seleccionarlo o no. Entonces vamos a mirar las dos opciones. Obviamente no vamos a pensar qué pasa en cada subconjunto posible del conjunto de nodos, eso tomaría $O(2^N)$ operaciones. Para eso vamos a usar la programación dinámica, que es más o menos "mirar todas las posibilidades" pero de una "manera inteligente".
+Entonces, si estamos en el nodo $u$, y sólo nos importa el subárbol del nodo $u$ (para eso vamos a ir de arriba hacia abajo), podemos o seleccionarlo o no.
+Si lo seleccionamos, luego no podremos seleccionar a ninguno de los hijos. Entonces las monedas que podemos obtener son las monedas del nodo $u$, $M_u$, más la mayor cantidad de monedas de los hijos de los hijos de $u$, ya que, como a sus hijos no los vamos a poder seleccionar, para los subárboles de los hijos de los hijos no tendremos ninguna restricción que nos impida seleccionar lo que queramos.
+Y si no seleccionamos el nodo $u$, vamos a poder hacer lo que queramos con los subárboles de los hijos de $u$, ya que no tendrán ninguna restricción. Además, es importante notar que como estos subárboles son disjuntos, seleccionemos lo que seleccionemos del subárbol de uno de los hijos no afecta lo que podamos seleccionar del subárbol de otro de los hijos.
+Entonces ya tenemos la manera de obtener lo mejor para un subárbol: O es la cantidad de monedas de la raíz del subárboles más la suma de las mejores cantidades para los subárboles de los hijos de los hijos de esta raíz; o es la suma de las mejor cantidades de los subárboles de sus hijos.
+Vamos a hacerlo, como se ve, recursivamente. Hasta que lleguemos a una hoja, donde la mejor cantidad para el subárbol de la raíz es simplemente la cantidad de monedas que hay en esa hoja (caso base).
+Para esto, vamos a tener una función recursiva "recorroSubarbolYGuardo", que dado un nodo y su padre, obtenga el mejor valor del subárbol (la solución parcial en programación dinámica), usando y sin usar el nodo. Cómo? Llamando a la función para los subárboles de los hijos y usando esa información como vimos antes.
 <code cpp>
-map<int,int> tamanioDeNodo;
+// Tenemos el grafo en "vector< vector<int> > grafo" y un vector<int> monedas con Mi en la posición i
+const int MAXN=1e5;
-int tamanio(int nodo, int padre){
+vector<int> mejorSinUsar(MAXN), mejorUsando(MAXN);
-    int miTamanio=1;
-    for(int i=0; i<grafo[nodo].size(); i++){ // Los casos base de esta recursión serían las hojas, ya que no tienen nodos adyacentes distintos del padre y el if no pasa y entonces no se llama a la función recursiva
+void recorroSubarbolYGuardo(int nodo, int padre){
-        if(grafo[nodo][i]!=padre){
+    int cantidadUsandoNodo = monedas[nodo];
-            miTamanio+=tamanio(grafo[nodo][i], nodo);
+    int cantidadSinUsar=0;
+    for(int i=0; i<grafo[nodo].size(); i++){
+        int hijo=grafo[nodo][i];
+        if(hijo!=padre){
+            recorroSubarbolYGuardo(hijo, nodo);
+            cantidadUsandoNodo+=mejorSinUsar[hijo];
+            cantidadSinUsar+=max(mejorUsando[hijo], mejorSinUsar[hijo]); // Como no hay restricción, quizás nos conviene seleccionar al hijo pero quizás no, entonces nos quedamos con la mejor de ambas posibilidades
         }
     }
-    tamanioDeNodo[nodo]=miTamanio;
+    mejorSinUsar[nodo]=cantidadSinUsar;
-    return miTamanio;
+    mejorUsando[nodo]=cantidadUsandoNodo;
 }
-tamanio(raiz, -1);
+recorroSubarbolYGuardo(0, -1);
+cout<<max(mejorSinUsar[0], mejorUsando[0])<<endl;
 </code>
@@ Línea 80: / Línea 89: @@
 ===== Problemas para practicar =====
-FIXME problemas
+[[https://www.e-olymp.com/en/problems/973|Mismo que el de las monedas]]
+[[https://www.hackerrank.com/challenges/tree-pruning/problem|Maximizar peso]]
+[[http://acm.timus.ru/problem.aspx?space=1&num=1039|Parecido al de las monedas]] (ojo con los pesos negativos!)
+==== Links externos ====
+http://codeforces.com/blog/entry/20935

OIA-Wiki

Herramientas de usuario

Herramientas del sitio

Diferencias

Herramientas de la página