A salesman visits 4 locations, A, B, C, and D. Distances between A and B; A and D; A and D; B and C; B and D; and C and D are given by 2, 3, 4, 3, 4, 2 respectively. Use an exhaustive search approach to find the best travel route for the salesman. Show all possible routes and their lengths and find the smallest. What is the efficiency of this algorithm?
A salesman visits 4 locations, A, B, C, and D. Distances between A and B; A and D; A and D; B and C; B and D; and C and D are given by 2, 3, 4, 3, 4, 2 respectively.
- Use an exhaustive search approach to find the best travel route for the salesman. Show all possible routes and their lengths and find the smallest.
- What is the efficiency of this
algorithm ?
Exhaustive Search
To solve combinatorial issues, a brute-force method is used (permutations, combinations). In this method, each element in the problem is generated, and only the elements that satisfy all the constraints are chosen as the final element. This strategy is not simple; to find all combinational items, we require a generative method.
Traveling Salesman Problem
Even if you don't know what this issue is, you've probably heard of it because it is so well-known. What should be the shortest tour that a salesman can accomplish by stopping in each city just once?
This issue can be modelled using a weighted graph. Cities are represented by vertices, and distances are represented by edge weights. Finding the shortest path in a Hamiltonian circuit then becomes the issue. A cycle that goes through every vertex of the graph exactly once is known as a Hamiltonian circuit.
Step by step
Solved in 4 steps with 1 images
