Greedy Random Start Algorithms: From TSP to Daily Life
2Greedy Random Start Algorithms: From TSP to Daily Life
Key Algorithm Concepts
Computational Complexity Classifications
•
Constant Time O(1): Runtime independent of input size (hash table lookups)
• "The holy grail of algorithms" - execution time fixed regardless of problem size
• Examples: Dictionary lookups, array indexing operations
•
Logarithmic Time O(log n): Runtime grows logarithmically
• Each doubling of input adds only constant time
• Divides problem space in half repeatedly
• Examples: Binary search, balanced tree operations
•
Linear Time O(n): Runtime grows proportionally with input
• Most intuitive: One worker processes one item per hour → two items need two workers
• Examples: Array traversal, linear search
•
Quadratic O(n²), Cubic O(n³), Exponential O(2ⁿ): Increasingly worse runtime
• Quadratic: Nested loops (bubble sort) - practical only for small datasets
• Cubic: Three nested loops - significant scaling problems
• Exponential: Runtime doubles with each input element - quickly intractable
•
Factorial Time O(n!): "Pathological case" with astronomical growth
• Brute-force TSP solutions (all permutations)
• 4 cities = 24 operations; 10 cities = 3.6 million operations
• Fundamentally impractical beyond tiny inputsPolynomial vs Non-Polynomial Time
•
Polynomial Time (P): Algorithms with O(nᵏ) runtime where k is constant
• O(n), O(n²), O(n³) are all polynomial
• Considered "tractable" in complexity theory
•
Non-deterministic Polynomial Time (NP)
• Problems where solutions can be verified in polynomial time
• Example: "Is there a route shorter than length L?" can be quickly verified
• Encompasses both easy and hard problems
•
NP-Complete: Hardest problems in NP
• All NP-complete problems are equivalent in difficulty
• If any NP-complete problem has polynomial solution, then P = NP
•
NP-Hard: At least as hard as NP-complete problems
• Example: Finding shortest TSP tour vs. verifying if tour is shorter than LThe Traveling Salesman Problem (TSP)
Problem Definition and Intractability
•
Formal Definition: Find shortest possible route visiting each city exactly once and returning to origin
•
Computational Scaling: Solution space grows factorially (n!)
• 10 cities: 181,440 possible routes
• 20 cities: 2.43×10¹⁸ routes (years of computation)
• 50 cities: More possibilities than atoms in observable universe
•
Real-World Challenges:
• Distance metric violations (triangle inequality)
• Multi-dimensional constraints beyond pure distance
• Dynamic environment changes during executionGreedy Random Start Algorithm
Standard Greedy Approach
• Mechanism: Always select nearest unvisited city
• Time Complexity: O(n²) - dominated by nearest neighbor calculations
• Memory Requirements: O(n) - tracking visited cities and current path
• Key Weakness: Extreme sensitivity to starting conditions
• Gets trapped in local optima
• Produces tours 15-25% longer than optimal solution
• Visual metaphor: Getting stuck in a valley instead of reaching mountain bottomRandom Restart Enhancement
• Core Innovation: Multiple independent greedy searches from different random starting cities
• Implementation Strategy: Run algorithm multiple times from random starting points, keep best result
• Statistical Foundation: Each restart samples different region of solution space
• Performance Improvement: Logarithmic improvement with iteration count
• Implementation Advantages:
• Natural parallelization with minimal synchronization
• Deterministic runtime regardless of problem instance
• No parameter tuning required unlike metaheuristicsReal-World Applications
Urban Navigation
• Traffic Light Optimization: Avoiding getting stuck at red lights
• Greedy approach: When facing red light, turn right if that's green
• Local optimum trap: Always choosing "shortest next segment"
• Random restart equivalent: Testing multiple routes from different entry points
• Implementation example: Navigation apps calculating multiple route optionsEconomic Decision Making
•
Online Marketplace Selling:
• Problem: Setting optimal price without complete market information
• Local optimum trap: Accepting first reasonable offer
• Random restart approach: Testing multiple price points simultaneously across platforms
•
Job Search Optimization:
• Local optimum trap: Accepting maximum immediate salary without considering growth traj...