Bidirectional Search

Hello people! In this post we will talk about Bidirectional Search, a powerful search strategy which can be used if you have a goal directed agent in a (possibly infinite) search space. The idea behind Bidirectional search is to run two simultaneous searches, one forward from the source state and the other backward from the goal, hoping that the two searches meet somewhere in the middle.

In this post we will talk about Bidirectional Breadth First Search, where we apply BFS from the source and goal simultaneously until search routes intersect. Visually, the way regular BFS would progress would be something like this –

Regular BFS Theory of ProgrammingBut if we applied BFS simultaneously from source (S) and goal (G), visually it would look something like this –

Bidirectional search visualisation Theor of ProgarmmingWe can already start to seem some improvement as the number of vertices visited would be lesser.

In terms of complexity, if branching factor is b, and distance from source to goal is d, then, BFS would take O(bd), but Bidirectional search would take O(bd/2 + bd/2) ⇒ O(bd/2), which is quite better than O(bd). So in many cases a bidirectional search is faster as the amount of exploration done is lesser.

Properties of Bidirectional search

  • Our goal in Bidirectional search is to find a path from source to goal.
  • We can use any search algorithm on both sides, Bidirectional search is more of a strategy than a fixed algorithm. Using BFS on both sides is the most popular option as it guarantees an optimal path.
  • Bidirectional search must be used only when your goal is well defined. Eg. for a Rubik’s cube, your goal is to fill each side with one color, which is your goal and your current configuration of cube is your source state. We could use Bidirectional search in this scenario. But in chess, your goal is to checkmate the other player, but a checkmate can happen in thousands of ways. Bidirectional search isn’t feasible in chess.
  • Bidirectional search using BFS needs the edge weights to be same or non-existent. So usually Bidirectional BFS is used in undirected unweighted graphs.

Code

Writing the code for Bidirectional BFS is easier if you have already written the code for Breadth First Search using queue. Basically, all the variables we used in BFS get doubled here. That is, for Bidirectional BFS, we will use 2 queues and 2 parent arrays. One set will be used for applying BFS from source and other set will be used for applying BFS from goal. So we can call them –

  • sourceParent – the parent array to construct paths for BFS from source vertex.
  • sourceQueue – the queue for BFS from source vertex.
  • goalParent – the parent array to construct paths for BFS from goal vertex.
  • goalQueue – the queue for BFS from goal vertex.

Although we are using a separate set of variables for BFS from source and goal, the way in which they operate will be the same, i.e., the steps like picking first element in queue, enqueuing its adjacent vertices, etc. We can put that logic in a separate method called BFSExplore().

So how will we know if the BFS from source and goal have an intersecting node? After expanding a layer on either side, we will check if a vertex has been marked as visited in both of the BFS. If yes, then that is our intersection node. Recall, that we can check if a vertex has been visited if its parent value has been set.

Now the only thing left is to return the final path. There’s no genius logic for this, just do it in a brute force way 😛 . Add all vertices from source → intersecting_vertex using sourceParent into a collection. Then add all the vertices from intersecting_vertex → goal using goalParent into the same collection. Be careful, don’t add the intersecting_vertex twice in the path 😉

I have given you all the theory you need to write the code for Bidirectional BFS. It may take some time, but do try your best to write the code yourself. You can refer to my code below if you get stuck –

I hope this has given you a good understanding of Bidirectional search. Keep practicing! Happy coding! 😀

Iterative Deepening Depth First Search (IDDFS)

Hello people! In this post we will talk about another search algorithm Iterative deepening depth first search (IDDFS) or Iterative deepening search (IDS). This algorithm is used when you have a goal directed agent in an infinite search space (or search tree).

Why do Breadth First Search (BFS) and Depth First Search (DFS) fail in the case of an infinite search space?

  • In DFS, you would recursively look at a node’s adjacent vertex. DFS may not end in an infinite search space. Also, DFS may not find the shortest path to the goal. DFS needs O(d) space, where d is depth of search.
  • BFS consumes too much memory. BFS needs to store all the elements in the same level. In the case of a tree, the last level has N / 2 leaf nodes, the second last level has N / 4. So, BFS needs O(N) space.

