﻿==================================================
8. TSP – LEAST COST BRANCH AND BOUND
==================================================

ALGORITHM:
1. Create the cost matrix and mark unavailable edges as INF.
2. Perform row and column reduction.
3. Calculate the initial lower bound.
4. Insert the root node into a min-priority queue.
5. Remove the node with minimum cost.
6. Generate child nodes for unvisited cities.
7. Set visited row and column values to INF.
8. Reduce the child matrix and calculate its lower bound.
9. Prune nodes that cannot improve the best tour.
10. When all cities are visited, add the return cost.
11. Display the minimum-cost tour.

FORMULA:
Child Cost = Parent Cost + Edge Cost + Reduction

RECURRENCE:
No standard recurrence. Uses state-space tree search.

TIME COMPLEXITY:
Best Case    : Depends on pruning.
Average Case : Input-dependent.
Worst Case   : O(n! * n^2)
Space        : O(n! * n^2)

IMPORTANT:
1. LC Branch and Bound uses a priority queue and pruning.