Discussion
The travelling salesman problem can be solved using :
Answer: C
Of the options, the travelling salesman problem is solved using a minimum spanning tree.
TSP is NP-hard, so no efficient exact method is known. For a metric TSP (distances obeying the triangle inequality), the standard approach builds a minimum spanning tree, walks it in preorder and skips repeated vertices; the resulting tour costs at most twice the optimum. Christofides' algorithm improves on this, again starting from an MST.
BFS and DFS traversals only visit vertices without regard to weights, and an arbitrary spanning tree carries no cost guarantee.
No comment is present. Be the first to comment.
Loading…
Post your comment
Please log in or register to post a comment.
Examination Categories
- SSC Exams
- Banking Exams
- Teaching Exams
- Civil Services Exams
- Railways Exams
- Engineering Recruitment Exams
- Defence Exams
- State Government Exams
- Police Exams
- Insurance Exams
- Nursing Exams
- Other Government Exams
- NRA CET
- PG Entrance Exams
- Campus Placement
- MBA Entrance Exams
- CUET and UG Entrance
- Judiciary Exams
- Regulatory Body Exams
- Software Development