Search Algorithms Part 3: Uninformed Search Algorithms — 2

In the previous blog, we have discussed the three popular uninformed search strategies: BFS, uniform-cost search and DFS, along with their advantages and disadvantages.

In this blog, we will discuss three more uninformed search algorithms, where two of them is intended to solve the infinity-depth problem of DFS, and the third one is a small improvisation on the idea of searching from the source to the destination.

Note: In the previous blog, you might have noticed this symbol occurring in some of the expressions: ^. This symbol refers to the mathematical expression “raised to the power of”. a^b means ‘a raised to the power of b’. I will be using this symbol with the same meaning throughout the series of blogs.

Depth-limited Search

To solve the problem of DFS getting stuck in a search tree with infinite depth, depth-limited search restricts the depth of the tree to a predetermined depth limit l. All the nodes at depth d is treated as if they have no successors.

Figure 1: Pseudo-code of the depth-limited search.

Depth-limited search solves the infinite-path problem. But the search is not complete if l < d. Even if l > d, optimal solution is not guaranteed, as we could be eliminating some of the solutions at depths > l. Time complexity is O(b^l), and space complexity is O(bm) (It is same as DFS, only with restricted depth to l). In fact, DFS can be viewed as a special-case of depth-limited search with l →infinity.

The problem with depth-limited search is to set the value of l optimally, so as to not leave out any solution, as well as keep the time and space complexity to a minimum. For example, in the problem of traveling from Arad to Bucharest, we can see that there are only 20 cities in the map. Hence, we can set the value of l to 19 (remember that we have set the root value to 0).

Figure 2: A part of the road map of Romania (revisited).

If we observe the map carefully, we can see that we can reach any city (state) from any other city (state) in at most 9 states. Using this information, called as the diameter of the state space, we can further reduce the l value to 9.

For most of the problems, we cannot estimate the depth limit until we have solved the problem.

Iterative Deepening Depth-first Search (IDS)

Iterative deepening search (or iterative-deepening depth-first search) offers a solution for the problem of finding the best depth limit. It gradually increases the depth — first 0, then 1, then 2, and so on — until a goal is found. It combines the advantages of both BFS and DFS. Like DFS, it consumes less memory: O(bd). Like BFS, it is complete when b is finite, and is optimal when the path cost is a non-decreasing function of depth.

Figure 3: Iterative-deepening search, repeatedly calling the depth-limited search while varying the depth limit in every iteration.

Iterative deepening search generates the states multiple times, but it is not too costly. In a search tree with nearly the same branching factor at every level, the size of the bottom levels are very huge compared to the top ones, hence it does not affect much if the nodes in the top levels are generated many times. To generate the node at depth d, the nodes at depth d-1 are generated twice, the nodes at depth d-2 are created 3 times, and so on. Hence, the total number of nodes generated will be:

which has the complexity of O(b^d), the same as BFS. For example, for d = 5 and b = 10:

n(IDS) = 50 + 400 + 3000 + 20000 + 100000 = 1,23,450

n(BFS) = 10 + 100 + 1000 + 10000 + 100000 = 1,11,110

In terms of performance measure, since IDS seems to be the hybrid form of BFS and DFS, IDS is the preferred uninformed search method when the search space is large and the depth of the solution is not known.

Bidirectional Search

The idea behind the bidirectional search is to run two searches simultaneously — one forward from the start state, and the other from the goal — hoping that the two will meet somewhere in the middle. It is implemented by replacing the goal test with a check to see whether the frontiers of the two search intersect (the solution is found if they do). The check can be performed when the node is generated, and can be done in constant time using hash tables.

The main aim of bidirectional search is to reduce the total search time. If we use BFS at both the ends as the search algorithm, the time and space complexity will be O(b^(d/2))(In the worst case, the two frontiers meet in the middle). The space can be reduced if one of them is IDS, but one of the frontiers must be in the memory to perform the check for the intersection.

The difficulty in using the bidirectional search is to search backwards. We need to find the predecessors of each state (all the states having the given state as their successor). If the actions of the search space are reversible, like in the Arad-Bucharest path-finding problem, the predecessors of the node are its successors.

If there are several goal states, then we can create a dummy goal state whose predecessors are the actual goal states.

Summary

This blog post was the continuation of the discussion on uninformed search algorithms. We have discussed couple of algorithms to handle the main problem faced in DFS — the infinite-depth situation. We came across depth-limited search, where we remove all the nodes beyond a certain limit, and iterative deepening search, where we incremented the limit of the depth until we find the solution. We finally discussed the bidirectional search, where we can perform two searches simultaneously to reduce the search time.

Figure 4: Evaluation of uninformed search strategies.

In the next blog, we will discuss on informed (heuristic) search algorithms.

References

Stuart Russel and Peter Norvig, Artificial Intelligence: A Modern Approach, 4th edition