# 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…