Kotlin coding test course, Salesman's dilemma

Problem Description

A salesman needs to visit customers in various cities. The salesman can sell products in each city, and each city is located at different distances from one another. The goal of the salesman is to find the minimum cost of traveling to all cities and returning to the starting city. This problem is known as the famous “Traveling Salesman Problem (TSP)” and is one of the NP-complete problems.

Example for Problem Description

Let’s assume there are 4 cities as follows:

City A – (0, 0)
City B – (1, 2)
City C – (4, 3)
City D – (7, 7)

In this case, the salesman needs to find the minimum distance of the route that visits cities A, B, C, and D and returns back to A.

Approach to the Problem

There are several approaches to solving this problem, but the most commonly used method is Dynamic Programming. By using dynamic programming, we can optimize the exploration of all cities.

1. Dynamic Programming using Bit Masking

By using bit masking, we can represent the visit status of each city in bits. For example, the bit representation for 4 cities can be expressed with values from 0000 (no city visited) to 1111 (all cities visited). Each bit of 1 indicates that the corresponding city has been visited.

2. Defining Dynamic Programming State

Let’s define the DP table. dp[mask][i] represents the minimum cost to arrive at city i with a bitmask indicating the visited cities as mask. The initial state is dp[1<<i][i] (each=”” 0).=”” <="" =="" i corresponds to="" the="" cost="" of="" visiting="" city="" i="" itself="" 0.="">

3. Defining the Recurrence Relation

The recurrence relation is as follows:

dp[mask][i] = min(dp[mask ^ (1 << i)][j] + dist[j][i]) for all j where j is in mask and j != i

This recurrence relation calculates the optimal cost of coming to the current city i from previously visited city j while in the state with the bitmask as mask.

Code Implementation

Let’s implement the algorithm in Kotlin.

        
        fun main() {
            val cities = arrayOf(
                Pair(0, 0),
                Pair(1, 2),
                Pair(4, 3),
                Pair(7, 7)
            )
            val n = cities.size
            val dist = Array(n) { IntArray(n) }
            
            // Distance calculation
            for (i in 0 until n) {
                for (j in 0 until n) {
                    dist[i][j] = manhattanDistance(cities[i], cities[j])
                }
            }

            // DP array initialization
            val dp = Array(1 shl n) { IntArray(n) { Int.MAX_VALUE } }

            for (i in 0 until n) {
                dp[1 shl i][i] = 0
            }

            // DP processing
            for (mask in 1 until (1 shl n)) {
                for (i in 0 until n) {
                    if (mask and (1 shl i) == 0) continue
                    for (j in 0 until n) {
                        if (mask and (1 shl j) == 0 || i == j) continue
                        dp[mask][i] = minOf(dp[mask][i], dp[mask xor (1 shl i)][j] + dist[j][i])
                    }
                }
            }

            // Minimum cost calculation
            var minCost = Int.MAX_VALUE
            
            for (i in 0 until n) {
                minCost = minOf(minCost, dp[(1 shl n) - 1][i] + dist[i][0])
            }
            println("Minimum cost: $minCost")
        }

        fun manhattanDistance(city1: Pair, city2: Pair): Int {
            return Math.abs(city1.first - city2.first) + Math.abs(city1.second - city2.second)
        }

Code Explanation

The code above calculates the cost of the optimal path through dynamic programming in the following steps:

Distance Calculation: Calculate the Manhattan distance between two cities.
DP Initialization: Set the initial DP array in the state of not having visited any cities.
DP Processing: Calculate the optimal cost based on the bit mask and the current city.
Minimum Cost Calculation: Calculate the minimum cost of returning after visiting all cities.

Complexity Analysis

The time complexity of this algorithm is O(n^2 * 2^n). This works effectively when n is small, but performance degrades sharply as n increases. Therefore, this problem may be inefficient for large inputs, requiring various optimization techniques.

Conclusion

The “Salesman’s Dilemma” problem is one of the frequently encountered algorithmic problems in coding tests. Through this problem, one can understand the importance of dynamic programming and bit masking, as well as learn how to solve it using Kotlin. It is advisable to develop the ability to solve more complex problems by engaging in deeper learning of optimization and other techniques.

Kotlin coding test course, Salesman’s dilemma