Consider a TSP with 4 cities A, B, C, D and the following distance mat

Back to the 2024 paper

Module 2: Fundamental Algorithmic Strategies

20247m

Consider a TSP with 4 cities A, B, C, D and the following distance matrix:

	A	B	C	D
A	0	10	15	20
B	10	0	35	25
C	15	35	0	30
D	20	25	30	0

Answer the following:
(i) Use the branch-and-bound algorithm to find the shortest possible route that visits all cities exactly once and returns to the starting city.
(ii) Show the branching steps and calculate lower bounds for each partial solution.
(iii) Identify how the bounding helps prune the search tree.

Search Google Ask AI

Similar questions

Design & Analysis of AlgorithmsAn all-pairs shortest-paths problem is efficiently solved using: - (i) Dijkstra's algorithm - (ii) Bellman-Ford algorithm - (iii) Kruskal algorithm - (iv) Floyd-Warshall algorithm20192m Design & Analysis of AlgorithmsWrite short notes on: Travelling Salesman Problem20247m Design and Analysis of Algorithms In the below given weighted graph W (Given in form of matrix), apply Bellman Ford's algorithm to find the shortest distances from source node 3. Write the time complexity of Bellman Ford's algorithm. | | 1 | 2 | 3 | 4 | 5 | |---|---|---|---|---|---| | 1 | 0 | 1 | 8 | 1 | 4 | | 2 | 1 | 0 | 12 | 4 | 9 | | 3 | 8 | 12 | 0 | 7 | 3 | | 4 | 1 | 4 | 7 | 0 | 2 | | 5 | 4 | 9 | 3 | 2 | 0 |20237m Design and Analysis of Algorithms Design a system that finds the shortest paths between various locations in a city. The locations and roads are represented using a graph. What algorithm would you use if: (i) All roads have equal length (ii) Roads have varying lengths, but no negative lengths (iii) Some roads have negative lengths Justify your choices with suitable algorithms and reasoning.20247m

PreviousThe 0/1 Knapsack Problem is a classical combinatorial optimization problem. Explain how this problem can be solved using: (i) Brute-force method (ii) Greedy method (iii) Dynamic Programming (iv) Branch-and-Bound For each approach, explain the algorithm, time complexity, and limitations. Highlight why the greedy method may not always yield the optimal solution.NextAnswer the following: (i) Compare and contrast the BFS and DFS traversal techniques in terms of their algorithmic approach, time complexity, data structures used, and typical applications. (ii) Give examples where one is preferred over the other.