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

Summary

This lecture explores advanced algorithmic concepts, including the closest pair problem in 2D and 3D spaces, as well as exhaustive search techniques. It introduces brute force methods for solving problems like finding the shortest pair of points and tackles complex issues like the Traveling Salesperson Problem (TSP), where the goal is to find the shortest route visiting all cities. The lecture emphasizes the high computational complexity of brute force algorithms (O(n^2) for closest pair and O(n!) for TSP) and highlights ongoing research to improve these approaches, making it an insightful discussion for students and researchers in algorithm design.

Takeaways

• 😀 The topic of the session is about analyzing and designing algorithms, with a focus on the closest pair search algorithm and exhaustive search techniques.
• 😀 The closest pair search involves finding the pair of points with the shortest distance between them, which can be represented in 2D or 3D space.
• 😀 In 2D space, the distance between two points (P1 and P2) is calculated using the Euclidean distance formula: √((x2 - x1)² + (y2 - y1)²). For 3D, the formula is extended by adding the Z components.
• 😀 The brute force approach to solving the closest pair problem involves calculating the distance between every possible pair of points, which results in a time complexity of O(n²).
• 😀 The brute force method compares each point against every other point, leading to a quadratic number of comparisons, and stores the smallest distance encountered.
• 😀 The algorithm works by iterating through pairs of points and updating the minimum distance if a smaller distance is found, and ultimately returns the closest pair of points.
• 😀 The complexity of the brute force algorithm is O(n²) because each point must be compared with every other point in the dataset.
• 😀 An exhaustive search technique involves systematically exploring all possible solutions, and is often used for problems like the Traveling Salesperson Problem (TSP), where the goal is to find the shortest route that visits all cities once.
• 😀 The TSP solution can be found by evaluating all possible permutations of routes, but this approach has a factorial time complexity, O(n!). For n=4, this leads to 3! = 6 possible routes to evaluate.
• 😀 Optimizations to exhaustive search, such as eliminating mirrored routes, can reduce the number of evaluations in some problems, but the overall complexity remains O(n * n!).
• 😀 Exhaustive search is still an active research area due to its inefficiency for large datasets, especially for problems like the Traveling Salesperson Problem where the factorial complexity becomes impractical for large n (e.g., n=20).