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.

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

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…