Iterative deepening depth first search (IDDFS) is a hybrid of BFS and DFS. In IDDFS, we perform DFS up to a certain “limited depth,” and keep increasing this “limited depth” after every iteration.

Let us take an example to understand this –

Our starting node (A) is at a depth of 0. Our goal node (R) is at a depth of 4. The above example is a finite tree, but think of the above tree as an infinitely long tree and only up to depth = 4 is shown in the diagram.

As stated earlier, in IDDFS, we perform DFS up to a certain depth and keep incrementing this allowed depth. Performing DFS upto a certain allowed depth is called Depth Limited Search (DLS). As Depth Limited Search (DLS) is important for IDDFS, let us take time to understand it first.

Let us understand DLS, by performing DLS on the above example. In Depth Limited Search, we first set a constraint on how deep (or how far from root) will we go. Let’s say our limit (DEPTH) is 2. Now, in the above diagram, place your hand to cover the nodes at depth 3 and 4. Now, by looking at the rest of the nodes, can you tell the order in which a normal DFS would visit them? It would be as follows –

A B E F C G D H

Can you do it for DEPTH = {0, 1, 2, 3, 4} ? Just cover the nodes you don’t need with your hand and try to perform DFS in you mind. You should get answers like this –

DEPTH DLS traversal
0 A
1 A B C D
2 A B E F C G D H
3 A B E I F J K C G L D H M N
4 A B E I F J K O P C G L R D H M N S

Now that you have got an idea of Depth Limited Search, Iterative deepening depth first search is just one loop away! The pseudo-code for IDDFS is as below –

IDDFS(tree):
    for depth = 0 to infinity:
        if (DLS(tree, depth)):
            return true

    return false

Before you race off to code, here are a few things –

  • IDDFS is used to check if the goal is reachable from start node. So its return type is boolean.
  • IDDFS is only used to check, not return the path from start node to goal. So we don’t maintain anything like parent array (like in DFS).
  • IDDFS is meant to run DLS from 0 → ∞, but we will write our IDDFS program to run DLS from 0 → MAX_DEPTH. Because in real world we never run anything up to ∞.
  • First code the DLS method, then add the IDDFS method which calls the DLS method.
  • IDDFS is meant to run in an infinite space tree. So, you can use a binary tree if you want, but in my opinion using an N-ary tree makes more sense. So, in my code below I use N-ary tree, the code taken from my article on N-ary tree.

You should be capable of writing the code for Iterative deepening depth first search now. Try it, I’m sure you can 😉 You can refer to my code if you get stuck –

JavaOutput
A
   B
      E
         I
      F
         J
         K
            O
            P
   C
      G
         L
            R
   D
      H
         M
         N
            S
Depth = 0, DLS Traversal => A, 
Depth = 1, DLS Traversal => A, B, C, D, 
Depth = 2, DLS Traversal => A, B, E, F, C, G, D, H, 
Depth = 3, DLS Traversal => A, B, E, I, F, J, K, C, G, L, D, H, M, N, 
Goal node = R is not reachable at a depth of 3
Depth = 0, DLS Traversal => A, 
Depth = 1, DLS Traversal => A, B, C, D, 
Depth = 2, DLS Traversal => A, B, E, F, C, G, D, H, 
Depth = 3, DLS Traversal => A, B, E, I, F, J, K, C, G, L, D, H, M, N, 
Depth = 4, DLS Traversal => A, B, E, I, F, J, K, O, P, C, G, L, R, 
Goal node = R is reachable at a depth of 4

