So far we have looked at uninformed and informed searches. Both have their advantages and disadvantages. But one thing that lacks in both is that whenever they find a solution they immediately stop. They never consider that there might be more than one solution to the problem and the solution that they have ignored might be the optimal one.
The simplest approach to find the optimal solution is this; find all the possible solutions using either an uninformed search or informed search and once you have searched the whole search space and no other solution exists, then choose the most optimal amongst the solutions found. But in reality, exploring the entire search space is never feasible and at times is not even possible.
Branch and Bound:
A search procedure to find the optimal solution. It finds the optimal path while maintaining the search efficiency. It eliminates the subtree if it can lead to a non-optimal solution on the basis of heuristic measures. For example, consider the 8-puzzle heuristic function of the previous lecture. As we declared that the most appealing heuristic in 8 puzzle games is the distance each tile away from the appropriate position. Assume that some 8puzzle board is represented as bellow.
The length of the complete path from S to G, S-D-E-F-G is 9. Similarly, the length of the partial path S-D-A-B also is 9 and any additional movement along a branch will make it longer than 9.
The length of the complete path from S to G is 9. Also, note that while traveling from S to B we have already covered a distance of 9 units. So traveling further from S D A B to some other node will make the path longer. So we ignore any further paths ahead of the path S D A B.
To explain the process in detail, the problem of finding the shortest path between two is considered.
We convert the map to a tree as shown below:
We proceed in a Best First Search manner. Starting at S we see that A is the best option so we explore A.
From S the options to travel are B and D, the children of A and D the child of S. Among these, D the child of S is the best option. So we explore D.
From here the best option is E so we go there,
Here we have E, F, and A as equally good options so we select arbitrarily and move to say A,
When we explore E we find out that if we follow this path further, our path length will increase beyond 9 which is the distance of S to G. Hence we block all the further sub-trees along this path, as shown in the diagram below.
Also Read: Best-First Algorithm Artificial Intelligence
Then we move to B on the right-hand side of the tree and bind the subtrees ahead of B as they also exceed the path length 9.
Notice that we have saved ourselves from traversing a considerable portion of the tree and still have found the optimal solution. The basic idea was to reduce the search space by binding the paths that exceed the path length from S to G.
Improvements in Branch and Bound:
The above procedure can be improved in many different ways.
- Dynamic Programming
The idea of estimates is that we can travel in the solution space using a heuristic estimate. By using “guesses” about the remaining distance as well as facts about distance already accumulated we will be able to travel in the solution space more efficiently. Hence we use the estimates of the remaining distance. A problem here is that if we go with an overestimate of the remaining distance then we might lose a solution that is somewhere nearby. Hence we always travel with underestimates of the remaining distance. We will demonstrate this improvement with an example.
The second improvement is dynamic programming. The simple idea behind dynamic programming is that if we can reach a specific node through more than one different path then we shall take the path with the minimum cost.
When we include these two improvements in branch and bound then we name it as a different technique known as A* Procedure.
This is actually a branch and bound technique with the improvement of underestimates and dynamic programming. We will discuss the technique with the same example as that in-branch and bound.
The values on the nodes shown in yellow are the underestimates of the distance of a specific node from G. The values on the edges are the distance between two adjacent cities.
Also Read: Heuristically Informed Searches AI
Our measure of goodness and badness of a node will now be decided by a combination of values that is the distance traveled so far and the estimate of the remaining distance. We construct the tree corresponding to the graph above. We start with a tree with the goodness of every node mentioned in it.
Standing at S we observe that the best node is A with a value of 4 so we move to 4.
Then B. As all the sub-trees emerging from B make our path length more than 9 units so we bound this path, as shown in the next diagram.
Now observe that to reach node D that is the child of A we can reach it either with a cost of 12 or we can directly reach D from S with a cost of 9. Hence using dynamic programming we will ignore the whole sub-tree beneath D
Now we move to D from S.
Now A and E are equally good nodes so we arbitrarily choose amongst them, and we move to A.
As the sub-tree beneath A expands the path length is beyond 9 so we bind it.
We visit F and finally we reach G as shown in the above diagrams
Notice that by using underestimates and dynamic programming the search space was further reduced and our optimal solution was found efficiently.
Like all informed search algorithms, it first searches the routes that appear to be most likely to lead towards the goal. What sets A* apart from a greedy best-first search is that it also takes the distance already traveled into account; the g(x) part of the heuristic is the cost from the starting point, not simply the local cost from the previously expanded node