Pertemuan 6 - Analisis & Desain Algoritma - Brute Force (Part II) Jarak & TSP - Informatika UNJANI

Summary

El video explica conceptos avanzados de algoritmos, centrando la atención en la búsqueda del par de puntos más cercano mediante fuerza bruta y en la búsqueda exhaustiva, ejemplificada con el Problema del Viajante de Comercio (TSP). Se detallan fórmulas para calcular distancias en 2D y 3D, se presentan algoritmos paso a paso, y se analiza la complejidad temporal de cada enfoque. Además, se discuten las limitaciones de la búsqueda exhaustiva para conjuntos grandes y cómo ciertos patrones permiten optimizar parcialmente el cálculo. El contenido combina teoría y práctica, mostrando tanto la implementación como los desafíos de la optimización en problemas computacionales complejos.

Takeaways

• 😀 El problema de la pareja más cercana consiste en encontrar dos puntos con la menor distancia entre todos los puntos dados.
• 😀 La distancia entre dos puntos en 2D se calcula utilizando la fórmula euclidiana basada en el teorema de Pitágoras.
• 😀 El algoritmo de fuerza bruta compara todas las posibles parejas de puntos para encontrar la distancia mínima.
• 😀 El número de comparaciones en el problema de puntos cercanos es aproximadamente n(n-1)/2.
• 😀 La complejidad temporal del algoritmo de fuerza bruta para este problema es O(n²).
• 😀 El algoritmo utiliza variables como distancia mínima (d_min) y recorre todos los pares mediante bucles anidados.
• 😀 El análisis de complejidad incluye operaciones de inicialización, aritmética y comparaciones.
• 😀 El método de búsqueda exhaustiva evalúa todas las posibles soluciones para encontrar la mejor.
• 😀 Aunque la búsqueda exhaustiva garantiza una solución óptima, requiere mucho tiempo y recursos computacionales.
• 😀 El problema del viajante (TSP) busca la ruta más corta que visita todas las ciudades una vez y regresa al origen.
• 😀 El TSP se puede modelar como la búsqueda de un circuito hamiltoniano con peso mínimo.
• 😀 El número de rutas posibles en el TSP es (n-1)! lo que crece extremadamente rápido con el número de ciudades.
• 😀 La complejidad total del TSP con fuerza bruta es O(n × n!), lo que lo hace impráctico para grandes valores de n.
• 😀 Algunas rutas en el TSP son equivalentes por simetría, lo que permite reducir el número de evaluaciones a la mitad.
• 😀 A pesar de pequeñas optimizaciones, la complejidad factorial del TSP sigue siendo muy alta.
• 😀 Problemas como el TSP siguen siendo áreas abiertas de investigación debido a su alta complejidad computacional.

Q & A

¿Qué es el algoritmo de 'brute force' en la búsqueda de pares de puntos más cercanos?

El algoritmo de 'brute force' calcula la distancia entre cada par de puntos en un conjunto y selecciona el par con la distancia mínima. Su complejidad es O(n²) debido a la necesidad de comparar todos los pares posibles.

¿Cómo se calcula la distancia entre dos puntos en un plano bidimensional?

La distancia entre dos puntos P1(x1, y1) y P2(x2, y2) se calcula usando la fórmula de Pitágoras: √((x2 - x1)² + (y2 - y1)²).

¿Cómo cambia la fórmula de distancia si los puntos están en 3D?

En 3D, se agrega la coordenada z: √((x2 - x1)² + (y2 - y1)² + (z2 - z1)²).

¿Qué es 'exhaustive search' y en qué se diferencia del 'brute force'?

'Exhaustive search' es una técnica que revisa todas las soluciones posibles, considerando propiedades especiales de los elementos como permutaciones o combinaciones. Es similar a 'brute force', pero más general y aplicable a problemas complejos como rutas y combinaciones.

¿Qué problema resuelve el 'Traveling Salesperson Problem' (TSP)?

El TSP busca encontrar el recorrido más corto que visita cada ciudad exactamente una vez y regresa al punto de partida, minimizando la distancia total recorrida.

¿Cuál es la complejidad de tiempo para resolver el TSP mediante exhaustive search?

La complejidad es O(n * (n-1)!), ya que se deben evaluar todas las posibles rutas Hamiltonianas y calcular sus distancias.

¿Qué es un circuito Hamiltoniano?

Un circuito Hamiltoniano es un recorrido en un grafo que visita cada vértice exactamente una vez y regresa al punto de partida.

¿Cómo se puede reducir la cantidad de rutas a evaluar en el TSP?

Se puede reducir evaluando solo la mitad de las rutas, eliminando las que son reflejos de otras, ya que estas reflejan recorridos equivalentes.

¿Qué sucede con la complejidad del TSP cuando el número de ciudades aumenta?

La complejidad crece factorialmente, lo que hace que incluso con 20 ciudades el cálculo exhaustivo sea prácticamente imposible de realizar en un tiempo razonable.

¿Por qué la investigación sobre algoritmos brute force y exhaustive search sigue siendo relevante?

Porque aunque los métodos son conceptualmente simples, la eficiencia y la optimización de estos algoritmos para grandes conjuntos de datos o aplicaciones prácticas sigue siendo un campo de estudio abierto y desafiante.

¿Qué pasos sigue el algoritmo brute force para encontrar el par de puntos más cercano?

1) Inicializa la distancia mínima con un valor grande. 2) Compara cada punto con todos los demás. 3) Calcula la distancia entre los puntos. 4) Si la distancia calculada es menor que la mínima registrada, actualiza la distancia mínima y los puntos asociados. 5) Repite hasta revisar todos los pares.

¿Qué ejemplo se utiliza en el video para ilustrar el TSP?

Se utilizan cuatro puntos A, B, C y D con distancias específicas entre ellos para calcular manualmente todas las rutas posibles y encontrar la ruta más corta.