Why hill climbing is called anytime algorithm?

Question

From wikipedia, Anytime algorithm

In computer science an anytime algorithm is an algorithm that can return a valid solution to a problem even if it's interrupted at any time before it ends. The algorithm is expected to find better and better solutions the more time it keeps running.

Hill climbing

Hill climbing can often produce a better result than other algorithms when the amount of time available to perform a search is limited, such as with real-time systems. It is an anytime algorithm: it can return a valid solution even if it's interrupted at any time before it ends.

Hill climbing algorithm can stuck into local optima or ridge, after that even if it runs infinite time, the result won't be any better. Then, why hill climbing is called anytime algorithm?

Answer 1

At the start of hill climbing, you already have a solution, therefore it can return a valid solution even if interrupted, fulfilling one part of the anytime requirements.

Hill climbing also normally produces better results the more the algorithm runs, although the time taken to find a better solution can approach infinity if the algorithm gets stuck. However, the definition for an anytime algorithm says that it is expected to produce better results, and we expect hill climb algorithms to produce better results, although sometimes they don't.

So an anytime algorithm:

• Requires: A valid solution to be available even if the algorithm is interrupted before completion.
• Expects: Improvements in solution as time goes on.

Hill climbing fulfills both the requirement and the expectation, so it can be described as an anytime algorithm.

Answer 2

The answer to your question is hidden in the quoted piece of text:

it can return a valid solution even if it's interrupted at any time before it ends.

The important part is in the definition of valid in this context - that it satisfies all the constrains and is better or at least not worse than what you already had.

These algorithms are not called Anytime because improvement of its result is guaranteed to be a monotonously rising function. They are called so, because you can get a usable (valid, consistent, good enough...) result whenever you stop them. This even means that you can ask for a so far best result at any time, use it in your business and let the algorithm continue improving it even more (or not).