Question 4 (Pseudo-Code of Two-Opt Algorithm) (24 points) (8 points each) 2-opt Pseudo Code (Time Critical...

Transcribed Image Text:

Question 4 (Pseudo-Code of Two-Opt Algorithm) (24 points) (8 points each) 2-opt Pseudo Code (Time Critical Part) // city [i] is ith city (permutation array) #define dist (a, b) dmat [city [a]] [city [b]] do { Distance matrix: 0(n) time and space minchange = 0; for (i = 0; i < cities-2; i++) { Doubly-nested for loop for (j=i+2; j change) { minchange = change; mini= i; minj = j; } } } // apply mini/minj move while (minchange < 0); It suffices to compute change in length: O(1) time O(n) iterations needed to reach local minimum: overall algorithm is O(n) A) How can you terminate the algorithm that is given above. List at least 2 different termination conditions. B) Suppose the first two-opt move that improves the objective function value can be directly adopted at each iteration of the algorithm. That is we do not need to find the best two-opt as it is given in the pseudo code. How should we update the algorithm to do that? C) We want to adopt two-opt moves that improves objective function value at least 5% at each two- opt iteration of the algorithm. How should we update the algorithm to do that? Question 4 (Pseudo-Code of Two-Opt Algorithm) (24 points) (8 points each) 2-opt Pseudo Code (Time Critical Part) // city [i] is ith city (permutation array) #define dist (a, b) dmat [city [a]] [city [b]] do { Distance matrix: 0(n) time and space minchange = 0; for (i = 0; i < cities-2; i++) { Doubly-nested for loop for (j=i+2; j change) { minchange = change; mini= i; minj = j; } } } // apply mini/minj move while (minchange < 0); It suffices to compute change in length: O(1) time O(n) iterations needed to reach local minimum: overall algorithm is O(n) A) How can you terminate the algorithm that is given above. List at least 2 different termination conditions. B) Suppose the first two-opt move that improves the objective function value can be directly adopted at each iteration of the algorithm. That is we do not need to find the best two-opt as it is given in the pseudo code. How should we update the algorithm to do that? C) We want to adopt two-opt moves that improves objective function value at least 5% at each two- opt iteration of the algorithm. How should we update the algorithm to do that?

Answer rating: 100% (QA)

A Two different termination conditions for the algorithm 1 Set a maximum number of iterations after ... View the full answer