anytimeアルゴリズム

anytimeアルゴリズム (anytime algorithm)†

任意の時刻で停止でき，その時点でのある程度の品質の解を出力でき，その後再開することもできるようなアルゴリズムの総称．次ような性質を持つことが望ましい：

measurable quality：近似結果の真の解との差が計測可能
recognizable quality：実行時に，定数時間で品質を決定可能
monotonicity：品質が，時間と入力の質に対して非減少であること．品質が recognizable なら，今までの最良の結果を返すことで，monotonicity を満たすことができる．
consistency：結果の品質が，計算時間と入力の品質と相関がある
diminishing returns：解の改善の度合いは，初期は大きいが，あとになるほど小さくなる
interruptibility：任意の時刻で停止しても，何らかの解が得られる．ただし，contractアルゴリズムという事前に決めた時点以外では中断不可能なものもある．
preemptability：アルゴリズムは一時停止可能で，最小のオーバヘッドで再開可能

実行時間を入力として，解の品質の度合いを出力する関数を performance profile という．解の品質の度合いとは，正確な解が出力される確実性，最適解に対する近似の良さ，解の詳細さのレベルなどである．performance profile は理論的に求めたり，シミュレーションで求めたりする．

↑

例：巡回セールスマン問題†

初期的な巡回路を適当に選ぶ．その後，ランダムに一部の経路を変更し，もし経路長が変更前より短ければ，変更後の経路を新しい解とする．

このアルゴリズムを一時停止した場合に，現在の解は，最適ではないがある程度の品質の解となっている．アルゴリズムを再開することも容易．解の質である経路長は非減少であり，解の改善の度合いは，改善の度合いは初期は大きく，後になるほど小さくなる．いろいろな入力に対するシミュレーションにより performance profile は求めることができる．