Ahora toca explorar un algoritmo que es popularmente usado para la compresión de datos, estamos hablado del algoritmo para compresión de huffman, dicho algoritmo ofrece una compresión eficiente para los datos y es sencillo de entender, la idea del algoritmo es que dadas cadenas de símbolos contemos sus apariciones donde cada símbolo debe ser exactamente igual para contar las apariciones, por ejemplo no es lo mismo una "e" en la cadena que una "é" o "E", en este caso se contarían como símbolos distintos, podemos ordenar en una tabla de menor a mayor los símbolos totales en nuestra cadena seguidos de sus frecuencias, una vez contadas todas las frecuencias y registradas en nuestra tabla procedemos entonces con la construcción de un árbol binario, existen diferentes maneras para la construcción, pero se desea que los caracteres con frecuencias similares queden en un mismo nivel del árbol, para esto usaremos la estrategia de fijarnos en nuestros dos símbolos que tengan el menor numero de frecuencias, estos 2 símbolos serán nuestros dos nodos hoja que conectaremos a un nodo padre que tendrá la suma de las frecuencias de sus hijos, por lo que habremos creado un sub-arbol cuya frecuencia es igual a la suma de las frecuencias de sus hijos, podemos si se desea ubicar cual seria la posición de nuestro sub-arbol creado en la tabla de frecuencias para así saber que nodos deberíamos conectar a continuación, dicha conexión se realiza siempre tomando dos nodos y uniéndolos a un nodo padre que tenga la suma de frecuencias de ambos nodos, la idea de la construcción es ir conectando los nodos según las frecuencias menores para que los símbolos con menos repeticiones queden en los niveles inferiores del árbol y los símbolos con mas repeticiones queden en los niveles superiores del árbol, una vez que terminemos de conectar nuestros nodos nos quedara un solo árbol binario que contendrá todos nuestros símbolos de la cadena original, ahora para finalizar etiquetamos a todas las aristas que sean ramas izquierdas en nuestro árbol con 1 y etiquetamos con 0 todas las aristas que sean ramas derechas en nuestro árbol final, una vez listo nuestro árbol binario etiquetado la codificación de huffman en bits para cada símbolo sera la trayectoria desde la raíz de nuestro árbol hasta el nodo que contenga el símbolo de manera que cada que pasamos por una rama izquierda se agregara un 1 y si pasamos por una rama derecha se agregara un 0, al final la cadena de bits que representa la codificación dependerá de cuales ramas (izquierda o derecha) y cuantas ramas recorrimos en la trayectoria hasta llegar a nuestro símbolo en el árbol. A continuación se anexa un video con un ejemplo sencillo de aplicación del algoritmo de huffman de la mano del canal de youtube Matematicas con Jmq Mattosky:
Ademas de algoritmos para compresión también existen algoritmos aplicados para graficas donde si se llevo un curso de estructuras de datos le serán familiares algoritmos para recorrer graficas como lo son DFS (depht first search/búsqueda por profundidad) o BFS (brief first search/ búsqueda por amplitud), ambos algoritmos probablemente fueron introducidos para recorrer un tipo de grafica que ya conocemos bien, es decir un árbol, adicionalmente ambos tienen la complejidad O(|V| + |E|) donde |V| representa la cantidad de vértices en la grafica y |E| representa la cantidad de aristas en la grafica. Si se siente perdido en el tema anexamos a continuación un video de la mano del canal de youtube FLAGlab Uniandes que explica ambos algoritmos a detalle:
Sabemos ademas que existen graficas en las que las aristas tienen peso (graficas o grafos ponderados), esto se hace generalmente con el propósito de modelar distintas rutas que tienen un coste al pasar por ellas para llegar de punto A a punto B, normalmente lo que esperaríamos en un problema de este estilo es encontrar el camino mas corto que podemos recorrer, por lo que usamos un algoritmo que quizás resulta familiar, dicho algoritmo es el algoritmo de dijkstra, en dicho algoritmo la idea es iniciar desde un nodo y visitar todos sus vecinos donde a cada vecino le pondremos una etiqueta que sera [coste, nodo], en el coste sumaremos el peso de las aristas recorridas y en el nodo pondremos el nodo del que se visita, una vez agotemos todos los vecinos nos fijamos en el vecino en cuya etiqueta el coste sea menor, ahora repetiremos el proceso para ese nodo visitando sus vecinos y sumando el coste de las aristas, si se ya se tiene una etiqueta para ese nodo simplemente se actualiza la etiqueta [coste, nodo] con el coste acumulado y el nodo de donde estemos trabajando, esto se repite hasta llegar a nuestro nodo destino y entonces solamente queda reconstruir nuestro camino observando de donde viene cada conexión en los nodos. Puede ser útil ademas para este tipo de problemas encontrar el árbol generador mínimo (Minimum Spanning Tree), por lo que existen 2 algoritmos que nos facilitan la obtención del mismo que utilizan el paradigma de programación glotona, estos algoritmos son los de Prim y Kruskal. el algoritmo de prim consiste en fijarnos en la arista de menor peso siempre, dada una grafica ponderada nos vamos a fijar en la arista que tenga menor peso, dicha arista junto con sus vértices se ira a nuestro conjunto de árbol generador, ahora, verificaremos las aristas de los vértices en nuestro conjunto árbol y tomaremos aquella arista que tenga el menor peso entre ellas junto con su conexión al vértice cuidando siempre que no nos genere un ciclo, este paso lo vamos a repetir hasta tener n-1 aristas en nuestro conjunto árbol generador donde n es la cantidad total de vértices en la grafica. el algoritmo de kruskal consiste en primero ordenar las aristas por peso del peso mas pequeño al mas grande y agregar en el conjunto de árbol generador dichas aristas en el orden que presentan cuidando también que no generen un ciclo. A continuación se dejan un par de videos ilustrativos donde se ejemplifican los algoritmos de manera detallada, adicionalmente un extracto que explica a profundidad los algoritmos de prim y kruskal:
Algoritmo de dijkstra de la mano del canal de youtube Juan maTIC:
Ejemplo de Algoritmos de Prim y Kruskal de la mano del canal de youtube SUPERA MATES:
Se anexa un extracto de la mano del libro online de Matemáticas Discretas para Ciencia de Datos:
Árboles de peso mínimo: algoritmos de Prim y Kruskal.
También a la hora de trabajar con graficas podemos encontrarnos con graficas dirigidas las cuales tienen la particularidad de que para cada par de nodos conectados solo podemos ir de uno a otro esto esta determinado por la dirección que toma la arista, esta determina hacia que nodo podemos movernos a partir del que ya estamos, las aplicaciones de algoritmos para estas graficas también son posibles pues es posible por ejemplo obtener el camino mas corto usando dijkstra igualmente, adicionalmente veremos un algoritmo que soluciona la ruta mas corta usando programación dinámica como manera alternativa
Ruta mas corta con programación dinámica de la mano del canal de youtube Alvaro Jesus Nina Laura :
Ademas estas graficas dirigidas suelen indicar también problemas de redes de flujo las cuales se modelan como una grafica dirigida donde tenemos un nodo de inicio (también llamado fuente) generalmente nombrado s y un nodo destino (también llamado sumidero) que generalmente nombramos t , cada arista tiene una capacidad por la cual puede pasar el flujo la cual se agota hasta que dicha arista no pueda permitir mas flujo digamos un indicador como [flujo/capacidad], generalmente se busca obtener el flujo máximo, es decir obtener si existen los caminos que no saturan la red desde nuestro punto inicial hasta nuestro punto final, un algoritmo bastante conocido para redes de flujos es el algoritmo ford fulkerson el cual se auxilia de caminos aumentantes que pueden incrementar el flujo total hasta que ya no sea posible incrementarlo mas, primeramente encontramos trayectorias que nos lleven al sumidero de tal manera que veamos que el flujo puede seguir aumentándose, es decir que no se a excedido la capacidad de la arista, posteriormente tendremos que determinar si podemos enviar flujo adicional a través de algún camino que tengamos, este flujo restante estará delimitado siempre por la capacidad restante en las aristas del camino y deberemos actualizar los valores del flujo y la capacidad de la arista conforme realicemos este procedimiento, repetimos el procedimiento de encontrar los caminos hasta que ya no halla ningún camino por el cual enviar flujo entonces la suma de flujos enviados sera el flujo máximo que podremos mandar, el algoritmo como tal tiene complejidad O(E * F), siendo E las aristas y F el flujo máximo, existe una mejora al algoritmo que utiliza BFS y logra una complejidad de O(V + E^2), siendo este el algoritmo de Edmonds-Karp. A continuación se anexa un video que contiene un ejemplo del funcionamiento del algoritmo y se dejan 2 extractos donde se explican a detalle ambos algoritmos:
ejemplo del Algoritmo de Ford Fulkerson de la mano del canal de youtube 24h Vending:
Adicionalmente se dejan 2 extractos del sitio web W3schools donde se explican a detalle los algoritmos de ford fulkerson y la mejora al algoritmo de Edmonds-Karp (ambas referencias se encuentran en ingles por lo que se recomienda traducir en caso de que no se logre comprender, una traducción importante para casos de graficas es que para referirse a las aristas se usa "edge" en ingles):
No hay comentarios:
Publicar un comentario