Loading article…
コンピュータサイエンスにおいて、いつでもアルゴリズムとは、終了する前に中断された場合でも、問題に対する有効な解決策を返すことができるアルゴリズムです。アルゴリズムは、実行を続けるほど、より良い解決策を見つけることができると期待されています。
ほとんどのアルゴリズムは完了するまで実行されます。つまり、一定量の計算を実行した後、単一の回答が返されます。ただし、場合によっては、完了前にアルゴリズムを終了したい場合があります。たとえば、必要な計算量が非常に多い場合は、計算リソースを再割り当てする必要があります。ほとんどのアルゴリズムは完了するまで実行されるか、または有用なソリューション情報を提供しません。ただし、いつでも実行できるアルゴリズムは部分的な回答を返すことができ、その品質は実行できた計算量によって異なります。いつでも実行できるアルゴリズムによって生成される回答は、正解の近似値です。
名前
いつでもアルゴリズムは「割り込み可能なアルゴリズム」とも呼ばれます。これは、事前に時間を宣言する必要がある契約アルゴリズムとは異なります。いつでもアルゴリズムでは、プロセスは終了することを通知するだけで済みます。[1]
目標
いつでもアルゴリズムの目標は、インテリジェント システムに、ターンアラウンド タイムと引き換えに、より高品質の結果を出す能力を与えることです。[2]また、時間とリソースの柔軟性も求められます。[3]人工知能または AI アルゴリズムは結果を出すのに長い時間がかかることがあるため、これらは重要です。このアルゴリズムは、より短い時間で完了するように設計されています。[3]また、これらは、システムがエージェントに依存し、制限されていること、およびエージェントがどのように協力して動作するかをよりよく理解することを目的としています。[3]一例として、数値の平方根を求めるために適用されるニュートン - ラプソン反復法が挙げられます。 [4]いつでもアルゴリズムを使用するもう 1 つの例は、ターゲットを狙うときの軌道問題です。オブジェクトは、アルゴリズムが終了するのを待っている間に空間を移動しており、近似値の答えでも、早く与えられれば精度を大幅に向上させることができます。[3]
いつでもアルゴリズムがユニークなのは、与えられた入力に対して多くの可能な結果を返すことができる点です。 [ 2]いつでもアルゴリズムは、問題解決と分散コンピューティングリソースの進捗状況を監視するために、明確に定義された多くの品質尺度を使用します。[2]与えられた時間内で可能な限り最良の答えを探し続けます。[5]完了するまで実行されない場合があり、より長く実行できれば答えが改善される可能性があります。[6] これは、大規模な決定セットの問題によく使用されます。[7]通常、終了しない限り有用な情報は提供されません。[8]これは動的計画法に似ているように聞こえるかもしれませんが、違いは、順次ではなくランダムな調整によって微調整されることです。
いつでもアルゴリズムは、いつでも停止するように指示でき、その時点で見つかった最良の結果を返すように設計されています。[3]このため、割り込み可能なアルゴリズムと呼ばれます。また、特定のいつでもアルゴリズムは最後の結果も保持するため、より多くの時間が与えられた場合、中断したところから続行してさらに良い結果を得ることができます。[3]
決定木
決定者が行動しなければならないとき、何らかの曖昧さがなければなりません。また、この曖昧さを解決する方法についての何らかのアイデアがなければなりません。このアイデアは、状態から行動へのダイアグラムに変換可能でなければなりません。[7]
パフォーマンスプロファイル
パフォーマンス プロファイルは、入力とアルゴリズムに割り当てられた時間に基づいて、結果の品質を推定します。[3]推定が優れているほど、結果が早く見つかります。[3]一部のシステムには、出力が期待される出力である確率を示す大規模なデータベースがあります。[3] 1 つのアルゴリズムに複数のパフォーマンス プロファイルがある場合があることに注意することが重要です。[9]ほとんどの場合、パフォーマンス プロファイルは、代表的なケースを使用して数理統計を使用して構築されます。たとえば、巡回セールスマン問題では、パフォーマンス プロファイルは、必要な統計を生成するためにユーザー定義の特別なプログラムを使用して生成されました。[1]この例では、パフォーマンス プロファイルは、時間と期待される結果のマッピングです。[1]この品質は、いくつかの方法で測定できます。
- 確実性：正確さの確率が品質を決定する[1]
- 精度：誤差の限界が品質を決定する[1]
- 特異性：細部の量によって品質が決まる[1]
アルゴリズムの前提条件
初期動作：アルゴリズムの中には即座に推測を開始するものもありますが、他のアルゴリズムはより計算されたアプローチを採用し、推測を行う前に起動期間を設けます。[9]
- 成長方向: プログラムの「出力」または結果の品質が、時間の量（「実行時間」）の関数としてどのように変化するか[9]
- 成長率: 各ステップでの増加量。バブルソートのように常に変化するか、それとも予測できないほど変化するか?
- 終了条件: 必要な実行時間の量[9]
参考文献
- ^ abcdef Hendler, James A. 編 (2014) [1992]. 人工知能計画システム: 第 1 回会議 (AIPS 92) の議事録. Elsevier. ISBN 978-0-08-049944-4。
- ^ abc ジルバーシュタイン 1996
- ^ abcdefghi Grass, J. (1996). 「計算リソース割り当てに関する推論。XRDS: Crossroads」ACM Magazine for Students . 3 (1): 16–20. doi : 10.1145/332148.332154 . S2CID 45448244.
- ^ いつでもアルゴリズム、Free Online Dictionary of Computing (FOLDOC) より
- ^ 「Anytime algorithms」。認知アーキテクチャ。ミシガン大学人工知能研究所。2013年12月13日時点のオリジナルよりアーカイブ。
- ^ 「Anytime アルゴリズム - コンピューティングリファレンス」。eLook.org。2013年 12 月 12 日時点のオリジナルよりアーカイブ。
- ^ Horsch & Poole 1998より
- ^ ベンダー、エドワード A. (1996)。人工知能における数学的手法。ワイリー。ISBN 978-0-8186-7200-2。
- ^ abcd Teije, AT; van Harmelen, F. (2000). 「いつでもパフォーマンス プロファイルを使用して問題解決方法を説明する」(PDF)。第 14 回ヨーロッパ人工知能会議の議事録。pp. 181–5。
さらに読む
- Boddy, M.; Dean, T. (1989) 「時間依存の計画問題の解決」第 11 回国際人工知能合同会議議事録第 2 巻 979 ～ 984 ページ ブラウン大学 CS-89-03。
- Grass, J.; Zilberstein, S. (1996). 「Anytime アルゴリズム開発ツール」. ACM SIGART Bulletin . 7 (2 Anytime アルゴリズムと審議スケジュールに関する特別号): 20–27. doi :10.1145/242587.242592. S2CID 7670055.
- Horsch, MC; Poole , D. (1998) 「不確実性下での意思決定のためのいつでも実行可能なアルゴリズム」(PDF)。人工知能における不確実性に関する第 14 回会議の議事録。pp. 246–255。arXiv : 1301.7384。ISBN 978-1-55860-555-8。
- Horvitz, EJ (1986 年 3 月)。限られたリソースの世界における推論のトレードオフに関する推論(技術レポート)。スタンフォード大学、医療情報科学セクション、医療コンピュータ サイエンス グループ。KSL-86-55。
- Wallace, R.; Freuder, E. (1995). 「制約充足と SAT 問題のためのいつでも実行可能なアルゴリズム」ACM SIGART 速報. 7 (2): 7–10. doi : 10.1145/242587.242589 . S2CID 8250394.
- Zilberstein, S. (1993)。「いつでも実行可能なアルゴリズムのコンパイルによる操作合理性」(PhD)。カリフォルニア大学バークレー校、コンピュータサイエンス部門。UMX GAX94-08166。
- Zilberstein, Shlomo (1996). 「インテリジェントシステムにおける Anytime アルゴリズムの使用」(PDF) . AI Magazine . 17 (3): 73–83.