5
$\begingroup$

In N queens problem https://en.wikipedia.org/wiki/Eight_queens_puzzle, trying to find solution by backtracking encounters difficulties quite fast (even for SWI-Prolog, http://swish.swi-prolog.org/example/clpfd_queens.pl, which solves N=100 in 0.2 sec, entering N=150 in the link above did not reach a solution in a reasonable amount of time ("time limit exceeded"), and as for ECLiPSe (another Prolog with constraint poropagation) it chokes much, much earlier..).

On the other hand, local search works incredibly well on this problem (https://stackoverflow.com/questions/1863531/n-queens-probiem-how-far-can-we-go, answer by the user chesslover), as the solutions seem to be reachable easily enough by hill climbing (or rather, in this case, hill descending with occasional short range climbing), starting from a random position in the space of possible configurations (each column is occupied by exactly one queen).

Which other well known problems appear to have similar properties (say, a part from examples given in https://en.wikipedia.org/wiki/Local_search_(optimization))?

$\endgroup$
5
$\begingroup$

The following paper

has a thorough comparison of local search vs. backtracking-like algorithm. In the introduction, it even features a question:

"What is the essential difference between local search and backtracking, that sometimes enables local search causes to scale far better than backtracking"

While describing his variation of a hybrid local search + backtracking algorithm, Prestwich tests it on

  • classic $N$ queens problem
  • graph coloring with "real-world applications to timetabling, scheduling, frequency assignment, computer register allocation, printed circuit board testing, and pattern matching"
  • satisfiability (SAT)

All of the above (with possible specialization) can serve as examples for your question.

The other reference that is directly related to a comparison of local search algorithm to backtracking-like is:

which will also talk about the possible reasons for local search to perform better than backtracking.

In general, the possible reasons can be summarized as (Prestwich, 2001):

  • randomness
  • incompleteness
  • scalability
  • different search space
  • ability to follow gradients
  • backtracking's commitment to early variable assignments

The last reference that came to my mind is a nice PhD Thesis

that will feature a couple of other (depends on categorization) applications for local search, where backtracking suffers.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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