Solve Travelling Salesman Problem for the following graph us

Solve Travelling Salesman Problem for the following graph using local search with 2-substitute neighborhoods. Initial Hamiltonian cycle is 2-4-3-5-1 Iteration I. Hamiltonian cycle: ___________; its length is _________ Iteration 2. Hamiltonian cycle: ___________; its length is _________ Iteration 3. Hamiltonian cycle: ___________; its length is _________ Iteration 4. Hamiltonian cycle: ___________; its length is _________ Iteration 5. Hamiltonian cycle: ___________; its length is _________ Iteration 6. Hamiltonian cycle: ___________; its length is _________ Iteration 7. Hamiltonian cycle: ___________; its length is _________ c(l, 2)= 10 c(l, 3) =4 c(l, 4) = 4 c(l, 5) =6 c(2, 3) 6 c(2, 4) =10 c(2, 5) =4 c(3, 4) = 8 c(3, 5) = 6 c(4, 5) = 6 If you have fewer than 7 iterations, leave excess lines empty. If you have more than 7 iterations, add additional lines below those 7 lines

Solution

iteration1:2-4-3-5-1 length is 30

2)2-4-1-3-5 ,length:24

3)2-4-5-3-1,length:26

4)2-3-5-4-1,length:24

5)2-3-4-5-1,length:26

6)2-3-1-4-5,length:20

7)2-5-3-4-1,length:20

8)2-5-4-3-1,length:22

9)2-5-1-4-3,length:22

10)2-1-3-4-5,length:28

11)2-1-4-5-1,length:26

12)2-1-5-4-3,length:30