**Branch and Bound Travelling Salesman Problem**

Travelling Salesman Problem is the important topic of the Analysis & Design of Algorithm. Moreover, freestudy9 has all kind of important information and topic related to it.

**Branch and Bound**

- Set up a bounding function, which is used to compute a bound (for the value of the objective function) at a node on a state-space tree and determine if it is promising.
- Promising (if the bound is better than the value of the best solution so far): expand beyond the node.
- Non-promising (if the bound is no better than the value of the best solution so far). Not expand beyond the node (pruning the state-space tree).

**Traveling Salesman Problem**

Construct the state-space tree:

**A node = a vertex:**a vertex in the graph. A node that is not a leaf represents all the tours that start with the path stored at that node; each leaf represents a tour (or non-promising node).**Branch-and-bound:**we need to determine a lower bound for each node.- For example, to determine a lower bound for node [1, 2] means to determine a lower bound on the length of any tour that starts with edge 1—2.

- Expand each promising node, and stop when all the promising nodes have expanded. During this procedure, prune all the non-promising nodes.
**Promising node:**the node’s lower bound is less than current minimum tour length.**Non-promising node:**the node’s lower bound is NO less than current minimum tour length.

- Because a tour must leave every vertex exactly once, a lower bound on the length of a tour b (lower bound) minimum cost of leaving every vertex.
##### The lower bound on the cost of leaving vertex v

_{1}given by the minimum of all the nonzero entries in row 1 of the adjacency matrix.- The lower bound on the cost of leaving vertex v
_{n}given by the minimum of all the nonzero entries in row n of the adjacency matrix. - Because every vertex must entered and exited exactly once, a lower bound on the length of a tour is the sum of the minimum cost of entering and leaving every vertex.
- For a given edge (u, v), think of half of its weight as the existing cost of u. And half of its weight as the entering cost of v.
- The total length of a tour = the total cost of visiting (entering and exiting) every vertex exactly once.
- The lower bound of the length of a tour = the lower bound of the total cost of visiting (entering and exiting) every vertex exactly once.
- Calculation:
- For each vertex, pick top two shortest adjacent edges. (their sum divided by 2 is the lower bound of the total cost of entering and exiting the vertex); add up these summations for all the vertices.

- Assume that the tour starts with vertex a and that b visited before c.

**Related Terms**

ADA Algorithms, Back Tracking, Knapsack Problem using Backtracking, Minmax Principle

## Leave a Reply