8つの一般的なアルゴリズムのアイデアを説明する1つの記事

アルゴリズムとデータ構造は、常にプログラマーの基本的なスキルでした。データ構造の基本インフラストラクチャとアルゴリズムのサポートがなければ、約80年間の情報革命時代は存在しなかったと言えます。データ構造は、アルゴリズム実装のコンテナとして考えることができます。一連の特別に構造化されたデータ セットを通じて、アルゴリズムをより効率的かつ確実に実行できます。

アルゴリズムの適用はプログラミングにのみ反映されるわけではありません。狭義では、アルゴリズムとは、さまざまなソートアルゴリズムなど、データの転送や処理の順序、方法、構成を指すと言えます。広い意味では、アルゴリズムは物事が動作するロジックやルールに似ています。太陽が昇ったり沈んだり、海の潮が満ちたり、月が満ちたり欠けたり、これらはすべてアルゴリズムのように見えるかもしれませんが、実行者は電気コンピュータではなく、自然そのものです。

話が逸れてしまいました。したがって、アルゴリズムを理解するには、そのアイデアを理解し、その内部の意味を感じることが重要です。生徒の中には、「アルゴリズムって、Leetcode に過ぎない。ただの練習問題じゃないの？」と言う人もいるかもしれません。

それはあまりにも一方的だ。解決すべき疑問は常に無限にありますが、アルゴリズムのアイデアはほんのわずかです。したがって、これまで多くの問題を解いたにもかかわらず、これらの一般的なアルゴリズムの考え方をまだ理解していない場合は、おそらく自分自身を振り返る必要があるでしょう。

列挙する

まず、最も単純なアイデアである列挙アルゴリズムです。列挙は網羅的列挙とも呼ばれ、その名前が示すように、網羅的な列挙を意味します。列挙思考の応用シナリオは非常に幅広く、非常に理解しやすいです。簡単に言えば、列挙とは、問題の可能性を一つずつリストアップし、それを一つずつ問題に適用してテストし、一連の可能な解決策から問題を解決できる正確な解決策を得ることです。

列挙は単純に見えますが、見落としがちな考慮事項がいくつかあります。例えば、解決すべき問題に対する「可能解・候補解」の選別条件、「可能解」同士の相互影響、「可能解」を網羅的に列挙するコスト、「可能解」の網羅的方法などです。

多くの場合、実際にはハイエンドで複雑なアルゴリズム構造を追求する必要はありません。代わりに、シンプルさが最善の方法です。列挙方法を使用すると、システムの複雑さによって発生する冗長性を効果的に回避でき、スペースもある程度削減できる可能性があります。

列挙思考のプロセスは次の図で表すことができます。事前に「可能な解決策」を決定し、それをシステム内で一つずつ検証することで、検証結果に基づいて「可能な解決策」を分析・実証します。これは非常に明白な結果指向のアイデアであり、最終結果から「可能な解決策」の実現可能性を単純に大雑把に逆分析しようとします。

しかし、列挙思考の欠点ももちろん明らかです。実際に実行されているプログラムでは、列挙メソッドを通じて直接解決できる問題はほとんどありません。しかし、「可能な解決策」の選別条件が明確でなく、「可能な解決策」の数や範囲を正確に判断できない場合、列挙の意味が失われます。

ただし、「可能な解決策」の規模が比較的小さく、順次検証のプロセスを簡単に実装できる場合は、列挙が便利で迅速な方法です。ただし、具体的な使用法では、アプリケーション シナリオに応じて「可能なソリューション」の検証を最適化することもできます。

この最適化は 2 つの方向から開始できます。1 つは、問題を単純化し、扱う問題のモデル構造を可能な限り単純化することです。この単純化は、問題内の変数の数に具体的に反映され、変数のデータが削減され、それによって「可能な解決策」の組み合わせが根本的に削減されます。

第二に、「可能な解決策」を選別する範囲と条件を厳密に判断し、無効な「可能な解決策」を可能な限り排除します。

そうは言っても、一般的に言えば、列挙が使用できないシナリオのほとんどは、「可能な解決策」が多すぎて、限られたスペースや時間内ですべての可能性を検証することが不可能であるためです。しかし実際には、列挙思考は人間の思考方法に最も近く、「問題を解決する」というよりも「問題を理解する」のに役立つことが多いのです。

場合

