[Marcus Vilain]

Hi all,

I know well A* algorithm and the general idea of the heuristic (where h compute the estimated cost from current node to the goal node).
I have difficulties to see where is this heuristics when using a Branch&Bound algorithm.
Is it still a estimated cost ?  Is it the way we do the branching ? Could someone can show me this h in a B&B peudo code please ?
Thanks for your help,
Marcus

[infurl]

Branch & Bound differs from A* in that B&B does not use a heuristic to try to guess the best path between the current state and the goal state, there is no estimation of the remaining cost. Instead it just keeps the best path to all possible intermediate nodes making it an optimal but exhaustive search. Though exhaustive it is still potentially a lot more efficient than a naive search.

B&B discards intermediate paths that it has found to be less than optimal. For example if a search for a path from A-Z has two potential partial solutions A-B-D and A-C-D with costs 100 and 200 respectively, then A-C-D and all it's derivatives will henceforth be ignored. Note that it could subsequently discover that a path A-C-E is cheaper than A-B-D-E at which point A-B-D-E will be ignored.

In other words, B&B can only prune paths to improve the search, but A* can prune paths and nodes to improve the search.

[Marcus Vilain]

Hi,

Thank you for your reply. I understand what you mean but I think i'm missing something...
By "optimal but exhaustive search" do you mean that B&B expand more nodes than A* ? That the search is not informed ?  I have read that A* is a special case of B&B, that B&B is a big improvement over A* in space complexity. How can be the case if B&B does not use an heuristics ? Sometimes , in B&B pseudo code,  the heuristics appears to estimate the bounds, sometimes not. I "suspect" that the way we branch is part of the heuristic (when this branching is based on a merit function).  In CSP many different branching technique exists (branch on an more/less constrained variable, etc.)
May I ask your opinion on these questions ?
Thanks
Marcus

[infurl]

Branch and bound expands every node. In that sense it is exhaustive.

Branch and bound only remembers the optimal path to each node so it does not explore every possible path. There is no estimation required to eliminate non-optimal paths to each intermediate node.

A* could be thought of as a special case of branch and bound where potentially all nodes could be opened, but heuristics are used to prioritise the opening of nodes and some nodes may never need to be opened before an optimal solution is found.

I looked at the wikipedia article for branch and bound. It seems a bit messed up and I don't think it's just because the terminology has changed since I learned about it.

https://en.wikipedia.org/wiki/Branch_and_bound

Here's a complete example to illustrate the algorithm. First a graph listed as start node, end node, cost.

A,B,1; A,C,2; B,D,1; B,E,1; C,D,2; C,E,1; D,F,1; E,F,1

You should be able to see there are a number of possible solutions from A to F. A naive search would explore all possible paths as follows:

A,B,D,F = 3 (search cost is 3)
A,B,E,F = 3 (search cost is 3)
A,C,D,F = 5 (search cost is 3)
A,C,E,F = 4 (search cost is 3)

If each segment costs 1 to explore then that's a total cost of 12 (4 paths * 3 steps) to find the optimal solution(s).

Using a stack to remember intermediate results (i.e. breadth first or depth first search) would allow you to reduce the cost to 10 because A,B and A,C would only be explored once each instead of twice each.

Branch and bound finds the optimal path to each node as follows:

A,B = 1 (search cost is 1)
A,C = 2 (search cost is 1)
A,B,D = 2 (search cost is 1)
A,C,D is ignored because it can't beat the best path already found to D
A,B,E = 2 (search cost is 1)
A,C,E is ignored because it can't beat the best path already found to E
A,B,D,F = 3 (search cost is 1)
A,B,E,F = 3 (search cost is 1)

If each segment costs 1 to explore then that's a total cost of 6 (1 for each path thats added on).

[Marcus Vilain]

Hi,

Thank you for your example. May be I don't fully understand or may be i'm hard to convice...
Something very interesting here is the cost to explore a segment. You set it to be always equal to 1. Does this cost could be depending on the current node and the goal node ? Can it be an estimate of the cost to reach the goal ? If so, is not that the heuristic that will impact the bound calculation, the branching ?

Anyway, thanks a lot !
Marcus

[infurl]

Thank you for your example. May be I don't fully understand or may be i'm hard to convice...
Something very interesting here is the cost to explore a segment. You set it to be always equal to 1. Does this cost could be depending on the current node and the goal node ? Can it be an estimate of the cost to reach the goal ? If so, is not that the heuristic that will impact the bound calculation, the branching ?

There's cost associated with the algorithm and cost associated with the problem. They're totally unrelated. The goal is to find the best solution to the problem with the most efficient algorithm, so you certainly want to minimise the cost of the algorithm.

Anyway, if you haven't started coding a solution already you are just going to have to make a leap of faith and start trying to implement it yourself. Deep understanding will follow quickly after that I'm sure.

[Marcus Vilain]

Hi,

Sorry for my misunderstanding. I had read wrong. The difference between algorithmic cost and the cost of the problem are of course two different things.
I try too hard to say that the B & B is as efficient as A * because it also uses a heuristic. That B&B can also be optimal in terms of the number of nodes explored while guaranteeing a solution with minimal cost.
Thanks for your clear explanations,
Marcus