7
$\begingroup$

I don't know how to state it elegantly, but basically, I want to implement a brute force search algorithm, but there are many different ways that I could enumerate through the search space. This might be naive of me, but I imagine that how I choose to enumerate through the search space could greatly affect whether or not my algorithm works well in practice.

Consider the following decision problem as a simplified example.

Input: A polynomial $p(x)$ with integer coefficients and a natural number $k$.

Question: Does there exist $i \in [k]$ such that $p(i) = 0$?

Now, there could be many different algorithms for solving this problem, but I decide to choose a brute force approach. Consider the following strategies for enumerating through the search space.

Ascending Strategy: I could check if $p(1)$ is 0, then $p(2)$, then $p(3)$, ..., until I find an $i$ such that $p(i) = 0$ or I try every $i \in [k]$.

Descending Strategy: I could check if $p(k)$ is 0, then $p(k-1)$, then $p(k-2)$, ..., until I find an $i$ such that $p(i) = 0$ or I try every $i \in [k]$.

Popularity Strategy: I could store a small list $L$ of most popular solutions and try those first before trying the numbers in $[k] - L$.

Sieve Strategy: I could do a sort of sieve enumeration. I try all numbers divisible by 2 in $[k]$, then numbers divisible by 3 in $[k]$, then 5, then 7, then 11, then 13, and so on. (Assuming that I have access to some large pre-computed list of primes.)

Randomness Strategy: Maybe there is an interesting enumeration strategy that utilizes a large string of random bits.

Basically, I'm looking to answer the following questions about brute force search algorithms:

Question A: Are there any benefits to choosing a specific enumeration strategy?

Question B: Are there any examples of search problems where in practice you would choose an interesting enumeration strategy? I feel like there may be some search problems where in practice a variant of the Popularity Strategy works effectively.

Improve this question
$\endgroup$
5
  • 3
    $\begingroup$ Do you mean "brute force" in the strict sense of trying every possible input, using no information gained from one input to choose future inputs ? This particular definition of brute force is relevant because it is trivially parallelized, yet it's compatible with all your suggested strategies. OTOH, Juho's answer talks about "pruning the search space" which excludes multiple inputs based on the information gained from just one input. $\endgroup$
    – MSalters
    Commented Oct 14, 2015 at 9:38
  • 1
    $\begingroup$ A tidbit - I've calculated optimal rocket staging for Kerbal Space Program a few times with an alpha/beta/heuristic search (basically directed brute force that prunes search trees that cannot be the best answer), and manual tweaking of priorities can make it orders of magnitude faster. In particular, occasionally expanding a node with a good heuristic as opposed to best alpha seems to help significantly, as there's no inexpensive but good way to calculate alpha that I've found. So the answer is yes to question A. $\endgroup$
    – TLW
    Commented Oct 14, 2015 at 11:39
  • 1
    $\begingroup$ @MSalters You made a good point with your comment. I called it brute force search because if there is no solution then you would still try each element of the search space (little to no pruning). However, you may use previous knowledge that you've gained to intelligently determine the order in which you enumerate through the search space. Also, as you mentioned, by changing the enumeration order you could make parallelization more difficult. $\endgroup$
    – Michael Wehar
    Commented Oct 14, 2015 at 16:42
  • 1
    $\begingroup$ For your specific example, you've got sum and product of roots that can make simplify the search. $\endgroup$
    – Mark Hurd
    Commented Oct 16, 2015 at 7:23
  • $\begingroup$ This post discusses the complexity of brute force search: cstheory.stackexchange.com/questions/14404/… $\endgroup$
    – Michael Wehar
    Commented Oct 20, 2015 at 8:11

2 Answers 2

Reset to default
5
$\begingroup$

The answer to both of your questions is yes! Definitely, even though in the worst-case you will have to enumerate the whole search space with brute-force (to prove there is no solution), it absolutely makes sense to consider how you traverse the search space. In general, you will find a lot of literature and discussion on the topic from the field of AI, and in particular e.g. SAT/CSP solving. A quick and gentle introduction is given by the Russell and Norving book.

I like using the Sudoku puzzle as an example. To decide whether a partially filled puzzle has a solution, you can exhaustively check every possible way of completing it. The naive approach is a blind backtracking search. This is extremely wasteful. A better idea is this: for the next cell to assign to, always pick the one with the fewest legal values. In general, this is a "fail-first heuristic", and the intuition is that this choice is most likely to fail soon, and it thereby prunes the search tree aggressively. There is actually a known "wisdom" in the field: "to succeed, you must fail quickly". Roughly, the sooner you fail, the faster you get to concentrate your effort on the hard part of the problem.

It might seem like the above is very problem specific, and only applies to say Sudoku puzzles. Fortunately, this is not the case. It is quite helpful to model your problem, or try to you see your problem, as e.g. a SAT/CSP instance. Then you can immediately apply known tricks to speedup your brute-force, devise better heuristics, and so on. Of course, you might do several magnitudes better by using a good CSP/SAT-solver instead of brute-force. This is beneficial even if nothing considerably better than brute-force is known for your problem. This is due to the fact that instances tend to have structure that is exploitable by smart solvers, and it is difficult to detect the same structure yourself with e.g. brute force.

An older answer of mine gives a bit more concreteness. I think every strategy you mention has been experimented with, most notably randomness. For instance, random restart strategies are very powerful, and are in use in modern solvers.

Improve this answer
$\endgroup$
0
3
$\begingroup$

Brute forcing can indeed be somewhat improved by heuristics, based on some knowledge of the problem at hand.

There is no universal strategy that can work anywhere, especially if it is a blind one (independent of the history of outcomes for different trials). Moreover, there are probably problems elusive of any strategy.

An example of a heuristic strategy is simulated annealing, where you assume that the better solutions you find, the closer you are to the optimum. Such a property may not hold at all for other questions.

Question A: no, there is no general strategy to be applied blindly.

Improve this answer
$\endgroup$
1
  • $\begingroup$ @Juho: ok, I am discarding B, as the OP is asking for exceptions to the rule. $\endgroup$
    – user16034
    Commented Oct 14, 2015 at 7:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.