人生においては、必要な情報がすべて揃っていない状態で意思決定をしなければならないことがあります。 それはコンピューターサイエンスにも当てはまります。 これはオンライン アルゴリズムの領域です。その名前にもかかわらず、必ずしもインターネットが関与しているわけではありません。 代わりに、これらは、次に何が起こるかをまったく知らずに、データが到着するたびに対応する問題解決戦略です。 これらのアルゴリズムは不確実性に対処できるため、ラップトップのメモリ管理や Web 閲覧者に表示する広告の選択など、現実世界の難問に役立ちます。

研究者は、これらの問題に取り組むための新しい方法を調査するために、これらの問題の一般化されたバージョンを研究します。 中でも有名なのが「k-サーバーの問題」では、次々に届くリクエストに対応するために多数のエージェントを派遣するという厄介なタスクについて説明しています。 彼らは修理技術者や消防士、あるいは放浪のアイスクリーム販売員である可能性もあります。

「この問題を定義するのはとても簡単です」と彼は言った マルシン・ビエンコフスキ、ポーランドのヴロツワフ大学のアルゴリズム研究者。 しかし、それは「異様に難しいことが判明した」。 研究者が攻撃を開始して以来、 k1980 年代後半のサーバー問題では、オンライン アルゴリズムがどの程度うまくこのタスクを処理できるかについて疑問を抱いていました。

数十年にわたり、研究者たちは、常に一定レベルのアルゴリズム パフォーマンスを達成できると信じ始めました。 k-サーバーの問題。 したがって、扱っている問題のバージョンに関係なく、この目標を達成するアルゴリズムが存在します。 しかし、昨年 XNUMX 月に初めてオンラインで公開された論文の中で、XNUMX 人のコンピューター科学者は次のように述べています。 示されました これは常に達成できるわけではないということ。 場合によっては、どのアルゴリズムも不十分であることがあります。

「私にとって大きな驚きだったと言えてうれしいです」と語った。 アヌパムグプタ同氏はカーネギーメロン大学でアルゴリズムを研究しているが、この論文には関与していない。 この研究は「この分野の中心的な問題についてのより深い洞察」を提供します。

まずはコンピュータ科学者 この問題の概要を説明しました それを理解するために、配管工を雇用している会社を想像してみましょう。 電話が入ると、会社はどの配管工がどの場所に行くかを決定する必要があります。 会社の目標と、そのアルゴリズムの目標 k-サーバーの問題 — すべての配管工が移動する総距離を最小限に抑えることです。

難しいのは、電話がどこからかかってくるかが会社には事前に分からないことです。 もしそうなら、未来を知る「オフラインアルゴリズム」に依存する可能性がある。 特に、任意の呼び出し文字列に対して総移動量が最小のソリューションを見つける理想的なディスパッチング戦略を使用できます。 どのオンライン アルゴリズムもこれに勝るものはなく、確実に一致することさえありません。

しかし研究者たちは、できる限りそれに近づけたいと考えています。 各戦略の移動距離を比較することでオンライン アルゴリズムのパフォーマンスを測定し、いわゆる競争率を計算します。 アルゴリズム設計者は、この比率を 1 に近づけて、オフラインの理想に近づくオンライン戦略を作成しようとします。

私たちの配管会社には配管工が XNUMX 人しかおらず、XNUMX 本の長い通りだけを担当していると想像してみましょう。 電話は一度に XNUMX 件ずつかかってきます。 貪欲アルゴリズムとして知られる合理的な最初のアプローチは、すべての着信通話の場所に最も近い配管工を派遣することです。 しかし、このアルゴリズムが難しいシナリオは次のとおりです。XNUMX 人の配管工が通りの西端で作業を開始し、もう XNUMX 人が東端で作業を開始し、すべての電話が西端にある隣接する XNUMX 軒の家からかかってくると想像してください。 その場合、配管工の XNUMX 人は決して動かず、もう XNUMX 人はこれら XNUMX 軒の家でマイルを貯めます。 振り返ってみると、最善の戦略は、両方の配管工を問題が発生しやすい場所に移動させることでした。しかし、残念なことに、それがどこになるかはわかりませんでした。

それでもビエンコウスキー氏は、貪欲なアルゴリズムよりも優れた成果を上げることは可能だと語った。 ”ダブルカバー」アルゴリズムにより、両方の配管工が、どちらかが到達するまで、その間に発生した通話に向かって同じ速度で移動します。 この方法では、貪欲アルゴリズムよりも低い競争率が達成されます。

