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