liveBook · Manning

Brute-force search

As explained in Algorithms Every Programmer Should Know

Brute force is a problem-solving technique that straightforwardly examines possible solutions without applying problem-specific optimization.

Brute-force search checks possible solutions directly, without first optimizing the approach. It can provide a starting solution to compare with a more efficient one. section 1.2.1

Matching workers to tasks

For three workers and three tasks, check all six possible pairings, calculate each pairing’s cost, and keep the cheapest. At 100 workers and routes, the number of pairings is 100!, making exhaustive checking impractical. section 3.1

For large assignment problems, the Hungarian algorithm offers a more efficient alternative to checking every pairing. section 3.1

How Algorithms Every Programmer Should Know covers it

How deep it goes
Explains exhaustive assignment checking through permutations and contrasts its growth with the Hungarian algorithm.
Examples
Uses worker-task matching to compare six pairings for three workers with 100! possibilities for 100.
What you can do after
Evaluate when exhaustive matching becomes impractical and why a more efficient algorithm is useful.
How it connects
Connects brute-force search to algorithms, optimization, the assignment problem, and the Hungarian algorithm.

Also explained in

Compare how 8 books explain brute-force search →

Related concepts

This explainer was generated by Manning's knowledge graph from the text of Algorithms Every Programmer Should Know. The section links point to the parts of the book it draws on.