AI Glossary / Graphs and symbolic AI / Intermediate
Brute-force search
Definition
Brute-force search solves a problem by systematically generating candidate answers and checking them directly, with little or no problem-specific guidance for avoiding candidates. In a finite search space, exhaustive enumeration can establish whether a solution exists or identify the best candidate under a defined objective. Its main limitation is the amount of work required as the number of possibilities grows.
What it means
The method is deliberately straightforward: make a candidate, test it, and continue. For a small space this can be clear, dependable, and easier to verify than a sophisticated alternative. For a large combinatorial space, the same approach can become impractical even when checking one candidate is fast.
Brute force describes a broad strategy rather than one traversal order. An implementation may enumerate combinations, permutations, or assignments. A search for any valid answer can stop at the first match; a claim that no answer exists normally requires covering the entire relevant space, unless some additional proof justifies stopping earlier.
How it works
First define the candidate space precisely and ensure the generator covers it without omitting legitimate possibilities. Apply a validity test to each candidate. If optimizing, also calculate its objective value and retain the best valid candidate found so far.
At the end of a complete finite enumeration, the retained result is optimal within the specified space and model. If the process is interrupted, it normally establishes only what has been checked so far. Duplicate candidates waste effort, while an incorrect validity test can invalidate the conclusion even if enumeration is complete. Completeness therefore concerns both generation and evaluation.
Three practical examples
- A small configuration tool tries every combination of a few optional features and retains those satisfying compatibility rules.
- A developer uses exhaustive evaluation of tiny instances as a reference when testing a more sophisticated optimization algorithm.
- A planner checks every assignment of a small number of jobs to two teams before choosing the lowest-cost feasible assignment.
Think of it this way
Think of checking every drawer in a small cabinet for a missing key. Finding it permits an early stop; saying it is absent requires checking all relevant drawers properly. The analogy is limited because computational candidates can number in the billions, may overlap, and may be generated from a model that does not include every real-world possibility.
Worked example
Suppose four jobs must each be assigned to team A or team B, with exactly two jobs per team. Before applying that restriction there are 2 to the power 4, or 16, assignments. Six assignments satisfy the two-per-team condition.
Let the job costs for A be 2, 4, 7, and 8, and for B be 6, 5, 3, and 1. Listing the jobs assigned to A, the feasible totals are: {1,2}: 10; {1,3}: 15; {1,4}: 18; {2,3}: 18; {2,4}: 21; and {3,4}: 26. Thus A receives jobs 1 and 2 and B receives jobs 3 and 4 for minimum total cost 10. The result follows from checking all six feasible candidates. Checking only the first three and finding 10 would happen to give the same answer, but would not by itself prove optimality.
Illustrative case study
At fictional Spruce Tools, engineers maintain a simple exhaustive solver for very small assignment problems. They use its results to check a faster production method on selected tiny cases. When the two disagree, they inspect the candidate generator, constraints, and cost calculation on both sides.
They do not deploy the exhaustive version on unrestricted large workloads or call it an infallible reference without checking its implementation. This fictional case shows why a simple method can be valuable for validation even when it is unsuitable as the main operational solver.
Common misconceptions and mistakes
Brute force is not synonymous with random guessing: systematic enumeration can provide a completeness guarantee that random sampling lacks. It also does not always mean checking every candidate before stopping; finding any valid solution may allow early termination.
An interrupted search that finds no solution has not usually proved infeasibility. Likewise, an optimal result is only optimal for the enumerated model. If an assignment option was accidentally excluded, complete enumeration of the wrong space does not fix the omission. Finally, brute force is not necessarily a bad choice: small inputs and strong verification needs can favor simplicity.
Business use
Businesses can use exhaustive search for modest configuration spaces, transparent comparisons, and testing. Before relying on it, estimate how candidate counts grow when another option or item is added. Ten independent binary choices yield 1,024 candidates; twenty yield 1,048,576. These counts do not include the cost of checking each candidate. A sensible operational design states input limits and reports interruption honestly rather than presenting the best result found so far as a proven optimum.
People also ask
Is brute-force search always exponential?
No. Its complexity depends on the candidate space and test. Many combinatorial spaces are exponential or factorial, but the label alone does not determine a formula.
Can it be parallelized?
Often independent candidates can be checked in parallel, though coordination and total work still matter.
Does checking every candidate guarantee correctness?
Only if the candidate space, validity test, objective, and implementation correctly represent the problem.
Check your understanding
A solver checks 900 of 1,000 candidates and finds none valid before timing out. Has it proved that no valid candidate exists?
Answer: No. The remaining 100 may contain a solution unless another sound argument excludes them.
Related terms
- Combinatorial search
- Optimization
- exhaustive search
- enumeration
- search space
- backtracking
- branch and bound
Learn next
Enumerate the six feasible job assignments in the worked example and verify their totals. Then add two more jobs and compare the new candidate count. Use the exercise to separate the effort of generating candidates from the correctness of the test applied to each one.
More in Graphs and symbolic AI
- Branching factor - Branching factor is the number of immediate successor choices available from a node in a search tree. It describes how widely a search can expand at each step.
- Breadth First Search - Breadth First Search, usually written breadth-first search or BFS, explores a graph in layers outward from a starting node.
- Breadth First Search on Edges - Breadth First Search on Edges is a breadth-first graph traversal that reports encountered edges, including edges leading to nodes already discovered.
- Business rules engine - A business rules engine is software that evaluates explicitly defined rules against business data and determines which conclusions or actions apply.
- Capacity Scaling Minimum Cost Flow - Capacity Scaling Minimum Cost Flow is a network-flow method that finds the least-cost way to satisfy specified supplies and demands while respecting edge...
- CART - CART stands for Classification and Regression Trees, a methodology for learning decision trees from labeled data.
Sources
Sources: NIST Dictionary of Algorithms and Data Structures, exhaustive search: https://xlinux.nist.gov/dads/HTML/exhaustiveSearch.html . Russell and Norvig, original search materials: https://aima.eecs.berkeley.edu/slides-pdf/chapter03-6pp.pdf .