A naive greedy algorithm tries to find an optimal solution based on the best solution so far, hence it may get stuck in local optima.

To avoid this problem, we may keep track of the best $n > 1$ solutions (instead of the best only). What is the name(s) of this algorithm?

Surprisingly, I can't seem to find the answer from Google. It'd be great if you could also list some resources on extensions to the naive greedy algorithm.

  • 1
    $\begingroup$ My sense is that instead of asking for the name of something, it's often better to ask a technical question (e.g., if you had the name, what would you do with it? what question would you want to answer about this approach? then you can ask about that). $\endgroup$ – D.W. Feb 21 '18 at 5:47

You might be interested in beam search, which could be viewed as working in more or less this way.


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.