Suppose we're going on a trip to the beach. It's 500 km away, with two stops: one at a petting zoo and one at a pizza restaurant. We will sleep at a lodge close to the beach on arrival and partake in three activities. The trip to the destination will take approximately 8 hours...
We drive on and start getting hungry; it’s time for the stop at the restaurant. But to our surprise, the restaurant recently went out of business. We need to adjust our plan and find another place to eat, which involves searching.
After driving around for a while, we find a restaurant, enjoy a pizza, and get back on the road. Upon approaching the shortcut private road, we realize that it’s 2:20. The road is closed; yet again, we need to adjust our plan.
Searching involves evaluating future states toward a goal with the aim of finding an optimal path of states until the ultimate goal is reached. Search algorithms use this intuition to solve hard problems in many pieces of software we use everyday.
Understanding that different algorithms have different computation costs is critical because addressing this is the entire purpose of intelligent algorithms that solve problems well and fast. Big O makes sense of this - if it's confusing, look at the Good, Bad, and Okay labels.
Theoretically, we can solve almost any problem by trying every possible option until we find the best one (brute-forcing), but in reality, the computation on traditional computer architectures could take hours or even decades, which makes it infeasible for real-world scenarios.
Uninformed search is also known as unguided search or brute-force search. Uninformed search algorithms have no additional information about the domain of the problem apart from the representation of the problem, which is usually a tree data structure.
Breadth-first search is an algorithm used to traverse or generate a tree. This algorithm starts at a specific node, called the root, and explores every node at that depth before exploring the next depth of nodes, until it finds a goal leaf node.
Depth-first search is another algorithm used to traverse a tree or generate nodes and paths in a tree. It starts at a specific node and explores paths of connected nodes of the first child, doing this recursively until it reaches the farthest leaf node before backtracking.
Search algorithms are versatile and useful in several real-world use cases, such as finding paths between nodes in a computer network, crawling web pages, and finding degrees of possible friendship in social networks.
If you enjoyed this thread and want to learn more about search and other AI algorithms, check out my book, Grokking Artificial Intelligence Algorithms: http://bit.ly/gaia-book, consider following me for more, or join my mailing list for infrequent knowledge drops in your inbox: https://rhurbans.com/subscribe.
Top comments (0)