Posts Tagged ‘Brute-force’

PostHeaderIcon 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.


Breadth-First Search

Uniform-Cost Search

Depth-First Search

Depth-First Iterative-Deepening Search

Bidirectional Search

Combinatorial Explosion

AI Search Techniques

PostHeaderIcon 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 105 states is easily solved by brute-force search, the fifteen-puzzle contains over 1013 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 1025 states.