Branch and bound & A* algorithm

---

Types

• Branch and Bound
• Branch and bound with extended List
• Branch and Bound with Admissible distance
• A* = all the above combined

Branch and Bound

First of all let’s understand what branch and bound really is.

So, the branch and bound algorithm extends all the paths it can follow. That means it visits all the nodes and all the paths to generate the shortest distance.

i.e. from S we can extend branches to A and B. From B we can do the same and extend to C and A. and so on.

Now we will add the heuristic distances to all the nodes. We will select those nodes with the shortest path in along the way.

The oracle is the shortest path here. We started with oracle in mind and then extended all other paths and found the shortest path here. We search all the branches hence we call this branch and bound algorithm. Here as we can see here,

The oracle is not needed in branch and bound algorithms because we are extending the node with the shortest path always so it’s not that important. Even when we got the goal node G after extending A. We continued the search because we want to make sure the path is the shortest path (There is nothing in that algorithm that can store knowledge).

Branch and bound with extended list

Now we wanna improve our way to find the shortest path. As we discussed the branch and bound algorithms extend all the paths they can do to find the shortest path. The main problem with this approach is that it extends the same node multiple times as we can see in the image above the A has been extended twice. We don’t need to extend node A twice because we have already achieved the A with the shortest distance possible. So here we introduce a list which we call extended list. This list tracks all the nodes visited hence we can share this with the extended algorithm.

Now, when we visit A with this algorithm we need not extend it again after visiting B. Hence a lot of computation is avoided.

note that we are still extending all the paths after we found the node. But we are now extending only those nodes which have not been extended.

Branch and Bound plus Admissible Distance

There is another thing we can use to solve this and that is using admissible distance. The admissible distance is the direct distance from one node to another. As if the crow would fly between the nodes. The admissible distance is the only way to think about the way the human mind works. Like if our initial point is at the middle of the graph and we want to go to our final point(let’s say right). By only using the extended list, our algorithm will waste its time searching to the left. But if we use admissible distance as our heuristic we can avoid searching to our left.

But there is a problem with this approach as well, there can be a dead end at some point. Like in the first graph, if we reach E i.e. if we reach the dead end. Our algorithm can get stuck at that position. So instead

A* algorithm

At the end we are at the A* algorithm which is the combination of Branch and Bound plus Extended list plus Admissible distance algorithms.

Here we use the formula

where the h(x) is the distance covered and g(x) is the distance left in for the search!

That is adding the extended list with the admissible distances. Hence we won’t find the problem that occurred in the extended list nor we will get stuck at the dead end.

Limits of A*

Well, the graphs are not about just the Maps. They can be anything. These graphs can show us information that is not in the physical form, like a computer network with the no of computing units at each node or an electrical grid, where the distance actually doesn’t matter much(a signal can pass at the speed of light). We can show a graph like this in a hypothetical situation.

If we draw a A* graph for this graph. We will find that it will give us false results. As our algorithm will give us result like, S → A(1 +100) → C(1+1+0) → G(1+1+100)

So A* algorithm is not useful for graphs that are not maps, which means it can be only applied to the maps which can are based on the actual physical world.