100 ドルで 100 羽の鶏を買う問題。 問題は次のように説明されます: 1 羽の老鶏は 5 枚のコインの価値があります。1 羽の雌鶏は 3 枚のコインの価値があります。3 羽のひよこは 1 枚のコインの価値があります。100 枚のコインを使用して 100 羽の鶏を購入した場合、老鶏、雌鶏、ひよこは何羽あるでしょうか。

翻訳すると、雄鶏は5元、雌鶏は3元、ひよこ3羽は1元です。今、100元を使って鶏100羽を買いたいのですが、雄鶏、雌鶏、ひよこは何羽ありますか？

再帰

再帰的思考は、列挙的思考と同様に、人間の思考方法に近いだけでなく、実生活において列挙的思考よりも多くの応用シナリオがあります。人間の脳が未知の問題に遭遇すると、ほとんどの人が最初にとる本能は、蓄積された「事前の知識」から始めて、「既知」から「未知」を推論し、問題を解決して自分自身を納得させようとすることです。

実際、これは再帰アルゴリズムのアイデアです。再帰的思考の核心は、既知の条件から始めて、徐々に問題の解決策を導き出すことです。実施方法は、中学校や高校の数学のテスト問題にある「なぜなら」や「だから」の連続と非常によく似ています。当時はまだ3つの点で表されていました。

しかし、複雑な導出をコンピュータが実行するのは困難です。コンピュータは高密度で反復的なタスクを実行するのが得意ですが、非常にランダムで変化しやすい問題を計算するのは困難です。対照的に、人間の脳は、異なる次元の問題について推論する際に、より高い自由度を持っています。

たとえば、人間の脳は「太陽は西に沈む」ということから「太陽は東から昇る」ということを簡単に推測し、それから「現在の時刻」を大まかに推測することができます。しかし、コンピュータにとっては、それはそれほど簡単ではありません。コンピュータが「太陽/月/星」が「南/北/東」から「落ちる/飛んでいく/落ちる」可能性を推測するのを防ぐために、一連の制限を設定する必要があるかもしれません。

この例を挙げる目的は、コンピューターが再帰的思考を使用する場合、推論の大部分が反復的であることを示すことです。たとえば、「今日は 1 日です」から「明日は 2 日です」と推測できます。この種の推論の構造は非常に似ており、最終的な解決策は、推論を繰り返すことで得られることが多いです。

再帰的な考え方は、下の図に示すように図で表されます。各導出の結果は次の導出の開始点として使用できます。これは反復と再帰の考え方に多少似ているようですが、再帰の範囲はより広くなります。

場合

ウサギの問題。 大きなウサギのつがいは、毎月一組の子ウサギを産み、生まれた子ウサギは一ヶ月後には大きなウサギのつがいに成長し、繁殖能力を持つようになります。もし死ぬことがなく、一組ごとに雄と雌が生まれるとしたら、一年間に何組のウサギがいるでしょうか？

再帰

再帰について話した後は、その兄弟概念である再帰アルゴリズムについて話す必要があります。どちらにも「迭」という単語が含まれており、ある程度の類似点があることがわかります。 「配信」は、連続的かつ段階的に行うという意味で理解できます。再帰では、最終的な解決策が得られるまで、問題は一度に 1 ステップずつ推論されます。再帰では、回帰が終了するまで回帰が繰り返し実行されます。

再帰アルゴリズムは、実際には問題をより小規模な類似の問題に変換し、最初にサブ問題を解決し、次に同じ解決プロセスを通じて徐々に高レベルの問題を解決し、最終的に最終的な解決策を取得します。したがって、再帰と比較すると、再帰アルゴリズムの範囲は狭く、サブ問題の構造が親問題の構造と同じである必要があります。しかし、再帰的思考にはそのような概念的な制約はありません。

再帰アルゴリズムの実装を一言で説明すると、関数またはサブルーチン内で独自のアルゴリズムを直接または間接的に呼び出すことです。したがって、実装プロセスにおいて最も重要なことは、再帰プロセスの終了条件、つまり反復プロセスを終了するための条件判断を決定することです。そうしないと、プログラムは自己呼び出しで無限ループし、最終的にはメモリ オーバーフローによりクラッシュします。

再帰アルゴリズムは以下のように表すことができます。明らかに、再帰的思考は実際にはネストプロセスです。一般的に、当局は入れ子人形の使用を厳しく禁止しています。したがって、これを使用する場合は、「マトリョーシカ」アクションの停止条件を明確に定義し、時間内に損失を停止する必要があります。

場合

