ESTRUCTURAS DE DATOS

UNION-FIND

O también llamado Disjoint-Set(Conjuntos Disjuntos), esta estructura de datos nos ayuda a particionar de alguna forma que nos convenga una serie de conjuntos que un principio todos están disjuntos(separados) vamos a verlo gráficamente.

Podemos ver que los 4 nodos están separados esa sería la definición de conjuntos disjuntos en teoría de grafos.

Pero, ¿para que nos puede ayudar esta estructura de datos?

Hace un tiempo en el club de algoritmia se nos dio a la tarea de resolver un problema con esta estructura y consistía en lo siguiente...

Existía una red social en la cual podías hacer amistad con alguna persona y esa persona podía hacer amistad con otra y al mismo tiempo tu podías hacer amistad con otra, básicamente todos podían ser amigos de todos. Entonces nos daban un número n que era el número de amistades que podían surgir, y para cada n teníamos que dar el nombre de las dos personas que se volvían amigos por ejemplo:

Definiremos a
q0 = Beto
q1 = Elisa
q2 = Esteban

q3 = Pedro
q4 = Estefany

q5 = Ivan

en un inicio todos en el conjunto todos son padre de sí mismos.

Con n = 3

Beto Elisa
Esteban Pedro
Ivan Estefany

después de formar las redes sociales:

Y lo que teníamos que decir era de que tamaño hasta ese momento con esas personas, que se volvieron amigos, era la red social. Para el caso anterior las respuestas serían:

Personas          Respuesta

Beto Elisa              2
Esteban Pedro        2
Ivan Estefany         2

¿Pero porque dos? Bien pues en un principio la unión de dos personas forma una red de tamaño 2 y ninguna de las uniones de personas en cada consulta se volvió amigo de otra red social, para entenderlo mejor pondré otro ejemplo:

Personas          Respuesta

Beto Elisa              2
Esteban Pedro        2
Elisa Estefany         3

En este caso Beto y Elisa formaron una red de 2 personas pero después Elisa se volvió amiga de Estefany entonces la red que era de dos personas agregó a su conjunto otra persona entonces se volvió una red total de 3 personas.

Y así sucesivamente se iban agregando conjuntos a otros conjuntos para más información sobre el problema pueden ver acá
Pero como resolverlo, es aquí donde entra la magia de esta estructura de datos Disjoint Set y el algoritmo de Union Find.

Un algoritmo Unión-Buscar es un algoritmo que realiza dos importantes operaciones en esta estructura de datos:

• Buscar: Determina a cual subconjunto pertenece un elemento. Esta operación puede usarse para verificar si dos elementos están en el mismo conjunto
• Unión: Une dos subconjuntos en uno solo.

Para ello entonces tendremos dos funciones importantes la de calcular raíz del conjunto que analicemos y la de unión y en c estarán implementadas de la siguiente manera:

Primero tendremos un arreglo llamado padre donde el índice i es el conjunto y el contenido en el indice i es su raíz o su padre.

padre[]    1   2   3   4   5   //Nótese que al inicio el padre de cada conjunto es si mismo

raiz         1   2   3   4   5   // porque cada uno forma un conjunto por si solo

Para la raíz

int raiz(int a){//Devolvera un entero para saber cual es la raiz y recibe el numero del que se quiere calcular su raiz

   if(padre[a] != a)//Si el padre de ese numero a su contenido quiere decir que esa no es su raiz

      return padre[a] = raiz(padre[a]); //Y en esa posicion se guarda el contenido del padre y se calcula recursivamente hasta que el padre de 'a' sea igual a 'a'

   return a;//y se regresa a 'a'

}

Para la unión:

