Over the last few decades, we have seen a lot of technologies come by and make a significant impact. Most of these technologies, if you have noticed, revolve around intelligent actions. Let’s say you are in the middle of a street and you want a cab. We can solve this problem in a couple of different ways depending on the level of intelligence we put into our solution. How can we design something that can make use of all the data and provide the best possible solution to the person in the middle of the street? We can say that intelligent action involves search in some way. Searching is needed in a variety of situations, so developing mathematically and computationally strong algorithms is an absolute must. In most of the real life situations, we don’t really know where to look or how a particular search is going to pan out. How do we formulate this?
What is an “intelligent action”?
In our above example, to solve the problem, a cab company comes by and offers you a booking service over the phone. It solves the problem at hand but it is not exactly intelligent, is it? It’s just a regular service that already exists! On the other hand, a new company comes by and says that they have an app that tracks your location via GPS and offers you a cab service based on real time requests. Now that is an intelligent action!
What is blind search?
Blind search, also called uninformed search, works with no information about the search space. It only knows to distinguish the goal state from all the others. What this means is that it will know when you have reached to goal, but it will not tell you if a particular path is going to lead us to our goal. These algorithms have no domain knowledge of the problem state and they do not use heuristics. The only information available to blind search algorithms is the state, the successor function, the goal test and the path cost. The last sentence had a lot of jargon, right? To put it in another way, whenever we are searching for something using blind search, we only know the following:
- State: where we are right now
- Successor function: the method to get to the next step
- Goal test: a test to see whether or not we reached our goal
- Path cost: the penalty of the path; sometimes a path might look promising, but it will also have an associated penalty
Why don’t you show me an example?
Alright, let’s look at an example then. The image to the left shows a small town and how different places are connected. Let’s assume that you are currently at the Inn and you want to get to the Bakery. If we produce a search tree, level 1 will have three states; Brewery, Dry Cleaner and Library. These are basically the places that are directly connected to the Inn. A blind search will have no preference as to which node it should explore first. We can clearly see that picking the Brewery will give us the best result. We will see later as to how we can develop search strategies that incorporate some intelligence.
If it’s dumb, why should we use it?
You may wonder why one would ever use blind search, when we could instead use a search with some intelligence built in. Well, it’s because there may not be any information available to us. We might just be looking for an answer and won’t know we’ve found it until we see it. What we discussed here is a cute little problem with 9 nodes where we are fully aware of where everything is. In real world, you will have millions of nodes and you will have no idea where to look for your target. You will only know once you have reached your destination that you have reached your goal. Not only that, it is also useful to study these blind searches as they form the basis for some of the intelligent searches that we shall be looking at later.
Almost all the modern technologies you see on the internet use blind search. Some of most well-known algorithms that you know of are based on blind search algorithms. The algorithms that fall under this category include Depth First Search, Breadth First Search, Uniform Cost Search, Iterative Deepening, Bidirectional Search, etc. The different kinds of blind searches only differ in the order in which we expand the nodes. This, in turn, can have a dramatic effect as to how well the search performs.
————————————————————————————————-
Perpetual Enigma 