## Posts Tagged ‘Brute-force’

## Brute Force Search

### Brute-Force Approach

The most general search algorithms are brute-force searches since they do not require any domain specific knowledge. All that is required for a brute-force search is a state description, a set of legal operators, an initial state, and a descriptions of the goal state. So brute-force search is also called uninformed search and blind search.

**Brute-force search** should proceed in a systematic way by exploring nodes in some predetermined order or simply by selecting nodes at random. Search programs either return only a solution value when a goal is found or record and return the solution path. The most important brute-force techniques are as below.

## Combinatorial Explosion

# What is Combinatorial Explosion?

The problem with all brute-force search algorithms is that their time complexities grow exponentially with problem size. This problem is called combinatorial explosion.

The **combinatorial explosion** results in limited size of problems that can be solved with with brute-force search techniques. For example while eight-puzzle with 10^{5} states is easily solved by brute-force search, the fifteen-puzzle contains over 10^{13} states, and hence cannot be solved with brute-force techniques on current machines. Even faster machines cannot have significant impact on this problem since the 5 * 5 twenty-four puzzle contains almost 10^{25} states.