La geometría computacional es una rama que extiende el diseño y análisis de algoritmos, esta se comprende del estudio sistemático de algoritmos y estructuras de datos que refieran a objetos geométricos, esta área reúne tanto problemas matemáticos como problemas de ciencias de la computación, tiene aplicación en distintos campos como lo pueden ser la robótica, los gráficos por computadora o sistemas de ubicación geográfica, para dar una breve introducción veremos un algoritmo perteneciente a un problema estático que proviene de esta rama siendo un algoritmo para encontrar el cierre convexo dada una nube de puntos.
Veamos entonces el algoritmo para encontrar el cierre convexo (convex haull), este se refiere al polígono convexo que tenga en su interior todos los puntos, al ser un polígono convexo esto indica que todos los ángulos interiores son menores o iguales a 180 grados, dicho algoritmo es conocido como el algoritmo de graham (scan de graham), partimos encontrando el punto que tiene la coordenada mas pequeña en el eje Y, lo llamaremos p, tenemos ahora un angulo polar entre p y el resto de puntos, ordenamos dichos puntos de acuerdo al angulo polar que forman con p, una vez ordenados lo que haremos sera inicializar una pila en la que meteremos los primeros 2 puntos de nuestro ordenamiento, nos fijamos en la orientación que toma el angulo del punto en la pila con respecto al tercer punto en el ordenamiento si la orientación es de acuerdo al sentido contrario a las manecillas del reloj entonces lo metemos a la pila, si la orientación respecto al siguiente punto ordenado no es de acuerdo al sentido contrario a las manecillas del reloj entonces significa que ese punto no debería estar ahí por lo que quitamos el punto de la pila y comparamos la orientación con el punto actual de la pila y el siguiente punto ordenado, hacemos esto hasta que el punto que tengamos que meter sea igual a nuestro p inicial, lo que indica que habremos acabado y los puntos que están en la pila son los que forman nuestro cierre convexo, este algoritmo tiene una complejidad O(nlogn) por el tiempo que nos toma ordenar los puntos. A continuación se anexa un video de la mano del canal de youtube Inside code que explica el algoritmo y también muestra como seria una ejecución,(el video esta en ingles pero es posible activar subtítulos en español para una mayor comprensión):
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:
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):
Ahora es turno de describir otra estrategia para resolver problemas, vimos que para los ordenamientos utilizamos el paradigma de divide y vencerás, sin embargo cuando podemos descomponer un problema en varios sub-problemas y estos a su vez tienen otros problemas superpuestos es decir estos sub-problemas pueden necesitar repetirse varias veces mientras resolvemos el problema inicial, entonces es un indicio de que podemos resolver el problema usando Programación Dinámica, la cual es una estrategia de programación usada cuando se desea evitar el calculo repetido de sub-problemas guardando el calculo de la solución para el problema que se repite y evitando la repetición del calculo para este mismo, es también buena idea usar programación dinámica cuando notamos que nuestro problema tiene una sub estructura optima, esto es cuando para hallar la solución optima del problema inicial tenemos que también hallar una solución optima paralos sub-problemas en los que dividimos el problema inicial, en otras palabras nos ayuda para resolver problemas de optimización. Una buena manera de saber si podríamos necesitar programación dinámica es pensar en una solución para el problema, si dicha solución "inocente" tiene una complejidad cuadrática entonces es posible que necesitemos usar programación dinámica. Para desarrollar un algoritmo usando programación dinámica necesitaremos una secuencia de 4 pasos que serán, primero la caracterización de la solución, es decir, describir la estructura de nuestra solución optima, visualizar la solución optima de nuestro problema para posteriormente aplicar el segundo paso, la recursión, que sera definir el valor de esta solución optima de manera recursiva, construyendo el algoritmo recursivo, lo siguiente es el tercer paso la memorización donde calcularemos el valor optimo y veremos donde guardar nuestros valores previos para poder utilizarlos posteriormente, finalmente el ultimo paso es la construcción de la solución optima esta es dada por la información que ya calculamos anteriormente. Cabe mencionar que también se puede utilizar la programación dinámica utilizando la tabulacion que es la técnica de resolver iterativamente desde el sub-problema mas pequeño hasta el sub-problema principal construyendo una tabla con los resultados y haciendo uso de la misma durante la resolución de los problemas. Como siempre se deja un video de apoyo para comprender de mejor manera el tema con ejemplos para una mayor claridad de la mano del canal ChioCode:
Algunos ejemplos populares de problemas que pueden ser resueltos con programación dinámica son encontrar la subsecuencia común mas larga o la multiplicación de una secuencia de matrices, particularmente encontrar la subsecuencia común mas larga es interesante por que puede ser extendida al reconocimiento de patrones lo cual es útil cuando hablamos de inteligencia artificial y lo que refiere al análisis y comparación de datos, a continuación se dejan 2 videos de apoyo que ilustran la solución de ambos problemas de manera amplia utilizando programación dinámica:
Algoritmo para encontrar la subsecuencia común mas larga de la mano del canal de youtube Xavier Ochoa:
Algoritmo para la multiplicación de una secuencia de matrices de la mano del canal de youtube Preparación Estudiantil de 10:
De la mano con la programación dinámica vienen también los algoritmos voraces o greedy algorithms que son usados cuando se nos presentan problemas que tienen sub-problemas cuyas posibles soluciones son demasiadas, estos algoritmos tienen como principio que si se topan con varias opciones se elija la que parece mas adecuada en ese momento, este puede en un principio no dar la solución optima a todos los problemas pero puede dar una solución suficiente para los mismos, el principio de elegir la opción mas optima en lugar de calcular todas las posibles soluciones y de entre ellas elegir la mas optima puede resultar mas intuitivo y sencillo, entonces hay que saber, ¿como podemos ver si con un algoritmo voraz es suficiente para resolver el problema y no tener que quebrarnos la cabeza con la solución de programación dinámica?, pues lo cierto es que al ir de la mano ambos conceptos para cada solución que utiliza un algoritmo voraz, generalmente existe otra solución al problema usando programación dinámica pero esta solución suele ser mas complicada, entonces para ver si nuestro problema puede ser resuelto con un algoritmo voraz necesitamos prestar atención a 2 propiedades la sub-estructura optima y la selección greedy,la sub-estructura optima es como mencionamos antes, dado un problema principal, si la solución optima de este problema necesita la solución optima de los sub-problemas que vallamos generando, esto indica que tenemos una sub-estructura optima, la segunda y mas importante es la selección greedy la cual consta de saber que podemos construir la solución optima global usando la elección de las opciones locales sin tener en cuenta los resultados de otros sub-problemas, es decir, tenemos que poder realizar esta elección sin depender de los resultados de los otros sub-problemas, tenemos ademas que probar que esta elección que realizamos en el algoritmo lleve a la solución optima global, esto se hace examinando alguna solución optima global que tenga algunos sub-problemas, suponemos que nuestro algoritmo greedy no da la solución optima con la selección que tenemos, entonces usamos una selección alternativa a la que toma nuestro algoritmo y eventualmente si la selección alternativa da una solución menos optima llegaremos a una contradicción por que se supone que nuestro algoritmo greedy no da la solución optima, con esta contradicción exhibida podemos decir que la contradicción viene de suponer que nuestro algoritmo greedy no era optimo y por ende para que no exista contradicción entonces nuestro algoritmo greedy es en efecto optimo, lo complicado para estos casos es entonces demostrar que nuestro algoritmo voraz da la solución optima siempre. A continuación se deja un video de apoyo sobre el tema de la mano del canal de youtube ChioCode en el que muestra también algunos ejemplos, ademas se anexan otros 2 videos de ejemplos concretos con problemas solucionados con algoritmos voraces:
