アルゴリズム
ページは半保護されています

ループ内で、大きい数から小さい数を引きます。引き算によって負の数になった場合はループを停止します。2つの数のうち、どちらかが0かどうかを確認します。0の場合は、もう一方の数を最大公約数とします。0でない場合は、2つの数を再び引き算ループに戻します。
連続減算を使用して数rと数 sの最大公約数を求めるフローチャート

数学およびコンピュータサイエンスにおけるアルゴリズム( / ˈ æ l ɡ ə r ɪ ð əm /ⓘ ）は、数学的に厳密なの有限列であり問題を解い計算を実行したりするため。 [ 1 ]アルゴリズムは、計算やデータ処理を実行するための仕様として使用されます条件文を使用してコード実行をさまざまなルートに分岐させ（自動意思決定推論を導き出します自動推論と呼ばれます）。

対照的に、ヒューリスティックとは、明確に定義された正しい結果や最適な結果がない問題を解決するためのアプローチです。[ 2 ]たとえば、ソーシャルメディアの推奨システムは一般的に「アルゴリズム」と呼ばれていますが、実際には本当に「正しい」推奨は存在しないため、ヒューリスティックに依存しています。

効果的な方法として、アルゴリズムは有限の空間と時間[ 3 ]内で、関数を計算するための明確に定義された形式言語[ 4 ]で表現することができます。[ 5 ]初期状態と初期入力（おそらく空）から始まり、[ 6 ]命令は計算を記述します。この計算は、実行されると有限個の明確に定義された連続状態[ 7 ]を経て進み、最終的に「出力」 [ 8 ]を生成し、最終状態で終了します。ある状態から次の状態への遷移は必ずしも決定論的ではありません。ランダム化アルゴリズムと呼ばれる一部のアルゴリズムでは、ランダム入力が組み込まれています。[ 9 ]

語源

825年頃、ペルシャの科学者で博学者のムハンマド・イブン・ムーサー・アル＝フワーリズミーは、『キターブ・アル＝イスアーブ・アル＝ヒンディー』（インドの計算書）と『キターブ・アル＝ジャム・ワル・タフリク・アル＝イスアーブ・アル＝ヒンディー』（インドの算術における加減法）を著した。12世紀初頭には、ヒンドゥー教とアラビア数字のシステムと算術に関するこれらのテキストのラテン語訳が登場し、例えば、セビリアのヨハネに帰せられる『Liber Alghoarismi de practica arismetrice 』や、バースのアデラードに帰せられる『Liber Algorismi de numero Indorum 』がある。[ 10 ]ここで、alghoarismiまたはalgorismiはアル＝フワーリズミーの名前のラテン語化である。 [ 1 ]本文は「Dixit Algorismi」、つまり「アル・フワーリズミーはこう語った」というフレーズで始まる。[ 2 ]

英語の「アルゴリズム」という語は、計算において位取り記法を用いることを意味するようになり、1225年頃の『アンクレネ・ウィッセ』に登場します。 [ 11 ]ジェフリー・チョーサーが14世紀後半に『カンタベリー物語』を執筆した頃には、位取り計算に用いる石であるオーグリム石を説明する際に、同じ語の異形を用いていました。 [ 12 ] [ 13 ] 15世紀には、ギリシャ語のἀριθμός ( arithmos、「数」、比較すると「算術」)の影響を受けて、ラテン語の語はalgorithmusに変化しました。[ 14 ] 1596年までに、この語形はトーマス・フッドによって英語のalgorithmとして用いられました。[ 15 ]

意味

非公式な定義の一つは「一連の演算を正確に定義する規則の集合」である[ 16 ]。これには、数値計算を行わないプログラムを含むすべてのコンピュータプログラム、そして規定された官僚的手続き[ 17 ] や料理本のレシピ[ 18 ]が含まれる。一般的に、プログラムは最終的に停止する場合にのみアルゴリズムである[ 19 ] 。ただし、無限ループが望ましい場合もある。Boolos 、Jeffrey、1974、1999は、アルゴリズムを、出力を決定するための明示的な命令の集合であり、計算機または記号に対して特定の基本演算しか実行できない人間が実行できるものと定義している[ 20 ]。

ほとんどのアルゴリズムはコンピュータプログラムとして実装されることを目的としています。しかし、アルゴリズムは生物学的ニューラルネットワーク（例えば、人間の脳が計算を行う、昆虫が餌を探すなど）、電気回路、機械装置など、他の手段によって実装されることもあります。

歴史

古代のアルゴリズム

数学の問題を解くための段階的な手順は、古代から記録されています。これには、バビロニア数学（紀元前2500年頃）[ 21 ] 、エジプト数学（紀元前1550年頃）[ 21 ] 、インド数学（紀元前800年頃以降）[ 22 ] 、 [ 23 ]、イファの神託（紀元前500年頃）[ 24 ] 、ギリシャ数学（紀元前240年頃）[ 25 ] 、中国数学（紀元前200年頃以降）[ 26 ]、アラビア数学（紀元後800年頃）[ 27 ]が含まれます。

アルゴリズムの最も古い証拠は、古代メソポタミアの数学に見られます。バグダッド近郊のシュルッパクで発見され、紀元前 2500年頃のシュメールの粘土板には、最古の除算アルゴリズムが記されています。[ 21 ]ハンムラビ王朝時代（紀元前 1800年頃 ～紀元前 1600年頃）には、バビロニアの粘土板に数式を計算するためのアルゴリズムが記されていました。[ 28 ]アルゴリズムはバビロニアの天文学でも使用されていました。バビロニアの粘土板には、重要な天文現象の時間と場所を計算するためのアルゴリズム手順が記されており、それが用いられています。[ 29 ]

算術アルゴリズムは古代エジプトの数学にも見られ、 紀元前1550年頃のリンド数学パピルス にまで遡ります。[ 21 ]アルゴリズムは後に古代ヘレニズム数学でも使用されました。2つの例としては、ニコマコスの『算術入門』 [ 30 ] [ 25 ] : 第9章2節 に記載されているエラトステネスのふるいと、ユークリッドの『原論』 （紀元前 300年頃）で初めて説明されたユークリッドの互除法があります。[ 25 ] : 第9章1節 古代インドの数学の例には、シュルバ・スートラ、ケーララ学派、ブラフマスフタシッダーンタなどがあります。[ 22 ]

暗号化されたコードを解読するための最初の暗号アルゴリズムは、9世紀のアラブの数学者アル＝キンディーによって『暗号解読に関する手稿』の中で開発されました。彼は、最古の暗号解読アルゴリズムである頻度分析による暗号解読法を初めて記述しました。[ 27 ]

コンピューター

重力駆動時計

デイヴィッド・ボルターは、重錘駆動時計の発明を「[中世ヨーロッパにおける]鍵となる発明」と称え、特に機械式時計のチクタク音を生み出すバージ脱進機機構[ 31 ]を高く評価しています。「正確な自動機械」 [ 32 ]は、13世紀の「機械式オートマタ」、そして19世紀半ばのチャールズ・バベッジとエイダ・ラブレスによる「計算機械」、すなわち差分機関と解析機関[ 33 ]へと直接つながりました。ラブレスは、コンピュータ処理を目的とした最初のアルゴリズム、バベッジの解析機関を設計しました。これは、単なる計算機ではなく、真のチューリング完全コンピュータとみなされた最初の装置です。バベッジの2番目の装置の完全な実装は、彼女の生後数十年を経て実現されましたが、ラブレスは「歴史上最初のプログラマー」と呼ばれています。

電気機械リレー

ベルとニューウェル（1971）は、ホレリスカード（パンチカード）の前身であるジャカード織機と「電話交換技術」が、最初のコンピュータの開発につながったと述べている。[ 34 ] 19世紀半ばまでに、電話の前身である電信が世界中で使用されるようになった。19世紀後半には、ティッカーテープ（ 1870年代頃）とホレリスカード（1890年頃）が使用されるようになった。その後、テープに ボードット符号を刻んだパンチ紙を備えたテレプリンター（ 1910年頃）が登場した。

電気機械式リレーを用いた電話交換網は1835年に発明されました。これは1937年、ジョージ・スティビッツによるデジタル加算装置の発明につながりました。ベル研究所で働いていたスティビッツは、歯車を使った機械式計算機の「煩わしい」使用方法に気づきました。「1937年のある晩、彼は自分のアイデアをテストしようと帰宅しました…試行錯誤が終わると、スティビッツは2進加算装置を完成させました。」[ 35 ] [ 36 ]

形式化

エイダ・ラブレスの「ノートG」の図、最初に公開されたコンピュータアルゴリズム

1928年、現代アルゴリズムの概念の部分的な形式化は、デイヴィッド・ヒルベルトが提起した決定問題（Entscheidungsproblem ）を解く試みから始まった。その後の形式化は、「有効な計算可能性」[ 37 ]または「有効な方法」[ 38 ]を定義する試みとして位置づけられた。これらの形式化には、1930年、1934年、1935年のゲーデル・ヘルブランド・クリーネの再帰関数、1936年のアロンゾ・チャーチのラムダ計算、1936年のエミール・ポストの定式化1、そして1936年から1937年、そして1939年のアラン・チューリングのチューリングマシンなどが含まれる。

現代のアルゴリズム

アルゴリズムは、時とともに様々な形で進化し、改善されてきました。今日、アルゴリズムの一般的な用途としては、 InstagramやYouTubeなどのソーシャルメディアアプリが挙げられます。アルゴリズムは、人々が何を好むかを分析し、それらと交流する人々に、それらのものをより多くプッシュする手段として利用されています。量子コンピューティングは、量子アルゴリズムの手順を用いて問題をより迅速に解決します。さらに最近では、2024年にNIST（米国国立標準技術研究所）がポスト量子暗号標準を更新し、量子コンピューティングを用いた攻撃に対する防御を強化するための新しい暗号化アルゴリズムを追加しました。

表現

アルゴリズムは、自然言語、擬似コード、フローチャート、ドラコンチャート、プログラミング言語、制御表（インタープリタによって処理される）など、様々な表記法で表現できます。自然言語によるアルゴリズムの表現は冗長で曖昧になりがちで、複雑なアルゴリズムや技術的なアルゴリズムにはほとんど使用されません。擬似コード、フローチャート、ドラコンチャート、制御表は、自然言語によくある曖昧さを回避した、アルゴリズムの構造化された表現です。プログラミング言語は、主にアルゴリズムをコンピュータで実行可能な形式で表現するためのものですが、アルゴリズムの定義や文書化にも使用されます。

チューリングマシン

チューリングマシンのプログラムは、様々な表現方法があり、マシンテーブルのシーケンス（詳細は有限状態機械、状態遷移表、制御表を参照）、フローチャートやドラコンチャート（詳細は状態図を参照）、基本的なマシンコードまたはアセンブリコードの一種である「四重項の集合」などとして表現できます。アルゴリズムの表現は、チューリングマシン記述の3つのレベル、すなわち高レベル記述、実装記述、形式記述に分類できます。[ 39 ]高レベル記述は、アルゴリズム自体の特性を記述し、チューリングマシン上での実装方法は考慮しません。[ 39 ]実装記述は、アルゴリズムを実行するためにマシンがヘッドを動かし、データを格納する一般的な方法を記述しますが、正確な状態は示しません。[ 39 ]形式記述は、最も詳細には、チューリングマシンの正確な状態テーブルと遷移リストを示します。[ 39 ]

フローチャート表現

フローチャートと呼ばれる図表は、アルゴリズム（およびそれに対応するコンピュータプログラム）を記述し、文書化する手段を提供します。フローチャートには、プログラムの流れを示す矢印、四角形（SEQUENCE、GOTO）、ひし形（IF-THEN-ELSE）、そして点（OR-Tie）の4つの主要な記号があります。四角形の中にサブ構造を「ネスト」することができますが、その場合、スーパー構造から単一の出口が存在する必要があります。

アルゴリズム分析

アルゴリズムに必要な時間、ストレージ、その他のコストを把握することは、多くの場合重要です。このような定量的な答え（推定値）を得るために、アルゴリズムを分析する方法が開発されてきました。たとえば、n個の数値のリストの要素を合計するアルゴリズムでは、 big O 表記法を使用すると、時間要件は⁠ ⁠お（n）{\displaystyle O(n)}となります。アルゴリズムが記憶する必要があるのは、これまでのすべての要素の合計と、入力リスト内の現在の位置の2つの値だけです。入力数値を格納するために必要なスペースを考慮しない場合、スペース要件は⁠ ⁠ですが、そうでない場合は⁠ ⁠が必要です。 お（1）{\displaystyle O(1)}お（n）{\displaystyle O(n)}

異なるアルゴリズムは、異なる命令セットを用いて、他のアルゴリズムよりも少ない時間、空間、または「労力」で同じタスクを完了する場合があります。例えば、ソートされたリストや配列の表検索にバイナリサーチアルゴリズム（コスト⁠ ⁠お（ログ⁡n）{\displaystyle O(\log n)} ）を使用すると、シーケンシャルサーチ（コスト⁠ ⁠お（n）{\displaystyle O(n)} ）よりも優れたパフォーマンスを発揮します。

形式的対経験的

アルゴリズムの分析と研究は、コンピュータサイエンスの一分野です。アルゴリズムは、特定のプログラミング言語や実装を参照することなく、抽象的に研究されることがよくあります。アルゴリズム分析は、実装ではなくアルゴリズムの特性に焦点を当てる点で、他の数学分野に似ています。擬似コードは、単純で汎用的な表現であるため、分析によく使用されます。ほとんどのアルゴリズムは特定のハードウェア/ソフトウェアプラットフォーム上に実装され、そのアルゴリズムの効率性は実際のコードを用いてテストされます。特定のアルゴリズムの効率性は、多くの「一回限りの」問題では重要ではないかもしれませんが、高速なインタラクティブ、商用、または長期にわたる科学的利用のために設計されたアルゴリズムにとっては、非常に重要になる場合があります。小さなnから大きなnへとスケーリングすると、通常は問題のない非効率的なアルゴリズムが頻繁に明らかになります。

経験的テストは、パフォーマンスに影響を与える予期せぬ相互作用を発見するのに役立ちます。ベンチマークは、プログラム最適化後のアルゴリズムの潜在的な改善点を、その前後で比較するために使用できます。しかし、経験的テストは正式な分析に取って代わるものではなく、公平に実施することも容易ではありません。[ 40 ]

実行効率

十分に確立されたアルゴリズムでも改善の余地があることを示す例として、FFTアルゴリズム（画像処理の分野で多用されている）に関する最近の重要な技術革新により、医療用画像処理などのアプリケーションで処理時間を最大1,000倍短縮できることが挙げられます。[ 41 ]一般に、速度の向上は問題の特殊な特性に依存しますが、これは実際のアプリケーションでは非常に一般的です。[ 42 ]この規模の高速化により、画像処理を多用するコンピューティングデバイス（デジタルカメラや医療機器など）の消費電力を削減できます。

最良のケースと最悪のケース

アルゴリズムの最良のケースとは、アルゴリズムまたはデータ構造がタスクを完了するのに最も少ない時間とリソースしかかからないシナリオまたは入力を指します。[ 43 ] アルゴリズムの最悪のケースとは、アルゴリズムまたはデータ構造が最大の時間と計算リソースを消費するケースです。[ 44 ]

デザイン

アルゴリズム設計とは、問題解決やアルゴリズム設計のための手法、あるいは数学的プロセスである。アルゴリズム設計は、オペレーションズ・リサーチにおける分割統治法や動的計画法など、多くの解決理論の一部である。アルゴリズム設計の設計と実装のための手法は、アルゴリズム設計パターンとも呼ばれ、[ 45 ]テンプレートメソッドパターンやデコレータパターンなどがその例である。アルゴリズム設計において最も重要な側面の一つは、リソース（実行時間、メモリ使用量）の効率である。例えば、入力サイズの増加に伴うアルゴリズムの実行時間の増加を記述するために、ビッグオー記法が用いられる。[ 46 ]

構造化プログラミング

チャーチ＝チューリングのテーゼによれば、あらゆるアルゴリズムはあらゆるチューリング完全モデルで計算できる。チューリング完全性には、条件付きGOTO、無条件GOTO、代入、HALTの4種類の命令のみが必要である。しかし、ケメニーとカーツは、無条件GOTOと条件付きIF-THEN GOTOを「無秩序に」使用すると「スパゲッティコード」になる可能性がある一方で、プログラマーはこれらの命令のみを使用して構造化プログラムを作成できると指摘している。一方で、「構造化言語で構造化の悪いプログラムを作成することも可能であり、それほど難しくはない」。[ 47 ]タウスワースは、ベーム＝ヤコピニの3つの標準構造、[ 48 ] SEQUENCE、IF-THEN-ELSE、WHILE-DOに、DO-WHILEとCASEの2つを追加した。[ 49 ]構造化プログラムのもう1つの利点は、数学的帰納法を用いた正しさの証明が容易なことである。[ 50 ]

アルゴリズム自体は、通常、特許を取得できません。米国では、抽象概念、数値、または信号の単純な操作のみからなるクレームは「プロセス」を構成しないため（USPTO 2006）、アルゴリズムは特許を取得できません（Gottschalk v. Benson事件を参照）。しかし、アルゴリズムの実用化は特許を取得できる場合があります。例えば、Diamond v. Diehr事件では、合成ゴムの硬化を助けるための単純なフィードバックアルゴリズムの応用が特許取得可能と判断されました。ソフトウェアの特許取得は議論の的となっており、[ 51 ]アルゴリズム、特にUnisysのLZW特許のようなデータ圧縮アルゴリズムに関する特許は批判されています。さらに、一部の暗号アルゴリズムには輸出制限があります（暗号の輸出を参照）。

分類

実装によって

再帰
再帰アルゴリズムは、終了条件を満たすまで自身を繰り返し呼び出し、一般的な関数型プログラミング手法です。反復アルゴリズムは、ループなどの繰り返しやスタックなどのデータ構造を用いて問題を解決します。問題によっては、どちらの実装が適しているかが異なります。ハノイの塔は、一般的に再帰実装を用いて解かれるパズルです。すべての再帰バージョンには、同等の（ただし、複雑さは多少異なる）反復バージョンがあり、その逆も同様です。
直列、並列、分散
アルゴリズムは通常、逐次実行型のコンピュータではアルゴリズムの命令を 1 つずつ実行するという前提で説明されます。逐次アルゴリズムは、並列アルゴリズムや分散アルゴリズムとは異なり、これらの環境向けに設計されています。並列アルゴリズムは、複数のプロセッサが同時に問題を処理できるコンピュータ アーキテクチャを活用します。分散アルゴリズムは、コンピュータ ネットワークを介して接続された複数のマシンを使用します。並列アルゴリズムと分散アルゴリズムは、問題をサブ問題に分割し、結果をまとめて収集します。これらのアルゴリズムでのリソース消費は、各プロセッサのプロセッサ サイクルだけでなく、プロセッサ間の通信オーバーヘッドも含まれます。一部のソート アルゴリズムは効率的に並列化できますが、通信オーバーヘッドが高くなります。反復アルゴリズムは一般に並列化可能ですが、一部の問題には並列アルゴリズムが存在せず、本質的に逐次的な問題と呼ばれるものもあります。
決定論的か非決定論的か
決定論的アルゴリズムは、各ステップで正確な判断を下すことで問題を解決します。一方、非決定論的アルゴリズムは推測によって問題を解決します。推測は通常、ヒューリスティックスを用いることでより正確になります。
正確か近似か
多くのアルゴリズムは正確な解に到達するのに対し、近似アルゴリズムは真の解に近い近似値を求めます。このようなアルゴリズムは、多くの難問において実用的な価値を持ちます。例えば、ナップサック問題では、複数の品物があり、その合計値が最大になるようにナップサックに詰めることが目標となります。各品物には重さと価値があり、持ち運べる総重量は一定値X以下です。したがって、解法では品物の重さと価値の両方を考慮する必要があります。[ 52 ]
量子アルゴリズム
量子アルゴリズムは、量子計算の現実的なモデルに基づいて実行されます。この用語は通常、本質的に量子的であるように見えるアルゴリズム、または量子重ね合わせや量子もつれといった量子計算の本質的な特徴を利用するアルゴリズムに対して使用されます。

デザインパラダイムによって

アルゴリズムを分類する別の方法は、設計手法またはパラダイムによって分類することです。一般的なパラダイムには以下のようなものがあります。

総当たりまたは網羅的な検索
ブルートフォースとは、最適な解が見つかるまであらゆる選択肢を体系的に試す問題解決手法です。このアプローチは、あらゆる変数の組み合わせをテストするため、非常に時間がかかります。他の方法が利用できない場合や複雑すぎる場合によく使用されます。ブルートフォースは、2点間の最短経路の探索やパスワードの解読など、さまざまな問題を解決できます。
分割して征服する
分割統治アルゴリズムは、問題を 1 つ以上のより小さなインスタンスに繰り返し縮小し (通常は再帰的に)、インスタンスが簡単に解けるほど小さくなるまで続けます。マージ ソートは分割統治の一例であり、順序なしリストが繰り返し小さなリストに分割され、同じ方法でソートされてからマージされます。[ 53 ]分割統治のより単純な変種であるプルーン アンド 検索または減少統治アルゴリズムでは、それ自体の 1 つの小さなインスタンスが解決され、マージ ステップは必要ありません。[ 54 ]プルーン アンド 検索アルゴリズムの一例としては、バイナリ検索アルゴリズムがあります。
検索と列挙
多くの問題（例えばチェスのプレイ）はグラフ上の問題としてモデル化できます。グラフ探索アルゴリズムはグラフ上の移動規則を規定し、このような問題に役立ちます。このカテゴリには、探索アルゴリズム、分枝限定列挙法、バックトラッキングも含まれます。
ランダム化アルゴリズム
このようなアルゴリズムは、いくつかの選択をランダム（または擬似ランダム）に行う。正確な解を求めるのが現実的でない場合に、近似解を求める（以下のヒューリスティックな方法を参照）。問題によっては、最速の近似解を得るにはある程度のランダム性が必要となる。[ 55 ]多項式時間計算量を持つランダム化アルゴリズムが、ある問題に対して最速のアルゴリズムとなり得るかどうかは、P対NP問題として知られる未解決の問題である。このようなアルゴリズムには、大きく分けて2つの種類がある。
  1. モンテカルロアルゴリズムは高い確率で正解を返します。例えば、RPは多項式時間で実行されるこれらのサブクラスです。
  2. ラスベガス アルゴリズムは常に正しい答えを返しますが、その実行時間は確率的に制限されます (例: ZPP )。
複雑さの軽減
この手法は、難問を、（うまくいけば）漸近的に最適なアルゴリズムで解ける、よりよく知られた問題へと変換します。目標は、結果として得られる縮約アルゴリズムによって複雑性が支配されない縮約アルゴリズムを見つけることです。例えば、ある選択アルゴリズムは、まずリスト（コストの高い部分）をソートし、次にソート済みリストの中央の要素（コストの低い部分）を取り出すことで、ソートされていないリストの中央値を求めます。この手法は「変換統治法」とも呼ばれます。
バックトラッキング
このアプローチでは、複数のソリューションが段階的に構築され、有効な完全なソリューションに到達できないと判断された時点で放棄されます。

最適化問題

最適化問題の場合、アルゴリズムのより具体的な分類があります。このような問題のアルゴリズムは、上記の一般的なカテゴリの 1 つ以上と、次のいずれかに分類される可能性があります。

線形計画法
線形等式制約および不等式制約で制限された線形関数の最適解を探す場合、制約を直接使用して最適解を生成することができます。このカテゴリのあらゆる問題を解決できるアルゴリズムがあり、よく知られている単体アルゴリズムなどがあります。[ 56 ]線形計画法で解決できる問題には、有向グラフの最大フロー問題があります。問題が未知数のいずれかが整数であることも要求する場合、その問題は整数計画法に分類されます。整数値に対する制約がすべて表面的である、つまり解がいずれにせよこれらの制約を満たすことが証明できれば、線形計画法アルゴリズムでそのような問題を解決できます。一般的には、問題の難易度に応じて、専用のアルゴリズムまたは近似解を見つけるアルゴリズムが使用されます。
動的計画法
問題が最適なサブ構造 (つまり、最適解はサブ問題への最適解から構築できる) と重複するサブ問題(同じサブ問題が多くの異なる問題インスタンスの解決に使用されている)を示す場合、動的計画法と呼ばれるより迅速なアプローチにより、解の再計算を回避できます。たとえば、フロイド–ワーシャル アルゴリズムでは、重み付きグラフの開始頂点と目標頂点間の最短経路は、すべての隣接する頂点から目標への最短経路を使用して見つけることができます。動的計画法とメモ化は連携して行われます。分割統治法とは異なり、動的計画法のサブ問題は重複することがよくあります。動的計画法と単純な再帰の違いは、再帰呼び出しのキャッシュまたはメモ化です。サブ問題が独立していて繰り返されない場合、メモ化は役に立ちません。したがって、動的計画法はすべての複雑な問題に適用できるわけではありません。メモ化動的計画法を使用すると、多くの問題の複雑性が指数関数的から多項式的へと軽減されます。
貪欲な方法
貪欲アルゴリズムは、動的計画法と同様に、問題ではなく与えられた解の部分構造を調べることで機能します。このようなアルゴリズムは、ある解から始めて、小さな修正を加えることでそれを改善していきます。問題によっては、常に最適な解が見つかりますが、他の問題では局所最適解で止まることもあります。貪欲アルゴリズムの最も一般的な用途は、負の閉路を持たないグラフの最小全域木を見つけることです。ハフマン木、クラスカル木、プリム木、ソリン木は、この最適化問題を解くことができる貪欲アルゴリズムです。
ヒューリスティックな方法
最適化問題において、最適解を見つけることが実際的でない場合、ヒューリスティック アルゴリズムによって最適解に近い解が見つかります。これらのアルゴリズムは、処理が進むにつれて最適解にどんどん近づいていきます。原則として、無限の時間実行すると最適解が見つかります。理想的には、比較的短時間で最適解に非常に近い解を見つけることができます。これらのアルゴリズムには、局所探索、タブー探索、焼きなまし法、遺伝的アルゴリズムなどがあります。焼きなまし法のように非決定論的なアルゴリズムもあれば、タブー探索のように決定論的なアルゴリズムもあります。最適でない解の誤差の境界がわかっている場合、アルゴリズムはさらに近似アルゴリズムに分類されます。

例

最も単純なアルゴリズムの一つは、ランダムな順序の数字のリストの中から最大の数字を見つけるというものです。この解を見つけるには、リスト内のすべての数字を調べる必要があります。このことから、平易な言葉で次のように説明できる単純なアルゴリズムが導き出されます。

高レベルの説明:

  1. 数字のセットが空の場合、最高数字は存在しません。
  2. セット内の最初の数字が最大であると仮定します。
  3. セット内の残りの数字ごとに、この数字が現在の最大値より大きい場合、それが新しい最大値になります。
  4. セット内にチェックされていない数字が残っていない場合は、現在の最大数字をセット内の最大数字とみなします。

(準)正式な説明: 散文で書かれていますが、コンピュータ プログラムの高級言語に非常に近い、擬似コードまたはピジン コードでアルゴリズムをより正式にコーディングしたものが次のものです。 

アルゴリズムLargestNumber 入力: 数値のリストL。 出力: リストL内の最大の数値。 
L.size = 0の場合null を返す最大← L [0] Lの各項目 について、項目>最大の場合、最大←項目最大を返す
  • 「←」は代入を表します。例えば、「biggest ← item 」は、 biggest の値がitemの値に変更されることを意味します。
  • 「return」はアルゴリズムを終了し、次の値を出力します。

参照

注記

  1. ^ a b「ALGORITHMの定義」。メリアム・ウェブスターオンライン辞書。2020年2月14日時点のオリジナルよりアーカイブ。 2019年11月14日閲覧。
  2. ^ a b David A. Grossman、Ophir Frieder、『情報検索：アルゴリズムとヒューリスティックス』第2版、2004年、ISBN 1402030045
  3. ^「たとえば、古典的な数学アルゴリズムはすべて、有限個の英語の単語で記述できます」(Rogers 1987:2)。
  4. ^アルゴリズムを実行するエージェントについては明確に定義されています。「通常は人間である計算エージェントが存在し、命令に反応して計算を実行できます」(Rogers 1987:2)。
  5. ^「アルゴリズムとは（整数の選択された表記法に関する）関数を計算する手順である...この（数値関数への）制限によって一般性が失われることはない」（Rogers 1977:1）。
  6. ^「アルゴリズムには0 個以上の入力、つまりアルゴリズムが開始する前に最初に与えられる量があります」(Knuth 1973:5)。
  7. ^「有限性がない可能性があることを除いてアルゴリズムのすべての特徴を備えた手順は、「計算方法」と呼ばれることがあります」（Knuth 1971:5）。
  8. ^「アルゴリズムには 1 つ以上の出力、つまり入力に対して特定の関係を持つ量があります」(Knuth 1973:5)。
  9. ^ランダムな内部プロセス（入力を含まない）を持つプロセスがアルゴリズムであるかどうかは議論の余地がある。ロジャーズは次のように述べている。「計算は、連続的な手法やアナログデバイスを用いることなく、離散的なステップバイステップの方法で実行される…サイコロなどのランダムな手法やデバイスに頼ることなく、決定論的に進められる」（Rogers 1987:2）。
  10. ^ブレア, アン, デュギッド, ポール, ゴーイング, アンジャ＝シルビア, グラフトン, アンソニー. 『インフォメーション：歴史のコンパニオン』プリンストン：プリンストン大学出版局, 2021年, 247頁
  11. ^ 「アルゴリズム」 .オックスフォード英語辞典. 2025年5月18日閲覧。
  12. ^チョーサー、ジェフリー. 「粉屋の物語」 . 3210行目.
  13. ^スキート、ウォルター・ウィリアム (1914) 「agrim, agrum」。アンソニー・ローソン・メイヒュー編『チューダー朝とスチュアート朝の言葉集：特に劇作家の言葉から』クラレンドン・プレス、  5～ 6頁。
  14. ^グラビナー, ジュディス・V. (2013年12月). 「リベラルアーツ教育における数学の役割」. マシューズ, マイケル・R. (編). 『歴史・哲学・科学教育研究の国際ハンドブック』 . シュプリンガー. pp.  793– 836. doi : 10.1007/978-94-007-7654-8_25 . ISBN 9789400776548。
  15. ^ 「アルゴリズム」 .オックスフォード英語辞典. 2025年5月18日閲覧。
  16. ^ストーン（1971）、8ページ。
  17. ^シマノウスキー、ロベルト（2018年）『死のアルゴリズムとその他のデジタルジレンマ』『不時な瞑想』第14巻。チェイス、ジェファーソン訳。マサチューセッツ州ケンブリッジ：MITプレス。147ページ。ISBN 9780262536370. 2019年12月22日時点のオリジナルよりアーカイブ。2019年5月27日閲覧。[...] 中央官僚機構の抽象化の次のレベル：グローバルに動作するアルゴリズム。
  18. ^ディートリッヒ, エリック (1999). 「アルゴリズム」. ロバート・アンドリュー・ウィルソン, フランク・C. キール (編). 『MIT認知科学百科事典』 . MIT Cognetライブラリ. マサチューセッツ州ケンブリッジ: MIT Press (2001年出版). p. 11. ISBN 9780262731447. 2020年7月22日閲覧。アルゴリズムとは、何かを行うためのレシピ、方法、またはテクニックのことです。
  19. ^ストーンは「有限数のステップで終了しなければならない」ことを要求している（ストーン1973：7–8）。
  20. ^ BoolosとJeffrey 1974、1999:19
  21. ^ a b c dジャン＝リュック・シャベール（2012年）『アルゴリズムの歴史：小石からマイクロチップまで』シュプリンガー・サイエンス＆ビジネス・メディア、  7～ 8頁。ISBN 9783642181924。
  22. ^ a b Sriram, MS (2005). 「インド数学におけるアルゴリズム」 . Emch, Gerard G.; Sridharan, R.; Srinivas, MD (編).インド数学史への貢献. Springer. p. 153. ISBN 978-93-86279-25-5。
  23. ^林 徹 (2023年1月1日).ブラフマグプタ. ブリタニカ百科事典.
  24. ^ザスラフスキー、クラウディア (1970). 「ナイジェリア南部のヨルバ族とその近隣住民の数学」 . 2年制大学数学ジャーナル. 1 (2): 76– 99. doi : 10.2307/3027363 . ISSN 0049-4925 . JSTOR 3027363 .  
  25. ^ a b cクック、ロジャー・L. (2005). 『数学の歴史：簡潔な講座』 ジョン・ワイリー・アンド・サンズ. ISBN 978-1-118-46029-0。
  26. ^シャベール、ジャン＝リュック編。 （1999年）。アルゴリズムの歴史。土井：10.1007/978-3-642-18192-4。ISBN 978-3-540-63369-3。
  27. ^ a bドゥーリー、ジョン・F. (2013).暗号学と暗号アルゴリズムの簡潔な歴史. シュプリンガー・サイエンス＆ビジネス・メディア. pp.  12–3 . ISBN 9783319016283。
  28. ^ Knuth, Donald E. (1972). 「古代バビロニアのアルゴリズム」(PDF) . Commun. ACM . 15 (7): 671– 677. doi : 10.1145/361454.361514 . ISSN 0001-0782 . S2CID 7829945. 2012年12月24日時点のオリジナル(PDF)からのアーカイブ。  
  29. ^アボエ、アスガー（2001年）『天文学初期史のエピソード』ニューヨーク：シュプリンガー、  pp.40-62、ISBN 978-0-387-95136-2。
  30. ^ Ast, Courtney. 「エラトステネス」ウィチタ州立大学：数学・統計学部. 2015年2月27日時点のオリジナルよりアーカイブ。 2015年2月27日閲覧。
  31. ^ボルター 1984:24
  32. ^ボルター 1984:26
  33. ^ボルター 1984:33–34、204–206。
  34. ^ベルとニューウェルの図 1971:39、デイビス 2000 参照
  35. ^メリナ・ヒル、バレー・ニュース特派員、「ティンカーラーが歴史に名を残す」、バレー・ニュース・ウェスト・レバノン、NH、1983年3月31日木曜日、13ページ。
  36. ^デイビス 2000:14
  37. ^クリーネ 1943、デイビス 1965:274
  38. ^ Rosser 1939、Davis 1965:225
  39. ^ a b c dシプサー 2006:157
  40. ^ Kriegel, Hans-Peter ; Schubert, Erich ; Zimek, Arthur (2016). 「実行時評価の（ブラック）アート：比較しているのはアルゴリズムか実装か？」Knowledge and Information Systems . 52 (2): 341– 378. doi : 10.1007/s10115-016-1004-2 . ISSN 0219-1377 . S2CID 40772241 .  
  41. ^ Gillian Conahan (2013年1月). 「Better Math Makes Faster Data Networks」 . discovermagazine.com. 2014年5月13日時点のオリジナルよりアーカイブ。 2014年5月13日閲覧。
  42. ^ Haitham Hassanieh、 Piotr Indyk、Dina Katabi、Eric Price、「 ACM-SIAM Symposium On Discrete Algorithms (SODA)」 、2013 年 7 月 4 日アーカイブ、 Wayback Machine、京都、2012 年 1 月。sFFT Web ページ も参照してください ( 2012 年 2 月 21 日アーカイブ、 Wayback Machine )。
  43. ^ 「ベストケース」 .アルゴリズムとデータ構造の辞書. 米国国立標準技術研究所 (NIST). 米国国立標準技術研究所. 2025年5月29日閲覧。
  44. ^ 「最悪のケース」。アルゴリズムとデータ構造の辞書。米国国立標準技術研究所（NIST）。2025年5月29日閲覧。
  45. ^ Goodrich, Michael T. ; Tamassia, Roberto (2002). 『アルゴリズム設計：基礎、分析、そしてインターネットの事例』 John Wiley & Sons, Inc. ISBN 978-0-471-38365-9. 2015年4月28日時点のオリジナルよりアーカイブ。2018年6月14日閲覧。
  46. ^ 「Big-O記法（記事）| アルゴリズム」カーンアカデミー。2024年6月3日閲覧。
  47. ^ジョン・G・ケメニーとトーマス・E・カーツ1985年『Back to Basic: The History, Corruption, and Future of the Language』、Addison-Wesley Publishing Company, Inc.、マサチューセッツ州リーディング、 ISBN 0-201-13433-0。
  48. ^タウスワース 1977:101
  49. ^タウスワース 1977:142
  50. ^ Knuth 1973 セクション 1.2.1、Tausworthe 1977 により 100 ページ以降と第 9.1 章で拡張
  51. ^ 「専門家：特許制度はイノベーションを促進するのか？」ウォール・ストリート・ジャーナル。2013年5月16日。ISSN 0099-9660 。2017年3月29日閲覧。 
  52. ^ケラー、ハンス;フェルシー、ウルリッヒ。デイビッド・パイジンジャー (2004)。ナップザックの問題 |ハンス・ケラー |スプリンガー。スプリンガー。土井: 10.1007/978-3-540-24777-7。ISBN 978-3-540-40286-2. S2CID  28836720 . 2017年10月18日時点のオリジナルよりアーカイブ。2017年9月19日閲覧。
  53. ^ Goodrich, Michael T.; Tamassia, Roberto (2001). 「5.2 分割統治」.アルゴリズム設計：基礎、分析、そしてインターネットの事例. John Wiley & Sons. p. 263. ISBN 9780471383659。
  54. ^ Goodrich & Tamassia (2001)、p. 245、4.7.1 プルーンアンドサーチ。
  55. ^例えば、凸多面体の体積（メンバーシップオラクルを用いて記述される）は、ランダム多項式時間アルゴリズムによって高精度に近似できますが、決定論的アルゴリズムでは近似できません。Dyer , Martin; Frieze, Alan; Kannan, Ravi (1991年1月). "A Random Polynomial-time Algorithm for approximating the Volume of Convex Bodies". J. ACM . 38 (1): 1– 17. CiteSeerX 10.1.1.145.4600 . doi : 10.1145/102782.102783 . S2CID 13268711 .  
  56. ^ George B. DantzigとMukund N. Thapa. 2003. Linear Programming 2: Theory and Extensions . Springer-Verlag.

参考文献

さらに読む

無料辞書のウィクショナリーでアルゴリズムを調べてください。
Wikibooksにはアルゴリズムに関する本があります
ウィキバーシティでは、アルゴリズム学科でアルゴリズムについてさらに学び、他の人に教えることができます。
ウィキメディア コモンズには、アルゴリズムに関連するメディアがあります。
アルゴリズムリポジトリ
「 https://en.wikipedia.org/w/index.php?title=アルゴリズム&oldid= 1332362226」より取得