In the Traveling Salesman Problem (or TSP), the input is a complete graph G = (V

Question

In the Traveling Salesman Problem (or TSP), the input is a complete graph G = (V, E) with vertex set V = {v_1, v_2,..., v_n} and edge weights given by a function w : E rightarrow R^+. The objective is to find a tour of G with minimum cost. A tour of G is an ordering of its vertices. We think of a tour as a permutation^1 pi P_n. That is, the tour defined by pi is upsilon_pi (1) upsilon_pi (2)... upsilon_pi (n) and its cast is sigma_i = 1^n - 1 w (upsilon_pi (i), upsilon_pi (I + 1)). Write pseudocode to solve TSP using a brute-force approach. Assume you are given w as an n Times n matrix W, where W[i][j] = w(v_i v_j). Assume that you can loop over the set of permutations of n elements in Theta(n!) time (your pseudocode should use the line for pi P_n do). Solution. Your Solution here Compute the complexity of your algorithm from part (a). Solution. Your Solution here

Explanation / Answer

a)Given an initial_tour picked at random from all the tours:

  

best_length = length (initial_tour)

   For Pn do

       if length() < best_length

       best_length = length()

End_For

   Print best_length

b)Since the algorithm only loops through all the n! permutations, computed in a O(n!) time, it’s time complexity is O(n!).

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.