ハノイの塔問題。 これは、ブラフマーが世界を創造したとき、3 本のダイヤモンドの柱を建て、そのうちの 1 本に下から上に 64 枚の金の円盤が積み重ねられていたというインドの伝説に由来しています。ブラフマー神はバラモンに、別の柱の上の円盤を下から大きさの順に並べ直すように命じました。また、小円盤上では円盤を拡大することはできないこと、また、3本の柱の間では一度に1枚の円盤しか移動できないことが規定されています。

分割して征服する

分割して征服する。

分割統治アルゴリズムの中核となるステップは 2 つあり、1 つは分割、もう 1 つは統治です。しかし、これはまた、なぜ分割するのか、どのように分割するのか、どのように治療するのか、そして治療後に何が起こるのかといった一連の疑問につながります。

分割統治アルゴリズムは、下向きの管理アイデアに非常に似ています。これは、サブタスクを最上位レベルから異なるサブモジュールに分割し、次に大きな問題を分割し、システム問題の粒度を細かくして、最下位レベルで最も基本的なソリューションを探します。この考え方は、直交座標、単位座標、幾何数学の基底の概念など、多くの分野で使用されています。これらの考え方はすべて、複雑な問題を基本的なサブ問題に単純化し、最初にサブモジュールを解決してメインモジュールを徐々に解決することによって適用されます。

実際のアプリケーションでは、分割統治アルゴリズムには主に 2 つの処理次元が含まれます。1 つは上から下への処理で、メインの問題を層ごとにサブ問題に分割します。もう 1 つは下から上への処理で、サブ問題のソリューションを層ごとにメインの問題のソリューションに統合します。

では、なぜ分割する必要があるのでしょうか。これは簡単に説明できます。主な問題の規模が大きすぎて直接解決できないため、主な問題を粒度に分割する必要があるからです。

どのように分割するか？コンピュータが最も得意とする繰り返し操作に従い、分割されたサブ問題は互いに独立しており、元の問題と同じ構造特性を持つ必要があります。これにより、サブ問題を解決した後、メインの問題をスムーズに解決できるようになります。

どうやって治すか？これには、最も基本的なサブ問題を解決することが含まれます。最小のサブ問題は簡単に解決でき、そのようなサブ問題の分割だけが意味があることに同意します。したがって、治療プロセスでは、最も基本的なサブ問題に対する簡単な解決策を見つける必要があります。

次に何が起こるでしょうか? サブ問題の解決策がメインの問題に役立ちます。最も基本的なサブ問題が解決されたら、元の問題の最終的な解決が得られるまで、レベルを段階的に上げていき、より高レベルの問題の解決を徐々に得る必要があります。

分割統治の考え方の図は、下の図に示されています。元の問題を層ごとに細分化して最小のサブ問題に分割することで、より高い粒度のソリューションを順番に得ることができます。上から下へ、そして下から上へ。まず分解し、次に解決し、最後にマージします。

場合

マージソート。

動的プログラミング

分割統治について話した後、分割統治の考え方の最も重要な点は、分解されたサブ問題が互いに独立しており、同じ構造特性を持っていることであることがわかります。これはすべての問題に当てはまるわけではありません。多くの問題のサブ問題は重複して相互に影響を及ぼし合うことが多いため、分割統治アルゴリズムを使用してサブ問題を効果的かつきれいに分割することは困難です。

そこで、動的プログラミングが生まれました。動的プログラミングでは、問題を複数のサブ問題に分割する必要もありますが、サブ問題は互いに独立していないことがよくあります。現在のサブ問題の解決策は、前の段階の問題の完全な要約として考えることができます。したがって、サブ問題を解決するプロセスでは多段階の意思決定を行う必要があり、現在の段階より前の意思決定によって最適なサブ構造を構成することができます。これがいわゆる最適化の原則です。

最適化の原則: 最適化戦略には、過去の状態や決定が何であっても、残りの決定は、以前の決定によって形成された状態に対して最適な戦略を構成する必要があるという特性があります。同時に、このような最適戦略は、これまでに行われた決定の要約であり、後続の決定に直接影響を与えることはなく、現在の最適戦略のステータスデータを借りることしかできません。これを後遺症なしとも言います。

動的プログラミングは、人間の思考の仕組みから非常にかけ離れているように思えるアルゴリズムです。その主な理由は、計算プロセス中に各決定の結果を人間の脳が記憶することが難しいためです。実際の操作では、動的プログラミングでは、次の決定で使用するために各ステージのステータスデータを保存するための追加のスペースが必要になることがよくあります。

