anytimeアルゴリズム (anytime algorithm)

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

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

例:巡回セールスマン問題

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

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

-- しましま

関連項目

リンク集

関連文献


トップ   編集 凍結 差分 履歴 添付 複製 名前変更 リロード   新規 一覧 検索 最終更新   ヘルプ   最終更新のRSS
Last-modified: 2012-02-26 (日) 09:52:51