Enumeration

Enumeration is a very simple search algorithm that just puts every solution in some (total) order, checks the first one, then the second, then the third, and so on until it finds a solution with a good enough fitness.

In this example, the fitness of a particular location is shown by how light the grey colour is. This is randomly generated when the page loads (if the square looks black, try reloading the page).

Each (x, y) point in the square is a solution, and our goal is to find the best (lightest). To enumerate 2D points we need to interleave the x and y values somehow. There are a few different ways we could do it, but in this case we use the following algorithm:

denominator := 2
x_numerator := 1
y_numerator := 1
loop forever:
    try_solution((x_numerator / denominator, y_numerator / denominator))
    y_numerator := y_numerator + 2
    if y_numerator > denominator:
        y_numerator := 1
        x_numerator := x_numerator + 2
    if x_numerator > denominator:
        x_numerator := 1
        denominator := denominator * 2
end loop

This basically takes all of the odd coordinates, like (1, 1), (1, 3), (3, 1), etc. and divides them by increasing powers of 2 (2, 4, 8, 16, etc.). This ensures we never hit the same point twice, and we will eventually get arbitrarily-close to every point in the space.

Fittest so far: -1

Clicking the square above will start the search.

Whilst enumeration is a very simple search algorithm, its results can be pretty poor; especially when we have many dimensions. It requires some prior knowledge of the search space in order to choose a reasonable enumeration order, otherwise the best solutions may take so long to find that it’s not worth using ;)