動的計画法の解法アイデアは次の図に示されています。動的回帰を開始するには、問題を特定の順序でさまざまな段階に分割し、図のノードの F0 など、各段階のステータスを決定する必要があります。次に、意思決定方法に基づいて状態遷移方程式を決定することに焦点が当てられます。つまり、現在のステージの状態に基づいて次のステージの状態を決定する必要があります。

このプロセスでは、次の状態を決定するために、多くの場合、前の状態を参照する必要があります。したがって、後続の検索を容易にするために、各状態転送中に現在の状態変数を記録する必要があります。

動的計画法は主に多段階の意思決定問題を解決するために使用されますが、実際の問題に対して統一されたアプローチをとることは難しいことがよくあります。アルゴリズムは問題の特性に基づいて設計する必要があります。これが、このアルゴリズムを真に習得するのが難しい理由です。

場合

ナップザック問題。 n 個のアイテムと容量 m のバックパックがあります。アイテムの重量と価値を指定します。バックパックに入れるアイテムの重量がバックパックの容量を超えず、値が最大になるような解決策を見つけます。

弾性

貪欲アルゴリズムは最も現実的なアルゴリズムのアイデアだと私は呼びたいと思います。

人間がこの世に生きるとき、すべての選択が完璧であることは不可能です。問題が多すぎるため、すべての問題に対して最善の解決策を見つけることは不可能です。多くの問題には正確な解決策がないか、あるいはまったく解決策が存在しないこともあります。したがって、シナリオによっては、問題に対する最も正確な解決策を愚かに追求するのは無意味です。

最適な解決策があると主張する人もいます。最適なソリューションはもう必要ありませんか?

はい、多くの問題に対して最も正確な解決策はありませんが、確かに 1 つまたは複数の最適な解決策は存在します。しかし、こうした最適解を追求する必要があるのでしょうか? 私はそうは思いません。

アルゴリズムの存在は、単に問題を解決するためではなく、「戦略」を提供するためです。 「戦略」とは何でしょうか? それは問題を解決するための方法、角度、または経路です。したがって、貪欲な思考は価値があるのです。

貪欲アルゴリズムについて話しましょう。貪欲という言葉からわかるように、このアルゴリズムの目的は「もっと欲しがること」です。しかし、このような貪欲さは「近視眼的」であり、貪欲なアルゴリズムは長期的な視点を持てず、目先の利益だけに焦点を当てることになります。

具体的には、貪欲アルゴリズムの実行中は、毎回最大の利益が選択されますが、合計利益は必ずしも最大になるわけではありません。したがって、このような素朴な考え方の利点は、選択が単純であり、将来について心配したり考慮したりする必要がないことです。

貪欲アルゴリズムの実装プロセスは、問題の初期解決策から開始し、ローカルの極値点に遭遇するまで毎回「現在最適な」選択を行うことです。貪欲によってもたらされる限界は明らかです。つまり、最終的な解決策が最善であるという保証はなく、局所的な最適な状況に陥りやすいのです。

しかし、毎回の選択は非常に速く、判断条件も単純なので、比較的早く同様の解を出すことができます。ここでは、次の図を使用して図を説明します。

この図は、複数の直線の交差の解を示しています。明らかに、下の図の直線には統一された交点がありませんが、アルゴリズムを通じて統一された交点の最適解を得ることができます。貪欲アルゴリズムが使用される場合、反復処理のたびに、現在の位置に最も近い行が更新用に選択されます。このように、多くの反復を経て、交差点の位置は特定の領域内で無限にジャンプすることになります。そして、この領域は、見つけることができるおおよその最適解領域です。

場合

巡回セールスマン問題。 都市のリストと各都市間の距離が与えられた場合、各都市を 1 回訪れて開始都市に戻る最短経路を見つけます。

バックトラッキング

葦は青々と茂り、白い露は霜に変わります。いわゆる美しさは水の向こう側にある。上流に向かって進むと、道は長くて困難です。それを上流に向かって辿っていくと、水の中心にたどり着くでしょう。

振り返ると言うと、いつも『姜佳』のこの一節を思い出さずにはいられません。恋しい恋人を見ると、たとえ道が長くて危険であっても、ついつい上流へ泳いで彼女を追いかけてしまいます。そして下流へ泳ぎ続け、まるで彼女が川の真ん中にいるような気分になります。バックトラッキング アルゴリズムのプロセスは、愛を追いかけるのと同じくらい困難で反復的です。時には上流に、時には下流に追従します。