In the output, the tree is printed first, then the IDDFS traversals. Purposefully, I took the goal node as a node which is not reachable by depth = 3 but is reachable by depth = 4. As you have noticed from the output above, we visit the nodes at depth = 0 a lot, the nodes at depth = 2 a little fewer but we visit them multiple times too, and we visit the nodes at depth = DEPTH_MAX only once. This may seem inefficient, but it is actually not. This is because, there are very few nodes at depth = 0, but a lot of nodes at depth = DEPTH_MAX. If ‘d‘ is depth, and ‘b‘ is the branching factor in the search tree (this would be N for an N-ary tree), then mathematically –

Iterative deepening depth first search time complexity Theory of ProgrammingThe time complexity remains O(bd) but the constants are large, so IDDFS is slower than BFS and DFS (which also have time complexity of O(bd)).

Time complexity Space complexity
DFS O(bd) O(d)
BFS O(bd) O(bd)
IDDFS O(bd) O(bd)

Iterative deepening depth first search may not be directly used in practical applications but the technique of iteratively progressing your search in an infinite search space is pretty useful and can be applied in many AI applications.

Congrats, your AI just got better! Keep practicing! Happy coding! 😀

Jump Search Algorithm

Hello, people…! In this post, we will discuss a new search algorithm, Jump Search, which searches for an element in a sorted array in O(√N) time. It is slower than binary search, then why learn it? What if the interviewer purposely asks you to write a search algorithm with O(√N) worst case complexity? You would be banging your head to cook up a new algorithm 😛 . Anyways, it’s fun learning new stuff, isn’t it?

Algorithm

Imagine you are given a sorted array, and you are applying linear search to find a value. Jump Search is an improvement to this scenario. Instead of searching one-by-one, we search k-by-k. Let’s say we have a sorted array A, then jump search will look at A[1], A[1 + k], A[1 + 2k], A[1 + 3k] … and so on.

As we keep jumping, we keep a note of the previous value and its index. Once we get a situation where A[i] < searchValue < A[i + k], then it means the value we want is in between the previous jump ends. So now we could simply perform a linear search between that A[i] and A[i + k].

Jump Search

Sound too boring? Here’s where things get interesting! How will we know the most optimal value of the jump size?

Optimal Jump Size

If we try to write down the complexity of the algorithm we described above.


\frac{n}{m} + m - 1
Now, let’s see for which value of ‘m’ does this expression have a minimum. To do this we differentiate with respect to ‘m’ and equate it to 0


\frac{n}{ -m^{2} } + 1 = 0 \newline \newline  n = m^{2} \newline \newline  m = \sqrt{n}
So, the optimal jump size is √N.

Code

It is a pretty simple algorithm to code. Try it by yourself. You can refer to my code below if you get stuck 🙂 .

CC++JavaPython
    
    
    
    

Faster Jump Search

How can we make this version of jump search faster? A few people might have guessed it by now! 😉 In the above algorithm, once we find the jump ends which contains the value we need, we are performing a linear search. But we could perform another jump search between these two jump ends! And then recursively perform jump search until we are left with only one element.

Implementing this version is more challenging. Firstly, you need to modify your above method to something which looks like this –

public Pair jumpSearchUtil(int[] arr, int val, int low, int high) {
    // return jump ends if condition meets
    // return null or a -1 otherwise
}

We must return the i and j between which the value is found or return null. And then call this from another method jumpSearch() which keeps calling jumpSearchUtil() until the jump interval has only 2 elements or it returns a null. We will need to return 2 values, the left end and the right end of the jump. So, we will use a structure in C, or a class in Java.

Try to code this version of Jump Search algorithm. If you get stuck, you can use my code below as a reference –

CJava
    
    

This optimised version has the following complexity –


\sqrt{N} + \sqrt{\sqrt{N}} + \sqrt{\sqrt{\sqrt{N}}} + ... + 1

This is still O(√N) in the worst case. But it is much faster because, in the previous version, the complexity was √N + √N, which made it O(√N), but here the additional terms have very low values.

I hope you’ve understood about the jump search algorithm. If you did, let me know by commenting! Keep practising! Happy Coding! 😀