The Traveling Salesman Problem: Why Some Problems Are Impossible to Solve Perfectly

The Real Problem: Optimizing Delivery Routes

Imagine you need to create the best route for a delivery driver to visit 5 different customers and return to the starting point. Seems simple, right? You could even calculate all the possibilities manually.

But what if there were 10 customers? Or 20? Or 100?

Here’s the problem: the number of possible routes grows absurdly. For 20 cities, there are more combinations than you could calculate in your entire lifetime, even with the most powerful computer in the world.

The important lesson: Sometimes, seeking the perfect solution is impossible. Instead, we need to find a “good enough” solution that works in practice.

What Is the Traveling Salesman Problem?

The Traveling Salesman Problem is one of the most famous problems in computer science. The idea is simple: you have several cities to visit and need to find the shortest route that passes through all of them exactly once and returns to the starting point.

Why Is It So Difficult?

The problem is that the number of possible routes grows exponentially. Here are some examples:

• 5 cities: 120 different routes to test
• 10 cities: 3,628,800 different routes
• 20 cities: More than 2 quintillion routes (a number with 18 zeros!)

To put it in perspective: if you tested 1 billion routes per second, it would still take more than 60 years to test all possibilities for just 20 cities.

Why Can’t We Solve It Perfectly?

Science hasn’t discovered a way to solve this type of problem quickly and perfectly yet. The more cities you add, the more time the computer needs to find the ideal solution. For real problems (with dozens or hundreds of points), this becomes impossible.

The Practical Solution: Greedy Algorithms

Since we can’t find the perfect solution in useful time, we use a strategy called a greedy algorithm. The idea is simple: at each step, we choose the best available option at that moment, without thinking too much about the future.

It’s like when you’re hungry and choose the closest dish at the restaurant, instead of analyzing the entire menu to find the perfect meal.

Where Do We Use This?

Delivery apps: When you order food and the app calculates the delivery driver’s route.

GPS and maps: When you ask for the fastest route between multiple destinations.

Route planning: Logistics companies use this to optimize deliveries.

When NOT to Use?

If you have few points (less than 10), it might be worth testing all possibilities to find the perfect solution. But for larger problems, the greedy algorithm is the best option.

How It Works in Practice: The Nearest Neighbor Algorithm

Let’s implement a simple solution in Kotlin. The strategy is: always go to the nearest city that hasn’t been visited yet. It’s like a GPS that always chooses the closest next destination.

data class City(val name: String)

/**
 * Represents the distance map: Origin City -> (Destination City -> Distance)
 */
typealias DistanceMap = Map<City, Map<City, Int>>

fun travelingSalesmanGreedy(initialCity: City, map: DistanceMap): List<City> {
    val route = mutableListOf<City>()
    val visited = mutableSetOf<City>()
    
    var currentCity = initialCity
    var totalDistance = 0
    
    route.add(currentCity)
    visited.add(currentCity)

    // While there are unvisited cities in the graph
    while (visited.size < map.size) {
        val neighbors = map[currentCity] ?: emptyMap()
        
        // Greedy Strategy: Filter unvisited and select the one with minimum distance
        val nextEntry = neighbors
            .filter { it.key !in visited }
            .minByOrNull { it.value }
            
        if (nextEntry != null) {
            val (nextCity, distance) = nextEntry
            visited.add(nextCity)
            route.add(nextCity)
            totalDistance += distance
            currentCity = nextCity
        } else {
            // Disconnected graph: no path to remaining cities
            break 
        }
    }
    
    // Cycle closure: Return to origin city
    map[currentCity]?.get(initialCity)?.let { returnDistance ->
        route.add(initialCity)
        totalDistance += returnDistance
    }

    println("Route Analysis Complete. Approximate Total Distance: ${totalDistance}km")
    return route
}

fun main() {
    // Cities in São Paulo state, Brazil
    val saoPaulo = City("São Paulo")
    val campinas = City("Campinas")
    val santos = City("Santos")
    val sorocaba = City("Sorocaba")
    val ribeiraoPreto = City("Ribeirão Preto")

    val map: DistanceMap = mapOf(
        saoPaulo to mapOf(campinas to 100, santos to 80, sorocaba to 100, ribeiraoPreto to 320),
        campinas to mapOf(saoPaulo to 100, santos to 150, sorocaba to 120, ribeiraoPreto to 220),
        santos to mapOf(saoPaulo to 80, campinas to 150, sorocaba to 180, ribeiraoPreto to 400),
        sorocaba to mapOf(saoPaulo to 100, campinas to 120, santos to 180, ribeiraoPreto to 280),
        ribeiraoPreto to mapOf(saoPaulo to 320, campinas to 220, santos to 400, sorocaba to 280)
    )

    val finalRoute = travelingSalesmanGreedy(saoPaulo, map)
    println("Visit Sequence: ${finalRoute.joinToString(" -> ") { it.name }}")
}

How the Code Works

The code is very simple to understand:

1. We start in São Paulo: We choose the initial city.

2. We find the nearest city: We look at all connected cities and choose the one that’s closest and we haven’t visited yet.

3. We go to it: We add that city to our route and mark it as visited.

4. We repeat: We continue this process until we’ve visited all cities (Campinas, Santos, Sorocaba, Ribeirão Preto).

5. We return to São Paulo: Finally, we return to the starting city.

The code uses a simple loop (for) to find the nearest city, making everything easier to understand than using complex functions. The result will be a route that visits all cities efficiently!

Comparison: Perfect Solution vs. Practical Solution

Why Not Use the Perfect Solution?

Characteristic	Test All Possibilities	Greedy Algorithm
Result	Always the best possible route	Good route (usually 95-99% of optimal)
Speed	Impossible for more than 15 cities	Fast even with hundreds of cities
Practical Use	Doesn’t work in real systems	Works perfectly in production

Why This Matters

In practice, the difference is minimal: A route that’s 5% longer than perfect is still excellent. And you can calculate it in milliseconds, not millennia.

Scales well: Whether you have 10 cities or 1000 cities, the greedy algorithm remains fast and useful.

Easy to understand and maintain: The code is simple, any developer can understand and modify it.

Important Lessons

1. Perfection isn’t always possible: Some problems are simply too difficult to solve perfectly. And that’s okay!

2. Good enough is enough: A solution that works well and is fast is better than a perfect solution that never finishes.

3. Greedy algorithms are useful: They transform impossible problems into practical solutions that work in the real world.

4. Think about context: In real systems, a route that’s 5% longer but calculates in milliseconds is much better than the perfect route that takes years to calculate.

Conclusion

The Traveling Salesman Problem teaches us a valuable lesson: we don’t always need the perfect solution. Sometimes, a good enough solution that works fast is exactly what we need.

In programming and in life, knowing when to stop seeking perfection and accept a practical solution is an important skill.

---

This article is part of the “Understanding Algorithms” series, based on the book by Aditya Y. Bhargava.