2
$\begingroup$

In practical applications, search algorithms are often strengthened using heuristics. e.g., Deep Blue beat gary kasparov by searching through possible chess moves by "guiding" its search with human-chosen heuristics. These heuristics are not proven to be the optimal heuristics. (they're not optimal obviously).

I am wondering however:

Is there some kind of search problem (ideally a non-trivial one), where (1) there is a specific known algorithm that solves it, and (2) a proof that the algorithm is optimal in the sense that there does not exist an algorithm that solves it faster in expectation, where (3) the probability distribution for that expectation is the relevant one for that practical search problem?

I'm interested in anything related to this. If you know something that seems partially relevant, please say so.

EDIT: Alternatively, please suggest a different notion of "optimality" if you think it is more relevant. I am not sure how relevant my notion of optimality is.

EDIT 2: I'm also interested in how this question relates to the 'No free lunch' theorems in search and optimization.

Improve this question
$\endgroup$
8
  • $\begingroup$ In expectation over what probability distribution? Random instances often have little connection to "real life". $\endgroup$
    – David Richerby
    Nov 16, 2018 at 15:03
  • $\begingroup$ @DavidRicherby, edited? $\endgroup$
    – user95640
    Nov 16, 2018 at 15:12
  • $\begingroup$ Does quicksort count? If not, why? $\endgroup$
    – John L.
    Nov 16, 2018 at 17:14
  • $\begingroup$ @Apass.Jack, I'm not sure I would call quicksort a "search algorithm". Also, I don't know whether quicksort is optimal, or in what sense $\endgroup$
    – user95640
    Nov 16, 2018 at 20:55
  • $\begingroup$ Sorry, I meant to type "binary search". Does binary search count? If not, why? $\endgroup$
    – John L.
    Nov 16, 2018 at 21:38

1 Answer 1

Reset to default
2
$\begingroup$

Finding an optimal solution for a problem is very difficult. for example in sorting you can prove that the optimal solution with comparison is $O(n \log n)$ but may be you can find an algorithm with $O(n)$ without comparison like hashing! another good example is NP Complete problems we even can't prove they haven't polynomial algorithm. so it is very hard to find an optimal solution for deep blue and similar algorithms and proving that the algorithm is optimal is very hard too.

Improve this answer
$\endgroup$

Your Answer

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

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