Question

Please solve in Java,

The traveling salesman, wishing to visit a set of cities in the shortest time possible. A tour is a path that starts in one city, visits all the other cities, and then returns to the starting point. The relevant pieces of information, then, are the cities and the distances between them. The given set of cities in this problem are: A, B, C, D, E , and F The cost matrix (distances in miles) between any pair of cities is given below: A B C D E F A - 21 13 17 25 9 B 21 - 14 19 21 27 C 13 14 - 8 18 20 D 17 19 8 - 29 17 E 25 21 18 29 - 15 F 9 27 20 17 16 - Implement the following Hill Climbing local search algorithm to solve the above travelling salesman problem.

Use Java programming language.

Algorithm:

1. Start with an initial current state (generated randomly), such as: C, B, E, F, A, D The cost of this state is: = C to B + B to E + E to F + F to A + A to D + D to C = 14 + 21 + 15 + 9 + 17 + 8 = 84 LOOP: 2. Generate three different possible successor moves from the current state as defined below:

i) Generate three random pairs of numbers: (c1, c2), (c3, c4), (c5, c6) Such that: Ci ( 1 <= i <= 6), has a random value between 1 and 6 (inclusive).

Make sure that the two random values in each pair are different. Also, make sure that no two pairs have the same random values. i.e. all pairs are unique.

ii) Then, the possible three successor moves from the current state are: Move 1: swap the city in position c1 with the city in position c2.

For example: given the current state: C, B, E, F, A, D if c1 = 2 and c2= 5, then swap city B (in position 2) with city A (in position 5) in the current sate to get the following move: C, A, E, F, B, D Move

2: swap the city in position c3 with the city in position c4 Move 3: swap the city in position c5 with the city in position c6

3. Calculate the cost of each of these three successor moves.

4. Choose the move with the best move (i.e. least cost) from these three successor moves.

5. If this best move state has a higher cost than the cost of current state, then return this current state as a solution with its cost and exit the algorithm. Otherwise, replace the current state by this best move state. Output: Initial state Best state found by the algorithm The cost of the best state Number of iterations the algorithm execute to find this best state

Answer 1

class GFG 
{ 

        static int tsp(int[][] graph, boolean[] v, 
                                int currPos, int n, 
                                int count, int cost, int ans) 
        { 

        
                if (count == n && graph[currPos][0] > 0) 
                { 
                        ans = Math.min(ans, cost + graph[currPos][0]); 
                        return ans; 
                } 


                for (int i = 0; i < n; i++) 
                { 
                        if (v[i] == false && graph[currPos][i] > 0) 
                        { 

                                v[i] = true; 
                                ans = tsp(graph, v, i, n, count + 1, 
                                                cost + graph[currPos][i], ans); 

                                v[i] = false; 
                        } 
                } 
                return ans; 
        } 

        // Driver code 
        public static void main(String[] args) 
        { 

                int n = 6; 

                int[][] graph = {{0, 21, 13, 17,25,9}, 
                                                {21,0,14,19,21,27}, 
                                                {13,14,0,8,18,20}, 
                                                {17,19,8,0,29,17},
                        {25,21,18,29,0,15},
                        {9,27,20,17,16,0}
}; 


                boolean[] v = new boolean[n]; 

                v[0] = true; 
                int ans = Integer.MAX_VALUE; 

         
                ans = tsp(graph, v, 0, n, 1, 0, ans); 

        
                System.out.println(ans); 
        } 
}