Brute-force search examines every available candidate or candidate combination, filters results against the constraints, and selects the best valid result. It avoids indexing and pruning, making it straightforward but potentially expensive. section 1.3.2
Packing food for Mars
For a weight-constrained food selection problem, each item can be packed or omitted. Enumerating all combinations, rejecting overweight choices, and taking the highest-value remainder produces a correct brute-force solution. With seven items there are 128 combinations; adding 25 items raises the search to approximately four billion combinations. section 1.3.2 section 1.3.5
In k-means, classification uses brute-force search to compare every point with every centroid and assign the point to its closest centroid. This direct implementation is simple, but the repeated point-centroid comparisons dominate the algorithm’s running time. section 12.2
Use brute-force search when:
- The candidate set is small enough that exhaustive evaluation is practical. section 1.3.2
- You need a direct baseline before replacing it with a more efficient data structure or algorithm. section 12.2.4
- You can tolerate the cost of checking all candidates and value implementation simplicity over scalability. section 1.3.5
Figure 12.7 Running time comparison between classifyPoints implementations using brute-force search (darker line) and k-d tree’s nearest neighbor (lighter). The running times are shown as functions of n, the number of points, for fixed values of k, the number of centroids. (Top left) k==5, the method using k-d tree, is always slower, and its running time grows faster. (Top Right) k == 50, the method using a k-d tree, is still slower, but its growth is similar to the brute-force one. (Bottom Left) k==75, the method using brute force, is initially taking a similar amount of time, but as n grows, the curves for the two running times diverge and k-d tree implementation grows more slowly. (Bottom Right) k==200, the k-d tree implementation, takes half the time of the brute-force approach even for small values of n, and it grows much more slowly.
Compare brute-force classification with k-d-tree nearest-neighbor search as the number of points and centroids changes; the faster approach depends on dataset size and centroid count. section 12.2.4
