Animation: Branch and Bound

Animation Systems Collection -- Animations Collection

Description

The branch and bound strategy divides a problem to be solved into a number of subproblems, similar to the strategy backtracking.

To avoid the complete calculation of all partial trees, one first tries to find a viable solution and note its value as a upper bound for the optimum. All following calculations are terminated as soon as their costs exceed the costs of the upper bound.

If a new cheaper solution was found, its value is used as the new upper bound.

In this way, many calculations that would have to be done using pure backtracking can be stopped early on.

The animation uses the travelling salesman problem as an example. The travelling salesman problem comprises of finding the cheapest round path on a weighted graph where each node is only visited once.

Under the graph and its adjacency matrix, the algorithm is described verbally and the current step is highlighted.

Screen Shot(s):

Description of the basic approach

Example - Traveling Salesman

First cheapest route found

Dead end - route more expensive than cheapest known route

Classification

• Algorithms
• Algorithmic Strategies
• Optimization Problems

Animation Rating

You can provide a rating for this animation. The rating is performed on a scale of 1 to 10, where 10 is the highest possible grade.

1(very bad) 2 3 4 5 6 7 8 9 10(very good)

File information

Title	Branch and Bound
Animation URL	http://www.animal.ahrgr.de/Anims/en/branchAndBound.aml
Animation Applet	Animal Applet
Animation System	Animal
Animation Type	dynamic full VCR
Supported OS(s)	Linux,MacOS,Windows 95,Windows 98,Windows ME,Windows NT,Windows 2000,Unix
Author(s)	Guido Rößling
Date	1999-05-10
File Size size	4928 Byte
Number of Accesses:	17670
Added to DB by	Guido Rößling
Average Rating	5.2192(73 submitted ratings)
Language:	en
Number of Accesses:	17670

BibTeX bibliographic entry for citations:

@Misc{Rößling:1999,
   author = {Guido Rößling},
   title = {Branch and Bound},
   howpublished = {WWW: \url{http://www.animal.ahrgr.de/Anims/en/branchAndBound.aml}},
 }