Anytime algorithm とは

コンピュータサイエンスでは、任意のアルゴリズムは、終了する前に中断されても有効な解を問題に戻すことができるアルゴリズムです。このアルゴリズムは、実行時間を長くするほど、より良い、より良い解決策を見つけることが期待されています。
大部分のアルゴリズムは完了まで実行されます。一定量の計算を実行した後で1つの答えが得られます。しかしながら、場合によっては、ユーザは完了前にアルゴリズムを終了させたいかもしれない。例えば、必要とされる計算量は相当なものであり、計算資源を再割当てする必要があるかもしれない。ほとんどのアルゴリズムは完了まで実行されるか、有用なソリューション情報を提供しません。しかし、いつでもアルゴリズムは部分的な回答を返すことができ、その質は実行可能な計算量に依存します。いつでもアルゴリズムによって生成される答えは、正解の近似値です。