この抽象的な問題は実際の配管会社には関係ありませんが、「 k「サーバーの問題自体が、オンライン コンピューティングを決定づける問題なのです」と氏は述べています。 ユヴァル・ラバーニ、最近の論文の共著者であるエルサレムのヘブライ大学のコンピューター科学者。 その理由の XNUMX つは、開発中にツールや技術が開発されたためです。 k-サーバーの問題は、オンライン アルゴリズムの研究の他の場所、さらにはその外側でも応用できることがよくあります。

「これはアルゴリズムに取り組む魔法の一部です」と彼は言いました。

これらの問題を研究するとき、科学者はそれらを敵とのゲームとして想像することを好みます。 敵対者は、オフラインのアルゴリズムと比較してオンライン アルゴリズムのパフォーマンスを可能な限り低下させるために、悪魔のような一連のリクエストを選択します。 敵対者の力の一部を奪うために、研究者は次のようなアルゴリズムを使用します。 ランダムな決定.

この戦略は非常に効果的であり、研究者たちは 1990 年代初頭から、特定のパフォーマンス目標 (対数に比例する競争率) を達成するランダム化されたアルゴリズムを常に見つけることができるのではないかと考えてきました。 kここで、 k エージェントの数です。 これをランダム化といいます k-サーバー予想であり、研究者らは、これが一部の空間、または特定の点の集合 (配管工を呼ぶ可能性のある家に相当) に当てはまることを示しました。 しかし、すべてのケースでそれが証明されたわけではありません。

ほとんどの研究者と同様に、ラバーニとその共著者も — セバスチャン・ブベック Microsoft Researchの クリスチャン・コースター オックスフォード大学の教授 — この推測は正しいと考えました。 「それを疑う理由はありませんでした」とコースター氏は語った。

しかし、別のオンライン問題に取り組むうちに状況は変わり始めました。 それにはつながりがありました k-サーバーの問題があり、既知の競争率の下限は予想外に高かった。 それは彼らに、おそらく目標はログと同じくらい低いものであると考えさせました k k-サーバーの問題は楽観的すぎました。

ラバーニ氏は、無作為化を最初に示唆したのはコースター氏だと述べた。 k-server の推測は間違っている可能性があります。 「彼がそう言った瞬間、すべてが腑に落ちた。」

この推測を反証するために、著者らは敵対者を演じ、オンラインアルゴリズムがログの競争率に達することを妨げる完璧な嵐を引き起こした。 k。 彼らの戦略には XNUMX つの部分がありました。複雑なフラクタルのような空間のファミリーを構築し、どのようなアルゴリズムでも困難なリクエスト シーケンスの分布を設計しました。 アルゴリズムの最初の移動では、空間の構造により XNUMX つの同一のパスから選択する必要があり、そのうちの XNUMX つは最終的にリクエストに基づいて追加の移動が必要になります。 次に、著者らは再帰と呼ばれる方法を使用して、これらの決定点を倍増させるスペースを構築し、アルゴリズムを悪い選択肢の泥沼に押し込み、コストを押し上げました。

この選択はラバニにロバート・フロストの詩を思い出させた。選ばれなかった道、」では、旅行者が黄色い森を通る XNUMX つの潜在的な道を熟考します。 「私たちは詩を再帰的に適用しているだけです」と彼は冗談を言いました。 「そして、事態は非常に悪い方向に進みます。」

著者らは、自分たちが構築した空間では、ランダム化されたアルゴリズムが (log k)²、ログの普遍的な目標を推進します k 永遠に手の届かないところに。 彼らはその推測を否定した。

を受賞したこの作品は、 最優秀論文賞 2023 年コンピューティング理論シンポジウム、グプタ氏は、「確かな理論的」マイルストーンをマークすると述べた。 この種の結果は、アルゴリズムにどのようなパフォーマンスが期待できるかを示すのに役立ちます。 しかし、実際には、アルゴリズム設計者は、全能の敵が存在し、将来のことをまったく知らないという最悪のシナリオを想定して計画を立てていないことがよくあります。 現実世界の問題に対してアルゴリズムが解き放たれると、理論的な期待を超えることがよくあります。

この論文は、他の問題に使用されるランダム化アルゴリズムのカットオフも証明しており、この分野での将来の研究にも影響を与える可能性があります。 この結果は、著者らが使用した手法の「威力を明らかに示している」とグプタ氏は述べた。

おそらく、これらの将来の発見は、今回の発見と同様に研究者の予想を裏切るものになるだろうとラバーニ氏は述べた。 「これは、間違っていることが本当に良いと感じるケースのXNUMXつです。」

クアンタ では、視聴者により良いサービスを提供するために一連のアンケートを実施しています。 私たちのものを取ってください コンピュータサイエンス読者アンケート そしてあなたは無料で当選するためにエントリーされます クアンタ 商品。