Virtual Labs

Tools

Aim

Theory

Pretest

Procedure

Simulation

Posttest

References

Contributors

Feedback

Aim

Theory

Pretest

Procedure

Simulation

Posttest

References

Contributors

Feedback

Traveling Salesman Problem(TSP) Using Heuristic Search

Choose difficulty:

Beginner

Intermediate

Advanced

In which search problem, to find the shortest path, each city must be visited once only?

a: Depth-first search traversal on a given map represented as a graph Explanation

Explanation

b: Finding the shortest path between a source and a destination Explanation

Explanation

c: Travelling Salesman problem Explanation

Explanation

d: None of the above Explanation

Explanation

What is the objective of the traveling salesman problem?

a: To minimize the total distance traveled by the salesman Explanation

Explanation

b: To maximize the total distance traveled by the salesman Explanation

Explanation

c: To find the shortest route between two cities Explanation

Explanation

d: None of the above Explanation

Explanation

In the TSP problem of n cities, the time taken for traversing all cities, without having prior knowledge of the length of the minimum tour will be_______.

a: O(n) Explanation

Explanation

b: O(n2) Explanation

Explanation

c: O(n!) Explanation

Explanation

d: O(n/2) Explanation

Explanation

Which of the following algorithms is a heuristic for the traveling salesman problem?

a: Dijkstra's algorithm Explanation

Explanation

b: A* algorithm Explanation

Explanation

c: Nearest neighbor algorithm Explanation

Explanation

d: None Explanation

Explanation

Heuristic function h(n) is ______?

a: Lowest path cost Explanation

Explanation

b: Average path cost Explanation

Explanation

c: Cheapest path from root to goal node Explanation

Explanation

d: Estimated cost of cheapest path from root to goal node Explanation

Explanation

What is the time complexity of the Traveling Salesman algorithm?

a: O(1) Explanation

Explanation

b: O(n log n) Explanation

Explanation

c: O(n!) Explanation

Explanation

Community Links Sakshat Portal Outreach Portal FAQ: Virtual Labs

AGPL 3.0 & Creative Commons (CC BY-NC-SA 4.0)