void une(int a, int b){//Se reciben los dos números a unir

   raizA = raiz(a);//Se calcula la raiz de a y se guarda en raizA

   raizB = raiz(b);//Se calcula la raiz de b y se guarda en raizB

   padre[raizA] = raizB;//La raiz de b o raizB se convierte en el nuevo padre de a o raizA }

Esta función es muy interesante porque recibe los dos números que se quieren unir y se calculan sus raices y se guardan en dos variables raizA y raizB una para cada número y en el arreglo de padres en la posición de la raiz de a se guarda la raiz de b entonces el padre de b pasa a ser el padre de a y así se une dicho conjunto. Su complejidad es O(nlogn).

Por esta sesión es todo y sugiero si quieres entender mejor como funciona esta sensacional estructura de datos en este algoritmo agarres lápiz y papel y hagas tus pruebas de escritorio que en verdad sirven y notes como funciona. ¡Hasta la próxima!
 

Ya saben si tienen dudas escríbanme a adrian.ipod25@gmail.com. Visitenme en Twitter @ferprogramming. Saludos.

MEMOIZACIÓN

En uno de mis anteriores post había mencionado el término "memoización" específicamente en el del cálculo del factorial de un número implementado de manera recursiva. Bien ahora veamos en que consiste...
 Esta técnica de optimización suele emplearse sobre todo en algoritmos implementados de manera recursiva, básicamente lo que hace es reducir considerablemente el número de llamadas dentro de una función recursiva, esto evita cálculos innecesarios los cuales ya se habían hecho antes dentro de la función.
Para hacer más gráfica mi explicación tomaré el cálculo de los números de la sucesión Fibonacci.

Cuando tenemos una sucesión de Fibonacci decimos que nuestros casos base son cuando dada una función  fibo(1) es igual a 1, y fibo(0) = 0, visto de mejor forma:

si fibo(0) = 0

ó
si fibo(1) = 1

lo demás es sencillo pues solo calculamos las respuestas para un número (n-1) + (n-2), según la sucesión.
Ya para conocer mejor aquí implementada la sucesión Fibonacci en C de manera recursiva:

int fibo(int n){

   if(n<=0)

      return 0;

   if(n==1)
      return 1;

return fibo(n-1) + fibo(n-2);
}
Aquí tenemos el código de una sucesión Fibonacci pero, si nos ponemos a analizar un poco el problema podemos observar que se harán cálculos de números que posiblemente en otra llamada ya se hayan hecho, por ejemplo para el fibonacci de n = 5, el la primera llamada sería...

1) fibo(4) + fibo(3); //Calculando el fibonacci de 3 y 4

2) Para la llamada con n=4 fibo(3) + fibo(2)  y para n=3 fibo(2) + fibo(1); //Note que se repite el cálculo para la del 3 con la anterior llamada y en esta misma llamada la del 2 se calcula dos veces, así en la próxima recursión tendremos otras ocho llamadas en total.

Esto no suele ser óptimo ya que si lo hacemos para un n con valores muy grandes tendría que hacer el cálculo de cada llamada calculando para su n-1 y n-2 y sobre esas mismas aplicar el mismo procedimiento. 

Para optimizar esto la técnica consiste en memorizar cada respuesta que ya se haya calculado en un arreglo y verificar que no se haya calculado antes. Veamos...

1° Llenamos un arreglo un número "infinito" que jamás llegaremos a obtener en la sucesión de fibonacci.

2° Preguntamos ya en nuestra función recursiva si el número que calculamos es diferente a nuestro número "infinto"(antes puesto en el arreglo), esto nos quiere decir que sí es diferente a ese infinito quiere decir que ya ocupa otro número antes calculado su lugar entonces basta con regresar ese número porque ya ha sido calculado

3° Por último regresamos el calculo de los casos base dentro de nuestro arreglo.

NOTA: dentro de nuestra función el índice del arreglo será nuestra misma n.
El código mejorado queda así...
En el main...
fill(memo,memo+n,INF) // Paso 1. INF es nuestro "inifnito" y la función fill() esta en la librería algorithm de C++ y llena un arreglo de número, para más info, consulte el C++ Reference en internet. ^_^

int fibo(int n){

   if(memo[n] != INF)
      return memo[n];  // Paso 2

   if(n<=0)

      return memo[n] = 0;//Paso 3

   if(n==1)
      return memo[n] = 1; // Paso 3

return memo[n] = fibo(n-1) + fibo(n-2); //Paso 3
}
Así un ejemplo de prueba de escritorio...
1) Nuestro arreglo esta de la siguiente manera:
pos    0       1      2     3      4      5

val   INF   INF   INF   INF   INF   INF

2) Aquí posiblemente ya tenga el calculo para el níumero 1 y 0
pos  0   1     2      3     4      5

val   0   1    INF   INF   INF   INF

Y así se irá llenando nuestro arreglo hasta que llegue a un caso base y de la respuesta pero sin volver a recalcular un número puesto que el paso 2 pregunta que si nuestro número n es diferente a nuestro "infinito" lo cual si es cierto solo devuelve el mismo.
La memoización es una técnica que nos ayuda mucho sobre todo en la Programación Dinámica(dp), porque si hacemos Top-Bottom o sea recursiva una solución podemos memorizar y evitar el recálculo de números...
Eso fue todo por esta sesión y si hay dudas por favor escríbeme a adrian.ipod25@gmail.com, hasta pronto!