Loading article…
数学とコンピュータサイエンスにおいて、アルゴリズム技術[1]はプロセスや計算を実装するための一般的なアプローチです。[2]
一般的なテクニック
アルゴリズムを設計および構築するための実証済みの方法やプロセスを提供する、広く認知されているアルゴリズム手法がいくつかあります。目的に応じて、検索、ソート、数学的最適化、制約充足、分類、分析、予測など、さまざまな手法が使用される場合があります。[3]
力ずくで
ブルートフォースは、あらゆる可能性のある結果を評価して解決策を見つけるシンプルで徹底的な手法です。[4]
分割して征服する
分割統治法は、複雑な問題を再帰的に小さなサブ問題に分解する手法です。各サブ問題を解決し、これらの部分的な解決策を再結合して全体の解決策を決定します。この手法は、検索やソートによく使用されます。[5]
動的
動的計画法は、複雑な問題を再帰的に分解して、より小さな重複するサブ問題に分解して解決する体系的な手法です。動的計画法では、メモ化と呼ばれる最適化手法を使用して、重複するサブ問題の結果をローカルに保存します。[6]
進化論的
進化的アプローチでは、候補となる解決策を開発し、その後、生物学的進化に似た方法で、一連のランダムな変更またはこれらの解決策の組み合わせを実行し、新しい結果を適応度関数に対して評価します。最も適合性の高い、または有望な結果が追加の反復のために選択され、全体的な最適な解決策が達成されます。[7]
グラフトラバーサル
グラフトラバーサルは、グラフとして表現できる問題の解決策を見つけるための手法です。このアプローチは幅広く、深さ優先探索、幅優先探索、ツリートラバーサル、および局所最適化や、最適ではない、または不可能であると判断できる探索空間の除外など、多くの特定のバリエーションが含まれます。これらの手法は、最短経路や制約充足問題など、さまざまな問題を解決するために使用できます。 [8]
よく深い
貪欲なアプローチは、まず可能な結果の集合から 1 つの可能な結果を評価し、次にその結果の改善を局所的に検索します。局所的な改善が見つかったら、このプロセスを繰り返し、この局所最適値の近くで追加の改善を再び局所的に検索します。貪欲な手法は一般的に実装が簡単で、これらの一連の決定を使用して、検索を開始した場所に応じて局所最適値を見つけることができます。ただし、貪欲な手法では、可能な結果の集合全体にわたってグローバル最適値を特定できない場合があります。, [9]
ヒューリスティック
ヒューリスティックアプローチは、最適であるとは保証されない即時の解決策に到達するための実用的な方法を採用します。[10]
学ぶ
学習技術は、明示的なプログラミングなしで分類と分析を実行するために統計的手法を採用しています。教師あり学習、教師なし学習、強化学習、ディープラーニング技術がこのカテゴリに含まれます。[11]
数学的最適化
数学的最適化は、関数を最小化または最大化することによって数学的な最適値を計算するために使用される技術です。[12]
モデリング
モデリングは、現実世界の問題を解決を支援するフレームワークやパラダイムに抽象化する一般的な手法です。[13]
再帰
再帰は、定義された結果を持つ1つ以上の基本ケースまで、タスクの段階的に単純な部分で自分自身を呼び出すアルゴリズムを設計するための一般的な手法です。[14] [15]
窓のスライド
ウィンドウ スライディングは、ネストされたループの使用を減らして単一のループに置き換えるために使用され、それによって時間の複雑さが軽減されます。
参照
注記
- ^ 「technique | Oxford Dictionariesによる英語のtechniqueの定義」。Oxford Dictionaries | 英語。2016年9月28日時点のオリジナルよりアーカイブ。 2019年3月23日閲覧。
- ^ コーメン、トーマス H.チャールズ・E・ライザーソン;ロナルド・L・リベスト、スタイン、クリフォード (2001)。アルゴリズムの紹介。 MITプレス。 p. 9.ISBN 9780262032933。
- ^スキエナ、スティーブン S. (1998)。アルゴリズム設計マニュアル: テキスト。Springer Science & Business Media。ISBN 9780387948607。
- ^ 「ブルートフォースとは何か? Webopediaの定義」www.webopedia.com。 1998年3月30日。 2019年3月23日閲覧。
- ^ Bentley, Jon Louis; Shamos, Michael Ian (1976). 「多次元空間での分割統治」。第 8 回 ACM コンピューティング理論シンポジウム議事録 - STOC '76 。STOC '76。ニューヨーク、ニューヨーク州、米国: ACM。pp. 220–230。doi :10.1145 / 800113.803652。S2CID 6400801。
- ^ Bellman, Richard (1966-07-01). 「動的プログラミング」. Science . 153 (3731): 34–37. Bibcode :1966Sci...153...34B. doi :10.1126/science.153.3731.34. ISSN 0036-8075. PMID 17730601. S2CID 220084443.
- ^ Coello Coello, Carlos A. (1999-08-01). 「進化に基づく多目的最適化手法の包括的調査」.知識と情報システム. 1 (3): 269–308. doi :10.1007/BF03325101. ISSN 0219-3116. S2CID 195337963.
- ^クマール、ニティン、ウェイン、ケビン ( 2014-02-01 )。アルゴリズム。Addison-Wesley Professional。ISBN 9780133799101。
- ^ 「greedy algorithm」. xlinux.nist.gov . 2019年3月23日閲覧。
- ^ 「ヒューリスティック」xlinux.nist.gov . 2019年3月23日閲覧。
- ^ Witten, Ian H.; Frank, Eibe; Hall, Mark A.; Pal, Christopher J. (2016-10-01). データマイニング: 実用的な機械学習ツールとテクニック。Morgan Kaufmann。ISBN 9780128043578。
- ^ Marler, RT; Arora, JS (2004-04-01). 「エンジニアリングのための多目的最適化手法の調査」.構造および多分野最適化. 26 (6): 369–395. doi :10.1007/s00158-003-0368-6. ISSN 1615-1488. S2CID 14841091.
- ^スキエナ、スティーブン S. (1998)。アルゴリズム設計マニュアル: テキスト。Springer Science & Business Media。ISBN 9780387948607。
- ^ 「再帰」xlinux.nist.gov . 2019年3月23日閲覧。
- ^ 「プログラミング - 再帰」www.cs.utah.edu . 2019年3月23日閲覧。
外部リンク
- アルゴリズム設計とテクニック - edX
- アルゴリズム技術と分析 –カーネギーメロン大学
- 大量データのためのアルゴリズム技術 – MIT