Hello, in this blog post, we will delve deeply into one of the frequently encountered problems in Java coding tests: the “Traveling Salesman Problem.” This problem is very useful for laying the foundations of graph theory and combinatorics, and it serves as a good example to apply various algorithmic techniques.<\/p>\n
The Traveling Salesman Problem can be described as follows. The salesman is tasked with finding the shortest path that visits all the given cities and returns to the starting city. All cities are connected, and the distance between any two cities is provided. The goal is to complete the tour of the visited cities with the minimum cost.<\/p>\n
Output the minimum cost to visit all cities once and return to the starting city.<\/p>\n
This problem is classified as an NP-hard problem, generally solvable with a complete search method. However, since N is limited to a maximum of 10, it can be solved efficiently using a bitmask technique with dynamic programming (DP). By using a bitmask, we can represent the visit status of each city as bits, allowing us to calculate the minimum cost for all possible paths.<\/p>\n
The basic idea for solving the problem is as follows:<\/p>\n
The code below implements the Traveling Salesman Problem according to the given algorithm. Check how each step progresses through the code.<\/p>\n
\n\nimport java.util.Arrays;\n\npublic class TravelingSalesman {\n \n static int N; \/\/ Number of cities\n static int[][] C; \/\/ Cost matrix\n static int[][] cache; \/\/ Array for memoization\n static final int INF = Integer.MAX_VALUE; \/\/ Infinite value\n\n public static void main(String[] args) {\n \/\/ Example: Number of cities N = 4\n N = 4; \n C = new int[][]{\n {0, 10, 15, 20},\n {5, 0, 9, 10},\n {6, 13, 0, 12},\n {8, 8, 9, 0}\n };\n\n \/\/ Initialize the memoization array\n cache = new int[1 << N][N];\n for (int i = 0; i < (1 << N); i++) {\n Arrays.fill(cache[i], -1);\n }\n\n int result = tsp(1, 0); \/\/ Start from the initial city 0 having visited all cities\n System.out.println(\"Minimum cost: \" + result);\n }\n\n static int tsp(int visited, int pos) {\n \/\/ Base case: when all cities have been visited\n if (visited == (1 << N) - 1) {\n return C[pos][0] == 0 ? INF : C[pos][0]; \/\/ Cost to return to the starting city\n }\n\n \/\/ If already computed\n if (cache[visited][pos] != -1) {\n return cache[visited][pos];\n }\n\n int answer = INF;\n\n \/\/ Check all cities\n for (int city = 0; city < N; city++) {\n \/\/ If the city hasn't been visited yet\n if ((visited & (1 << city)) == 0 && C[pos][city] != 0) {\n int newVisited = visited | (1 << city);\n int newCost = C[pos][city] + tsp(newVisited, city);\n answer = Math.min(answer, newCost);\n }\n }\n\n return cache[visited][pos] = answer; \/\/ Store the minimum cost\n }\n}\n<\/code>\n<\/pre>\nCode Explanation<\/h2>\n\n- Main Method:<\/strong> Initializes the number of cities and the cost matrix with the example, calls the TSP function, and outputs the result.<\/li>\n
- tsp Method:<\/strong> Recursively calculates the minimum cost based on the bitmask and current city information.<\/li>\n
- Base Case:<\/strong> When all cities have been visited, returns the cost to return to the starting city.<\/li>\n
- Memoization:<\/strong> Already computed states are stored in the cache array and reused as needed to enhance efficiency.<\/li>\n<\/ol>\n
Results<\/h2>\n
The above code calculates the minimum cost for the provided cities and cost matrix. The output is the minimum cost to visit all cities and return to the starting city. You can input your own cost matrix using this code and check the results, which will help you understand the flow of the algorithm.<\/p>\n
Conclusion<\/h2>\n
Through this tutorial, we learned how to solve the Traveling Salesman Problem using dynamic programming and bitmasks. This problem frequently appears in coding tests and will significantly aid in learning fundamental algorithmic techniques to tackle such challenges. Like other algorithm problems, there are multiple ways to approach the problem. Try various solutions to enhance your algorithm skills.<\/p>\n
Stay tuned for our next post, where we will cover another problem. If you have any questions or comments, please leave them below. Thank you!<\/p>\n","protected":false},"excerpt":{"rendered":"