Search Algorithms In a Nutshell
What could be better than funny analogies to help us understand a concept?
What is Search problem?
A search problem is a problem that can be represented as a set of states.
The goal is to find a path from an initial state to a goal state by making a sequence of legal moves.
There are many ways to visualize such problems, include:
A Single-Player game: Trying to pass every level in a single-player game such as “Super Mario”, “Minesweeper” etc.
A NP-complete problem: Trying to find an optimal solution for a problem, e.g. searching for a valid boolean variable assignment which satisfies all conditions in “SAT”, checking if all vertices of a graph can be colored using 3 colors in “3-COL”, etc.
But none of them really apply to the concrete world, right?
How about “Marry-Your-Soulmate”? A young man who recently moved into LA, searching for his soulmate, and wanting to marry her (if exists).”
Problem Statement
Everything counts as a date: It can be a minute of small talk, a barbecue party, a sleepover, the engagement party, whatever.
States: Let Z denote the set of all states. Each state in Z is a tuple z = (a,b,…), consisting of different features.
It all starts with no dates.
Initial state: The initial state z_0, usually empty (or an accepted solution if a local search approach is chosen).
It ends well, when he marries his soulmate.
Goal states: A solution based on an acceptance criteria, it can be a boolean function f: Z -> bool or a relation of accepted end states R = {z_1, …}.
If everything fits, he goes on a date with a girl, and this might affect his decision-making.
Actions: A function a: Z -> Z which transfers from a state to another state under certain conditions.
A date can affect him positively or negatively. It helps him make better decisions.
Cost: The cost of the action as a way of penalizing the actions. c: Z -> Z.
Search problems can be solved using search algorithms, which explore the space of possible states in order to find a solution.
Memoization Techniques
There are some general design ideas which are not limited to any search algorithm but solely depend on the given use case.
Memoization is a way of avoiding the re-computation of duplicate / redundant states, and heavily used in search algorithms too.
Redundancy elimination
It doesn’t matter where, when or how I met her, only whether I met her or not.
It is used in search algorithms to eliminate duplicate or unnecessary states in the search space.
It doesn’t matter if I choose it right now or later, it doesn’t make sense to compare them.
It makes use of Dynamic Programming, which is the technique of storing the best outcomes for each partial solution to avoid re-computation.
Cycle elimination
It’d be probably better if I got to know her in a cafe instead of hospital clinic.
It is used to prevent a search algorithm from getting stuck in an infinite loop by not revisiting states that have already been explored.
The score of current option can be improved by finding a better sequence of past actions followed by current option
It is implemented using a very simple condition, whether current path contains the new state.
Comparison of Search Algorithms
There are 4 main reasons to (or not to) choose an algorithm:
How many dates should I go on in the worst case?
Time Complexity: Upper time bound of search.
How many dates should I keep in mind while going on a date?
Space Complexity: Maximum amount of space used during search.
Is the girl I’m marrying my soulmate?
Correctness: Is the found solution always correct?
Can I always find someone who is willing to marry me?
Completeness: Is the correct solution always found?
There is no perfect algorithm, but different decisions.
Search Algorithms
Depth-First Search
I’ll marry the first girl I meet. Won’t go to a date with another girl, as long as it goes. However, no guarantee to find my soulmate.
TL;DR: I’ll exploit my current option as far as I can.
It is an approach, where a search algorithm explores as far as possible along each branch before backtracking.
It is space-efficient, but it fails the correctness and completeness test, because it may be stuck in an infinite loop.
Breadth-First Search
I’ll play around, meet always new girls, pay attention to girls equally. Also I’mma remind myself of all dates. I’m sure I’ll find the right one, but it’s very exhausting.
TL;DR: I’ll always explore new options.
It is an approach, where a search algorithm explores all the neighboring states of the current state before moving on to the next.
It finds always the correct solution, but has the worst-case time- and space characteristics.
Branch-and-Bound
I’ll still meet new girls, but have some preferences while choosing. Same situation, but at least it is smarter to pick the dates which went well first.
TL;DR: I’ll explore the options too, but exploit the easiest ones.
It is a method that involves using an upper bound on the cost of a solution in order to eliminate some of the branches from the search tree.
It has the same worst case characteristics as Breadth-First Search, but has a better performance in practice.
Heuristical Search
I’ll look for the girls who presumably want to marry the most. I don’t care about the previous dates. If I’m bad at reading the signals, I may not find a partner at all.
TL;DR: I’ll go along my intuition whichever option looks like the best.
It is an approach, where an algorithm uses a heuristic function to guide the search by estimating the cost of the cheapest solution through a state.
It depends on the quality of heuristic function: If it is very inaccurate, same worst case characteristics, additionally no guaranteed solution.
A*-Search
I’ll not only look for the girls whom I’d most likely marry, but also pick the best girls that I know. Future dates are equally as important as previous ones. It’s equally as exhaustive as before, but practically it works well for me. If I don’t overestimate the future with any girl, I’ll eventually arrive at my soulmate. The better I read the signs, the faster I can marry her.
TL;DR: I’ll not forget to weigh my current options when I follow my intuition.
It is a best-first search algorithm that uses a cost function to guide the search.
It performs way better in the best case, if the heuristic function is:
- admissible (never overestimate the cost) and
- consistent (the cost of moving from one state to another is the same in every direction).
Otherwise, it inherits the same worst-case characteristics as Breadth-First Search.
Local Search
The first thing to do is to marry to a girl, no matter what. If I’m married to a girl: I got already someone, and I’m ready to break up with her, if I find a more attractive girl. The good part is, I’ll always have a wife, and I don’t have to keep track of my other dates, and I’m not looking for the perfect girl, I can tolerate some flaws. The bad part is, I’m not gonna have the slightest idea whether she’s my soulmate or not. I might end up always looking out for other girls.
TL;DR: I’ll always find a better one if I try hard for sure, sky is the limit.
It is a method that starts with an initial solution and then iteratively makes small changes to try to find a better solution.
Both completeness and correctness fail, it is very space-efficient but may be very time-consuming.
Simulated Annealing
I marry the first girl who accepts my marriage proposal. In the earlier stages of our marriage, I’ll still reconsider my options, but later if we stick to each other, I’ll tend to stay committed. I’m not looking for the perfect girl, but “perfect enough” to tolerate. I know at least, when to stop searching.
TL;DR: I’ll cool down meanwhile during local search.
It is a method inspired by annealing in metallurgy, a process used to purify metals. The approach slowly reducing “randomness” over time to converge to a best solution.
Both completeness and correctness fail, it is very space-efficient but may be very time-consuming.
Taboo Search
Same strategy as Local Search: I’ll marry first and look for better options. But while dating, I’ll remind myself of dates which went terrible, and block the girls for a while. However I’ll keep my options open, she might turn out to be my soulmate, who knows?
TL;DR: I’ll skip the already visited options for a while, if I don’t have an option, but not forever.
It is an optimization method that uses a set of taboo states that can be temporarily avoided during the search.
Both completeness and correctness fail, it is very space-efficient but may be very time-consuming.
Final Thoughts
These are my technical notes which I wrote down two months ago before an exam, but forgot to share. Those analogies helped me remember the pros and cons of search algorithms as well as some other concepts like redundancy elimination or informed search. So I hope you find it interesting and useful. See you in the next article!
References
[1] Wikipedia, The Free Encyclopedia, s.v. “Search Algorithm” (accessed December 22, 2022), https://en.wikipedia.org/wiki/Search_algorithm
[2] Wikipedia, The Free Encyclopedia, s.v. “Depth-First Search” (accessed December 22, 2022), https://en.wikipedia.org/wiki/Depth-first_search
[3] Wikipedia, The Free Encyclopedia, s.v. “Breadth-First Search” (accessed December 22, 2022), https://en.wikipedia.org/wiki/Breadth-first_search
[4] Wikipedia, The Free Encyclopedia, s.v. “Branch and Bound” (accessed December 22, 2022), https://en.wikipedia.org/wiki/Branch_and_bound
[5] Wikipedia, The Free Encyclopedia, s.v. “Breadth-First Search” (accessed December 22, 2022), https://en.wikipedia.org/wiki/Breadth-first_search
[6] Wikipedia, The Free Encyclopedia, s.v. “Depth-First Search” (accessed December 22, 2022), https://en.wikipedia.org/wiki/Depth-first_search
[7] Wikipedia, The Free Encyclopedia, s.v. “Breadth-First Search” (accessed December 22, 2022), https://en.wikipedia.org/wiki/Breadth-first_search
[8] Wikipedia, The Free Encyclopedia, s.v. “Depth-First Search” (accessed December 22, 2022), https://en.wikipedia.org/wiki/Depth-first_search
[9] Wikipedia, The Free Encyclopedia, s.v. “Breadth-First Search” (accessed December 22, 2022), https://en.wikipedia.org/wiki/Breadth-first_search
