Loading article…
コンピュータサイエンスにおいて、オンラインアルゴリズム[1]とは、最初から入力全体が利用可能でなくても、 入力がアルゴリズムに入力された順序で、入力を少しずつシリアルに処理できるアルゴリズムのことである。
対照的に、オフライン アルゴリズムでは、問題データ全体が最初から与えられ、手元の問題を解決する答えを出力することが求められます。オペレーションズ リサーチでは、オンライン アルゴリズムが開発される領域はオンライン最適化と呼ばれます。
例として、ソートアルゴリズムの 選択ソートと挿入ソートを考えてみましょう。選択ソートは、ソートされていない残りの部分から最小の要素を繰り返し選択して先頭に配置します。これには入力全体へのアクセスが必要です。したがって、これはオフライン アルゴリズムです。一方、挿入ソートは、反復ごとに 1 つの入力要素を考慮し、将来の要素を考慮せずに部分的なソリューションを生成します。したがって、挿入ソートはオンライン アルゴリズムです。
挿入ソートの最終結果は最適、つまり正しくソートされたリストであることに注意してください。多くの問題では、オンラインアルゴリズムはオフラインアルゴリズムのパフォーマンスに匹敵することはできません。オンラインアルゴリズムと最適なオフラインアルゴリズムのパフォーマンスの比率が制限されている場合、オンラインアルゴリズムは競争力があると呼ばれます。[1]
すべてのオフライン アルゴリズムに、効率的なオンライン対応アルゴリズムがあるわけではありません。
文法理論では、これらは直線文法に関連付けられています。
意味
オンライン アルゴリズムは入力全体を把握していないため、後になって最適ではないことが判明する可能性のある決定を強いられます。オンライン アルゴリズムの研究は、この設定で可能な意思決定の質に焦点が当てられてきました。競合分析では、同じ問題インスタンスに対するオンライン アルゴリズムとオフライン アルゴリズムの相対的なパフォーマンスを比較することで、この考え方を形式化します。具体的には、アルゴリズムの競合比率は、考えられるすべての入力に対するそのコストの最悪ケース比率を最適コストで割ったものとして定義されます。オンライン問題の競合比率は、オンライン アルゴリズムによって達成される最高の競合比率です。直感的には、アルゴリズムの競合比率はこのアルゴリズムによって生成されるソリューションの品質の尺度を示し、問題の競合比率は、この問題の将来を知ることの重要性を示します。
その他の解釈
アルゴリズムへのオンライン入力に関する他の観点については、以下を参照してください。
- ストリーミング アルゴリズム: 過去の入力を正確に表現するために必要なメモリの量に重点を置きます。
- 動的アルゴリズム: オンライン入力による問題に対するソリューションを維持する時間の複雑さに焦点を当てます。
例
いくつかのオンラインアルゴリズム:
- 挿入ソート
- パーセプトロン
- 貯留層サンプリング
- 貪欲アルゴリズム
- 敵対者モデル
- メトリックタスクシステム
- オッズアルゴリズム
- ページ置換アルゴリズム
- 分散を計算するアルゴリズム
- ウッコネンのアルゴリズム
オンラインの問題
オンライン アルゴリズムの概念を例示する問題として、カナダ旅行者問題があります。この問題の目的は、一部のエッジが信頼できず、グラフから削除されている可能性のある重み付きグラフで、ターゲットに到達するコストを最小化することです。ただし、エッジが削除された (失敗) ことは、旅行者がエッジのエンドポイントの 1 つに到達したときにのみ明らかになります。この問題の最悪のケースは、信頼性のないエッジがすべて失敗することであり、問題は通常の最短経路問題に帰着します。競合分析の助けを借りて、この問題の別の分析を行うことができます。この分析方法では、オフライン アルゴリズムはどのエッジが失敗するかを事前に知っており、目標はオンライン アルゴリズムとオフライン アルゴリズムのパフォーマンスの比率を最小化することです。この問題はPSPACE 完全です。
解決策として複数のオンライン アルゴリズムを提供する形式的な問題は数多くあります。
参照
参考文献
- ^ ab Karp, Richard M. (1992). 「オンラインアルゴリズムとオフラインアルゴリズム: 未来を知ることはどれほど価値があるか?」(PDF) . IFIP Congress (1) . 12 : 416–429 . 2015年8月17日閲覧。
- ^ Dochow, Robert (2016). ポートフォリオ選択問題のためのオンラインアルゴリズム。Springer Gabler。
外部リンク
- オンラインアルゴリズムに関する論文の参考文献