Search Algorithms In a Nutshell

What could be better than funny analogies to help us understand a concept?

Yamac Eren Ay
8 min readFeb 22, 2023

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.

Source: https://medium.com/introduction-to-knowlegde-representation/propositional-logic-and-sat-problems-c0a3edac6a26

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).”

Source: https://www.researchgate.net/figure/The-initial-and-goal-states-for-Example-1_fig2_258240612

Problem Statement

--

--