Reference no: EM133395717

Question: In computer science theory, you learned about NP-complete problems. One of the best-known such problems is the Travel Salesperson Problem. The problem is defined as follows: Given: Let n be a natural number. A set of cities c1, c2, ..., cn. A complete set of distances between each pair of cities. The distances are positive integers. A bound B which is a positive integer. Problem. Is there a traveling salesperson's tour of the cities whose distance is less than B? Recall the tour starts at one city, visits every other city exactly once, and returns to the starting point. The total distance is simply the sum of the distances between each pair of cities. The fact that this problem is NP-complete indicates it isn't likely to have any efficient algorithms for it.

So, you are to construct a traveling-salesperson-tour approximation algorithm. Use your knowledge of computer-science theory to devise your approximation algorithm. Implement your approximation algorithm in either C, Rust, Clojure, or Prolog. It takes the same input as the Traveling Salesperson Problem. It outputs ‘YES' if your approximation algorithms finds a solution whose distance is less than B, and otherwise outputs ‘NO'. On ill-formed inputs, output ‘NO'. Describe how your approximation works.