バックトラッキング アルゴリズムは、ヒューリスティック アルゴリズムとも呼ばれます。女神の前でどれほど慎重だったかを思い出しませんか?簡単に言えば、バックトラッキングのプロセスは、次の選択を行う前にあらゆる可能性をテストすることです。可能性がある場合にのみ、前進します。すべての選択が不可能な場合は、元の位置に戻って新しい選択を行います。

バックトラッキング アルゴリズムは、進行中のすべての可能性を列挙して判断する、進行中の列挙アルゴリズムに非常によく似ているようです。一般的なアプリケーション シナリオとしては、ツリー構造、グラフ構造、チェス盤の駒のトラバースなどがあります。

非常に簡単な例を挙げて、下の図を見てみましょう。目標が O0 から O4 に到達することであると仮定すると、すべてのノードのパスをバックトラックする必要があります。次に、バックトラッキング アルゴリズム プロセスでは、各ステップですべての可能なパスを試す必要があります。

たとえば、ノード O0 が前進するためのパスは、O1、上パス、中パス、下パスの 3 つあります。バックトラック プロセスの開始時に、まず上記の O1 に移動し、次に上記の O2 に到達できますが、これは行き止まりです。次に、O2 から O1 に戻る必要がありますが、この時点では O1 という唯一のオプションは実行可能ではないため、O1 から O0 に戻る必要があります。次に、中央で O1 のテストを続けます。

バックトラッキング アルゴリズムのプロセスは、完全な前進経路が見つかるまで、このような試行、判断、後退、再試行を継続的に実行することです。ただし、このプロセスでは、「剪定」などの制限条件によって試行と検索の余地が削減され、試行の繰り返しや無効な試行が回避されます。たとえば、O0-O1-O2 を通じてテストされた後、上部および下部の O2 ノードは実行不可能であることが検証されているため、次回は O1 から O2 に対してテストを繰り返す必要はありません。

バックトラッキングの考え方は、多くの大規模な問題を解決する際に効果的に使用できます。バックトラッキングを使用すると、複雑な問題を段階的に調整できるため、列挙思考の可能なすべてのアプリケーションを中間プロセスで横断できます。これにより、問題解決のレベルを明確に把握できることが多く、問題の最終的な解決構造をよりよく理解するのに役立ちます。

場合

8人のクイーンの問題。 8×8 のチェス盤に 8 つのクイーンを配置して、クイーン同士が攻撃し合わないようにする方法、つまり、同じ行、列、または対角線上に 2 つのクイーンがないようにする方法は何通りありますか。

シミュレーション

上記のアイデアと比較すると、シミュレーションのアイデアを理解することは難しくないはずです。

多くの現実世界のシナリオでは、問題の規模が大きい、変数が多すぎるなどの要因により、特定の問題を抽象化することが難しく、抽象的な問題の特性に基づいてアルゴリズムを設計することも不可能です。現時点では、シミュレーション思考が最善の問題解決戦略である可能性があります。

シミュレーション プロセスは、実際のシーンをできるだけ忠実にシミュレートし、コンピューターの強力な計算能力によって結果を予測することです。これは上記のアルゴリズムよりも野心的なアイデアです。現実のシナリオをシミュレーションする場合、システム コンポーネントの実装には、前述のアルゴリズムのアイデアの参加が必要になる場合があります。

シミュレーションは非常に不思議な概念です。具体的な実装のアイデアや最適化戦略はありません。私が言えるのは、それぞれのケースを個別に分析する必要があるということだけです。

それで、どのように説明すればよいのでしょうか?私の理解では、カスタマイズされた任意の入力、不規則なシステム応答ですが、信頼できる理想的な出力を得るためだけです。

要約する

アルゴリズム的思考は実は非常に神秘的です。同じ問題が異なるアプローチで解決される場合もあります。これら 8 つのアイデアは、想像されているほど独立しているわけではありません。多くのアイデアが混ざり合っていますが、角度や重点が異なります。上記のケースは、1 つのアイデアだけで解決できるという意味ではなく、対応するアルゴリズムのアイデアを体験するために使用されているだけです。

低レベルのプログラマーの場合、毎日問題を練習する必要はありませんが、基本的なアルゴリズム思考は必要です。このようなことは、特定のアルゴリズムに特有のものではなく、むしろシステムや要件に対するより高レベルの理解です。

独立心や自由な考え方など。