### Exhaustive Enumeration

##### Description

Exhaustive Enumeration is a method for finite search spaces

It enumerates all possible solutions.

It will definitely find the global optimum $x$.

Usually it has exponential complexity: the number of possible solutions usually rises exponentially with input size

If lower bound $y$ for objective values is known, we can maybe stop earlier: If an element $x$ with $f(x) = y$ is discovered, it is the global optimum and we can stop

In general, however, this method is not feasible because it takes too long

##### Definitions

$$f \gets \text{the objective/fitness function}$$ $$y \gets \text{the lowest possible objective value, −∞ if unknown}$$ $$x \gets \text{the current candidate solution}$$ $$\textit{Best} \gets \text{the best individual ever discovered}$$

##### References

Thomas Weise - Metaheuristic Optimization

##### Pseudo Code
\begin{algorithm}
\caption{EE Algorithm}
\begin{algorithmic}
\STATE $\textit{Best} \gets Null$
\WHILE{not all solutions checked or $f(\textit{Best})>y$}
\STATE $x \gets \text{next candidate solution}$
\IF{$f(\textit{Best}) > f(x)$ or $\textit{Best} == Null$}
\STATE $\textit{Best} \gets x$
\ENDIF
\ENDWHILE
\RETURN $\textit{Best}$
\end{algorithmic}
\end{algorithm}