1
$\begingroup$

If I'm not mistaken, search heuristics rely on problems where the best answer is very close to pretty-good answers. For example, the traveling salesman problem. If there is a route which is the optimal except for a small anomaly somewhere, where the route isn't quite optimal, the algorithms still says that's "pretty good" and continues searching that space until it finds the optimal. I'm going to call this "gradient" because there isn't a sharp difference between optimal and something where everything is optimal except for a small part.

What happens if there is no "gradient"? For example, let's say I wanted to develop some electronic circuitry using a search heuristic. This probably isn't done much, or at all, but bear with me. The optimal circuit would be one which, say, does addition. But, if there is one small difference, like an AND logic gate instead of an OR gate, it doesn't perform at all and produces a terrible result. Now, in traditional search heuristics, it would probably drop this and say "this isn't even close to optimal". It has no way of telling whether something is close to optimal or far away to optimal, because there is really only one circuit that produces good results, and everything else fails miserably.

So what should I do in these situations? By the way, the circuit thing isn't my problem; just a way to demonstrate my issue.

Phrased Differently What does a search heuristic do when it has no way of "grading" how good a given state is, and only the optimal state produces good results? Everything else, no matter how close to the optimal, produces terrible results.

BONUS: What other group of algorithms might perform well in these situations?

$\endgroup$
2
$\begingroup$

Search heuristics will be useless on those kinds of problems. It will effectively degenerate to brute-force search: trying all possibilities in hopes that one of them works. That's very unlikely to find you the solution, except in the smallest possible problems, as its running time is exponential.

What else can you do instead? You'll need to consider other kind of approach: e.g., a SAT solver or ILP solver, an approximation algorithm or any of the other standard methods of dealing with NP-hardness.

$\endgroup$
  • $\begingroup$ Ah, I see. Thanks! +1 for the other options $\endgroup$ – APCoding Apr 2 '16 at 15:30

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.