Uninformed Search: BFS, DFS, DLS and IDS
Learn about uninformed search algorithms: Breadth First Search (BFS), Depth First Search(DFS), and improvements to Depth First Search.
Hi,
Welcome to my first newsletter tackling algorithms and data structures. To the best of my ability, I will try to explain everything as I would to a five year old. But before we begin, a recurring question on my mind is, why would a five year old need to learn about algorithms and data structures? For today, why would a five year old need to understand Uninformed Search? I have to be honest, I don’t know. Maybe they need it, maybe they don’t. I can assume that if you’re reading this, you either need it or you’re not a five year old 😅 but worry not, I do have a vivid imagination so I’ll pretend that we are all five year olds. As you can see, I will be addressing you personally in all my newsletters. Now let’s get started!
Introduction
Uninformed Search generally refers to search algorithms that have no additional information asides the one provided in the problem definition.
Imagine I sent you, my five year old, to go bring a white plate from the plate rack…don’t imagine, just look at the plate rack below
Clearly there’s no white plate on this rack, but you do not know that, you’d run downstairs, look through the rack, and conclude that there is no white plate. This is true; there is no white plate, so you’d come back to me saying “sorry, there is no white plate”. It wouldn’t matter that this white plate, below, is sitting right next to the rack.
Since it is uninformed search, you only look through the plate rack because that is all the context (information) I gave you. Rack, and white plate.
Now we’ve covered uninformed search, next we tackle Breadth First Search.
Breadth First Search and Depth First
Breadth First Search is arguably the more efficient of the two search algorithms. It provides a complete, and in most cases, optimal search solution when compared to depth first search, which we will explore next.
Given an assignment, as the name implies, breadth first search will search the breadth at each level and proceed downwards.
Imagine we have two staircases…yeah, don’t imagine, see it below
We have two stairs and we have a letter assigned to each step. If I asked you to find the letter “k”, how would you find it? Keep in mind that you DO NOT know what letter is assigned to what staircase or what step. You only know that you have two staircases, and a letter is assigned to each step of the staircase.
Breadth First Search (BFS) implores us to go through both staircases one step at a time, that is, we check the first step on staircase 1 to see if the letter assigned is what we are looking for (k), if it isn’t, check step 1 on staircase 2.
Breadth First Search will check step 1 on staircase 1 and 2 before proceeding to step 2.
To find the letter k, BFS will go through a→c→b→d→e→j→g→k [we proceed from step 1 on staircase 1 and move upwards only after going to the same level on staircase 2]
Depth First Search (DFS) on the other hand suggests that we go down staircase 1 in search of k, and only search staircase 2 if we do not find it. If you are lucky, k is in staircase 1, otherwise, you’d have spent all efforts searching staircase one for no reason. NO REASON! All of that work!
Depth First Search will check staircase 1 and proceed to check staircase 2 if we do not find what we are looking for in staircase 1. That is, we are going down in depth first thus the name.
To find the letter k, DFS will go through a→b→e→g→h→i→m→c→d→j→k. We can see that the path to find k consists of all steps on staircase 1 before the first step on staircase 2.
BFS vs DFS
The problem statement and nature of information provided will determine which of the algorithms is ideal but BFS is generally more performant and efficient. BFS is complete, meaning if a solution exists, it will be found. It is also optimal if the cost for each step is equal to 1.
DFS on the other hand fails on completeness if the depth of the staircase is infinite or there is a loop (staircase 1 leads to another staircase, say staircase 3?). As shown in the simple example above, it is also not optimal. If staircase 1 had five thousand (5000) steps, DFS will go through all of them before checking staircase 2.
DFS Improvements (DLS, IDS)
DFS is not always bad, in fact, with the right improvement and problem, it can outperform a BFS. Yes, you at the back, “What kind of improvements can be made to it?”, you asked. Well, I’m glad you asked. We know that the major setback of DFS is the fact that it can get caught up doing unnecessary work on staircase 1 when the solution we seek is on staircase 2, so can we tell it when to stop looking on staircase 1 and start looking at staircase 2? Yes. Yes, we can (or whatever Obama said).
Depth Limited Search (DLS) is an improvement on DFS that allows us to state the maximum depth (number of steps in our case) that we should go to on staircase 1 before moving to staircase 2.
If we used DLS instead of DFS on our staircase problem, we could say the maximum depth is 4 so our path to k would then be a→b→e→g →c→d→j→k. That is, we go down staircase 1 till we get to step 4, then we stop and start looking at staircase 2. As shown, this provides a shorter path to k when compared to the DFS path.
Iterative Deepening Search (IDS) is Depth Limited Search on steroids. Simply put, IDS is DLS in a loop. Instead of providing a static maximum depth as we did in depth limited search, we loop from 1 to the expected maximum provided maximum depth.
While IDS does in fact conduct repetitive work, it can provide better results. If the maximum depth provided for IDS is 4, we will eventually end up with the same solution as the DLS provided above, but that is only because letter k is on the 4th step.
For better clarity, let’s assume we are looking for the letter c.
Provided that the maximum depth is 4, DLS will result in our path being a→b→e→g →c because we will go down 4 steps on staircase 1 before starting on staircase 2. However, IDS will give us a→c because we iterate from 1-4, each time providing the current step as the maximum depth.
Code Implementation
See below examples of DLS and IDS implementation by me. Python isn’t my favorite language so I hope you don’t get lost.
That is it. With any luck you have a small idea of what BFS, DFS, DLS, and IDS are, even if it is just by explanation.
Subscribe
Thanks to those that already subscribed. While this is fun to do, I will be restricting future newsletters to only subscribers. However, it is possible for me to write every now and then for free as well. If you can, subscribe. Subscribers can make requests/suggestions about future newsletters. Tell me what you want to learn about.
Other Resources
Find other more technical resources that discuss more about DFS and BFS below. For interviewees, pay close attention to the last links.
https://www.geeksforgeeks.org/breadth-first-search-or-bfs-for-a-graph/
https://www.khanacademy.org/computing/computer-science/algorithms/breadth-first-search/a/the-breadth-first-search-algorithm
https://www.geeksforgeeks.org/depth-first-search-or-dfs-for-a-graph/
https://www.geeksforgeeks.org/top-10-interview-question-depth-first-search-dfs/
https://medium.com/techie-delight/top-25-depth-first-search-dfs-practice-problems-a620f0ab9faf
Conclusion
Thank you so much for subscribing and reading (hopefully). See you again next week.