Loading article…
競合分析は、オンライン アルゴリズムを分析するために考案された手法であり、オンライン アルゴリズム (予測不可能な一連の要求を満たし、各要求を将来を見ずに完了する必要がある) のパフォーマンスを、一連の要求を事前に確認できる最適なオフライン アルゴリズムのパフォーマンスと比較します。競合比率(パフォーマンスとオフライン アルゴリズムのパフォーマンスの比率) が制限されている場合、アルゴリズムは競合的です。アルゴリズムのパフォーマンスが「難しい」入力に対してのみ測定される従来の最悪ケース分析とは異なり、競合分析では、アルゴリズムが困難な入力と簡単な入力の両方で適切に機能する必要があります。ここで、「難しい」と「簡単」は、最適なオフライン アルゴリズムのパフォーマンスによって定義されます。
多くのアルゴリズムでは、パフォーマンスは入力のサイズだけでなく、その値にも依存します。たとえば、要素の配列をソートする場合、最初の順序によって難易度が変わります。このようなデータ依存アルゴリズムは、平均ケースと最悪ケースのデータに対して分析されます。競合分析は、通常データに依存するオンライン アルゴリズムとランダム化アルゴリズムに対して最悪ケース分析を行う方法です。
競合分析では、研究対象のアルゴリズムと何らかの最適アルゴリズムのコストの比率を最大化するために、意図的に難しいデータを選択する「敵」を想像します。ランダム化されたアルゴリズムを検討する場合、さらに、対戦するアルゴリズムによって行われたランダムな選択について何も知らない無意識の敵と、実行中の任意の時点でのアルゴリズムの内部状態を完全に知っている適応的な敵を区別する必要があります。(決定論的アルゴリズムの場合、違いはありません。どちらの敵も、将来の任意の時点でそのアルゴリズムがどのような状態になる必要があるかを計算し、それに応じて難しいデータを選択できます。)
たとえば、クイックソートアルゴリズムは、平均してソートするデータの中心値からそれほど離れていない「ピボット」と呼ばれる 1 つの要素を選択します。次に、クイックソートはデータを 2 つの山に分けます。1 つはピボットの値より小さい値を持つすべての要素を含み、もう 1 つは残りの要素を含みます。クイックソートが何らかの決定論的な方法でピボットを選択した場合 (たとえば、常にリストの最初の要素を選択する)、攻撃者はクイックソートが最悪のケース時間で実行されるように事前にデータを配置することが容易です。ただし、クイックソートがピボットとしてランダムな要素を選択した場合、どのような乱数が出てくるかを知らない攻撃者は、クイックソートの最悪のケースの実行時間を保証するようにデータを配置することはできません。
競合分析 (Sleator & Tarjan 1985) で最初に分析された古典的なオンライン問題は、リスト更新問題です。項目のリストとさまざまな項目の要求のシーケンスが与えられた場合、リストの先頭に近い要素ほどアクセス コストが低くなるように、リストへのアクセス コストを最小化します (通常、項目へのアクセス コストは、リスト内の位置と同じです)。アクセス後、リストが並べ替えられる場合があります。ほとんどの並べ替えにはコストがかかります。Move -To-Front アルゴリズムは、アクセス後に要求された項目をコストなしで先頭に移動するだけです。Transposeアルゴリズムは、アクセスされた項目をその直前の項目とコストなしで交換します。古典的な分析方法では、特定のコンテキストでは Transpose が最適であることが示されました。実際には、Move-To-Front の方がはるかに優れたパフォーマンスを発揮しました。競合分析により、攻撃者は Transpose のパフォーマンスを最適なアルゴリズムに比べて任意に低下させることができる一方で、Move-To-Front では最適なアルゴリズムの 2 倍以上のコストが発生することは決してないことが示されました。
サーバーからのオンライン リクエストの場合、競合アルゴリズムは将来に関する不確実性を克服するために使用されます。つまり、アルゴリズムは将来を「知りません」が、仮想の敵 (「競合相手」) は「知っています」。同様に、競合アルゴリズムは分散システム用に開発されました。分散システムでは、アルゴリズムは、リモート ロケーションで何が起こったかを「知らずに」、あるロケーションに到着したリクエストに反応する必要があります。この設定は、(Awerbuch、Kutten、Peleg 1992) で紹介されました。
参照
参考文献
- Sleator, D. ; Tarjan, R. (1985)、「リスト更新とページングルールの償却効率」、Communications of the ACM、28 (2): 202–208、doi : 10.1145/2786.2793。
- Aspnes, James (1998)、「分散アルゴリズムの競合分析」、Fiat, A. ; Woeginger, GJ (編)、オンライン アルゴリズム: 最新技術、Lecture Notes in Computer Science、vol. 1442、pp. 118–146、doi :10.1007/BFb0029567、ISBN 978-3-540-64917-5。
- ボロディン、A. ; エル・ヤニブ、R. (1998)、オンライン計算と競合分析、ケンブリッジ大学出版局、ISBN 0-521-56392-5。
- Awerbuch, B.; Kutten, S .; Peleg, D. (1992)、「競合的分散ジョブ スケジューリング」、ACM STOC、ビクトリア、ブリティッシュ コロンビア州、カナダ。