Question

Which of the following statements is/are true about ‘Traveling Salesman problem’ (TSP)?
1) It is an NP-hard problem in combinatorial optimisation
2) There aren’t any exact algorithms known to solve TSP therefore we use heuristic techniques
3)Ant colony optimisation can generate “good solutions” to TSP using a simulation of an ant colony
4)All of the above

Answer 1

Answer:

4

Explanation:

Because there is no other way around the idea of salesman to be put on

Answer 2

Answer:4

Explanation:

I will explain all the options.

First option 1

In Traveling salesman problems you are looking at the shortest loop that goes through every city in a given no of cities in a set. Let it be that you are given a set of cities, and the solution of the shortest loop among these cities. The way you will verify it will be your propaganda.In other words, the way you get to know there’s not another loop that is shorter than the one given to you. The only known way to verify that a provided solution is the shortest possible solution is to actually solve the entire TSP. Since it takes exponential time to solve NP, the solution cannot be checked in the real polynomial time. Hence, this problem is NP-hard, but not in NP.

Option 2: As said earlier The Travelling Salesman Problem is one of the known NP-hard problems, which means that there is no specific particular algorithm to solve it in given time complexity. The minimum expected time to obtain optimal solution is exponential of the polynomial function.

Option 3

Ant Colony Optimisation has been largely applied to solving various combinational optimization problems such as traveling salesman problems. Although ACO has a very effective capacity to find out solutions to combinational optimization problems, it has the problems of being stagnant, premature nature of convergence and the convergence speed of ACO is apparently slow.