JavaScript 技術 データ構造 アルゴリズム

JavaScriptにおけるデータ構造とアルゴリズム

✍🏼 作成日 2019年10月07日   
❗️ 注意：この記事が作成されてから既に 日が経過しています。情報の鮮度にご注意ください

はじめに

自分が努力していることは自覚しており、大企業にも入社したことがあります。しかし、コンピュータサイエンスの基礎がずっと弱いと感じていました。専門的な教育を受けていないため、専門出身の同僚との差を埋めたいという思いが強く、プログラマーの三大夢（言語/アルゴリズム/グラフィックス）の一つであるデータ構造とアルゴリズムは常に心の悩みでした。暇な時間に技術コミュニティを閲覧していると、データ構造やアルゴリズムに関するセンセーショナルなタイトルに引き寄せられ、クリックしても中身が空っぽなことが多々ありました。そこで、ついにアルゴリズム（基礎）をしっかり学ぶことを決意しました。

この記事は、私が学んだ内容をまとめたもので、『JavaScriptデータ構造とアルゴリズムの学習（第2版）』を読んだ際のまとめとメモです。まずデータ構造から始め、その後データ構造のさまざまなアルゴリズムを扱います。大部分はES5のメソッドを使用し、一部ES6のメソッドを使用しています。効果の実現に重点を置き、実行コストなどの関連しない問題（例えば、プロトタイプチェーンではなく各インスタンスにメソッドを追加するなど）は考慮していません。

スタック

スタックの基本概念とメソッド

スタックは後入れ先出し（LIFO）の原則に従う順序付けられたコレクションです。新しく追加または削除される要素はスタックの一端に保存され、これをスタックトップと呼び、もう一端をスタックボトムと呼びます。スタックでは、新しい要素はスタックトップに近く、古い要素はスタックボトムに近くなります。具体的な例としては本の積み重ねが挙げられます。スタックデータ構造には以下のメソッドがあります：

  1. push(element) 一つまたは複数の要素を追加
  2. pop() スタックトップの要素を削除し、削除された要素を返す
  3. peek() スタックトップの要素を返すが、元のスタックは変更しない
  4. isEmpty() スタックが空かどうかを判定
  5. clear() スタックを空にする
  6. size() スタック内の要素数を返す

スタックのJavaScript実装

  1. スタック

スタックの応用

  1. 10進数から2進数への変換
  2. ハノイの塔

キュー

キューの基本概念とメソッド

キューはFIFO（First In First Out、先入れ先出し）の原則に従う順序付けられた項目の集まりです。キューは末尾に新しい要素を追加し、先頭から要素を削除します。最新に追加された要素はキューの末尾に配置されます。キューデータ構造には以下のメソッドがあります：

  1. enqueue(element) キューの末尾に一つ（または複数）の新しい項目を追加
  2. dequeue() キューの最初の項目（最も早く追加された要素）を削除し、削除された要素を返す
  3. front() キューの最初の要素（最も早く追加された要素）を返すが、キューは変更しない
  4. isEmpty() キューが空かどうかを返す
  5. size() キューの要素数を返す

キューのJavaScript実装

  1. キュー
  2. 優先度付きキュー

リンクリスト

リンクリストの基本概念とメソッド

リンクリストの各項目は自身の値だけでなく、次の項目の位置を指すポインタも保持しています。これを単方向リンクリストと呼びます。各項目が次の項目の位置を指すポインタに加えて、前の項目を指すポインタも保持している場合（先頭/末尾の項目を除き、それらの前/次のポインタはnull）、これを双方向リンクリストと呼びます。双方向リンクリストの先頭と末尾が接続されている場合、双方向循環リンクリストと呼びます。以下のようになります（矢印はポインタで、矢印の尾部の項目の一部です）：

  1. 単方向リンクリスト
    graph RL
A(Tail) --> B(第三项) --> C(第二项) --> D(Head)
  2. 双方向リンクリスト
    graph LR
A(Head) --> B(第二项) --> A
B --> C(第三项) --> B
C --> D(Tail) --> C
  3. 循環リンクリスト
    graph LR
A(Head) --> B(第二项) --> A
B --> C(第三项) --> B
C --> D(Tail) --> C
A --> D --> A

リンクリストには以下のメソッドがあります：

  1. append(element) リストの末尾に新しい要素を追加
  2. insert(position, element) リストの指定位置に新しい要素を挿入
  3. remove(element) リストから要素を削除
  4. indexOf(element) 要素のインデックスを返す（存在しない場合は-1）
  5. removeAt(position) 指定位置の要素を削除
  6. isEmpty() リストが空かどうかを判定
  7. size() リストの要素数を返す

リストのJavaScript実装

  1. 単方向リスト{:data-open=“”}
  2. 双方向リスト{:data-open=“”}
  3. 循環リスト{:data-open=“”}

集合

集合の基本概念とメソッド

集合は順序付けられず、かつ一意（重複不可）の要素で構成されます。集合には以下のメソッドがあります:

  1. add(value) 集合に新しい要素を追加
  2. remove(value) 集合から要素を削除
  3. has(value) 要素が集合に含まれるか判定
  4. clear() 集合を空にする
  5. size() 集合の要素数を返す
  6. values() 集合の全要素を配列で返す
  7. union(set) 別の集合との和集合
  8. intersection(set) 別の集合との積集合
  9. difference(set) 別の集合との差集合（現在の集合から指定集合を引いたもの）
  10. subset(set) ある集合が別の集合の部分集合かどうかを判定

集合のJavaScript実装

通常はオブジェクトまたはES6のSetを使用して実装（詳細は割愛）

辞書

辞書の基本概念

集合が互いに異なる要素の集まりを表すのに対し、辞書は{キー: 値}の形式でデータを格納します。辞書は「マップ」とも呼ばれ、一般的に以下のメソッドを持ちます:

  1. set(key, value) 辞書に要素を追加
  2. delete(key) 指定キーの要素を削除
  3. has(key) 指定キーが辞書に存在するか判定
  4. get(key) 指定キーに対応する値を取得
  5. clear() 辞書を空にする
  6. size() 辞書の要素数を返す
  7. keys() 辞書内の全キーを配列で返す
  8. values() 辞書内の全値を配列で返す

辞書のJavaScript実装

（割愛）

ハッシュテーブル

ハッシュテーブル（HashTable: 配列実装、HashMap: オブジェクト実装）は、辞書データ構造のハッシュ実装です。辞書で要素を検索する場合、最悪のケースではデータ構造全体を走査する必要がありますが、ハッシュテーブルとハッシュアルゴリズムを使用すれば値の正確な位置がわかるため、高速に検索できます。ハッシュ関数の役割は、与えられたキー値から、ハッシュテーブル内のアドレスを返すことです。

ハッシュテーブルの用途

あなたはこう尋ねるかもしれません、なぜハッシュテーブルが必要なのでしょうか？JavaScriptでは、オブジェクトを直接使ってキーと値のマッピングを取得すれば、O(1)の速度で済むのではないか、と。その通りですが、もし重複するキーがあった場合どうするでしょうか？例えば、異なる生徒の情報を記録する名簿を作りたいとします。同じ名前の生徒がいたらどうしますか？このとき、各生徒の名前を入力として、出力がすべてユニークになるようなアルゴリズムが必要です。これによって一対一対応が実現でき、O(1)のアルゴリズムが可能になります。これを完全ハッシュと呼び、数学的には全単射関数と言います。しかし、これで数百万のデータを保存すると、Objectオブジェクトが非常に巨大になり、パフォーマンスの問題が生じます。そのため、時間と空間のバランスを取るためにハッシュアルゴリズムが必要です。

先ほどの名簿の例で言えば、同じ名前の生徒がいる場合、依然としてその名前をキーとしますが、値は単一の生徒情報ではなく、生徒情報の配列（またはリンクリスト）になります。生徒名が与えられた後、対応する値が配列であることがわかったら、その配列を走査して正確な生徒情報を見つけます。これにより、時間（以前のO(1)より長い ❌）と空間（以前のObjectオブジェクトが占める空間より小さい ✅）のバランスが取れます。優れたハッシュアルゴリズムは、各キー上の配列の大きさがほぼ同じになるように保証するべきです。

ハッシュテーブルの基本メソッド

  1. put(key, value) ハッシュテーブルに新しい項目を追加
  2. remove(key) キーに基づいてハッシュテーブルから項目を削除
  3. get(key) キーに基づいて項目を検索

最もシンプルなハッシュ関数

入力が文字列の場合を例に、同じ文字列は一時的に考慮せず、データ構造として配列を使用。これにより、keyをキーとして使用可能

1
2
3
4
5
6
7
let loseloseHashCode = function (key) {
  let hash = 0;
  for (let i = 0; i < key.length; i++) {
    hash += key.charCodeAt(i);
  }
  return hash % 37;
};

ハッシュテーブルにおける衝突の解決

上記のハッシュアルゴリズムからわかるように、計算されたキーは衝突する可能性があります。つまり、配列内で同じkeyに異なる値が割り当てられる可能性があり、上書きされてしまいます。そのため、衝突を解決する必要があります。3つの方法があります：

  1. 分離連鎖法 ハッシュアルゴリズムで生成されたキーが同じ場合、キーは直接値を指すのではなく、配列/リンクリストを指すようにし、問題を配列/リンクリストの挿入/検索に変換
  2. 線形探査法 ハッシュアルゴリズムで生成されたキーが同じ場合、キーを自動的に+1して再度保存を試みる。それでも衝突する場合は、+1を続け、空き位置が見つかるまで繰り返す（配列のような数値キーのハッシュテーブル形式に適応）。数値キー向けのさらに優れたハッシュ実装はこちら
  3. 二重ハッシュ法 ハッシュアルゴリズムで生成されたキーが同じ場合、衝突に対して別のまたは同じハッシュ関数を使用してキーを再生成

ハッシュテーブルのJavaScript実装

  1. 通常のハッシュテーブル実装
  2. 分離連鎖法
  3. 線形探査法

木

木に関する用語

まず構造の示意图を見てください：

graph TD;
    11---7;
    11---15;
    7---5;
    7---9;
    5---3;
    5---6;
    9---8;
    9---10;
    15---13;
    15---20;
    13---12;
    13---14;
    20---18;
    20---25;

この中で：

  1. 11は第0層、7/15は第1層、5/9/13/20は第2層、他は第3層
  2. 11を根ノード、他を子ノードと呼びます。少なくとも1つの子ノードを持つノードを内部ノード、子要素を持たないノードを外部ノードと呼びます
  3. ノードには深さ属性があり、例えばノード3には3つの祖先要素があるため、深さは3です
  4. 木の高さはすべてのノードの深さの最大値によって決まります
  5. これは完全二分木です。なぜなら、最下層のノード以外はすべて2つのノードを持っているからです

注意：同じデータでも複数の木構造が存在する可能性があり、必ずしも唯一の表現形式ではありません。そのため、次の節のAVL木があります—データを可能な限り完全な木に構築するためのものです

二分木と二分探索木

二分木のノードは最大2つの子ノードを持ちます。1つは左側の子ノード、もう1つは右側の子ノードです。二分探索木(BST)は二分木の一種ですが、任意のノードの左側にはそのノードより小さい値のみを格納し、右側にはそのノードより大きいまたは等しい値を格納するという制約があります。図中の木は二分探索木で、以下のメソッドを持ちます:

  1. insert(key) 新しいノードを挿入
  2. search(key) ノードを検索またはnullを返す
  3. inOrderTraverse 中順走査で全てのノードを訪問
  4. preOrderTraverse 前順走査で全てのノードを訪問
  5. postOrderTraverse 後順走査で全てのノードを訪問
  6. min 木中の最小値を返す
  7. max 木中の最大値を返す
  8. remove(key) 木からノードを削除

木の走査図示:

  1. 中順走査—木のソート操作によく使用

    graph TD;
    11---7;
    11---15;
    7---5;
    7---9;
    5---3;
    5---6;
    9---8;
    9---10;
    15---13;
    15---20;
    13---12;
    13---14;
    20---18;
    20---25;
    3-.->5
    5-.->6;
    6-.->7;
    7-.->8;
    8-.->9;
    9-.->10;
    10-.->11;
    11-.->12;
    12-.->13;
    13-.->14;
    14-.->15;
    15-.->18;
    18-.->20;
    20-.->25;

    走査順序:3 5 6 7 8 9 10 11 12 13 14 15 18 20 25

  2. 前順走査—構造化されたドキュメントの印刷によく使用。図中の走査順序:11 7 5 3 6 9 8 10 15 13 12 14 20 18 25

  3. 後順走査—ディレクトリとそのサブディレクトリ内の全ファイルのサイズ計算に適用。図中の走査順序:3 6 5 8 10 9 7 12 14 13 18 25 20 15 11

Adelson-Velskii-Landi木(AVL木)

AVL木は自己平衡木です。二分木は状況によって片側の部分木が深くなりすぎ、他の部分木が浅くなりすぎることがあります。下図のように:

graph TD;
    11---7;
    11---15;
    7---5;
    7---9;
    5---3;
    5---6;
    9---8;
    9---10;
    15---13;
    15---20;
    13---12;
    13---14;
    20---18;
    20---25;
    25---27
    27---30

この木は右側が深すぎ、ノードの検索・追加・削除時に性能問題を引き起こす可能性があるため、AVL自己平衡木が必要です。AVLは自己平衡二分探索木で、任意のノードの左右部分木の高さ差が最大1であることを意味します。つまり、この木はノードの追加・削除時に完全木に近づこうとします。

AVL木の平衡係数と計算

AVL木へのノード挿入・削除はBSTと全く同じですが、AVLの違いは挿入/削除時に平衡係数をチェックし、必要に応じて木の自己平衡を行う点です。AVL木では各ノードについて右部分木高さ(hr)と左部分木高さ(hl)の差を計算し、この値(hr-hl)が0/1/-1のいずれでもない場合、AVL木を平衡化する必要があります。これが平衡係数の概念です。以下の3つの木は全て平衡しています:

graph TD;
    subgraph 第三种
        A((+1))---B(( -1))
        A---C(( -1))
        B---E((0))
        C---D((+1))
        C---F((0))
        D---H((0))
    end
    subgraph 第二种
        I((+1))---G((0))
        I---K(( -1))
        K---L((0))
    end
    subgraph 第一种
        M(( -1))---N((0))
    end

AVL木の回転

AVL木にノードを挿入する際、単回転または双回転の2種類の平衡操作を行えます。それぞれ4つのシナリオに対応:

  1. 右---右(RR) 左への単回転
  2. 左---左(LL) 右への単回転
  3. 左---右(LR) 右への双回転
  4. 右---左(RL) 左への双回転

右—右(RR): 左への単回転図(mermaid描画で二分木として正しく表現できず80が左、50が右に):

graph TD;
    subgraph 之后
        G((70))---H((50))
        G---I((80))
        I---J((90))
        H---K((30))
        H---L((60))
    end
    subgraph 之前
        A((50))---B((30))
        A---C((70))
        C---D((60))
        C---E((80))
        E---F((90))
    end

左—左(LL): 右への単回転図(mermaid描画で二分木として正しく表現できず50が左、10が右に):

graph TD;
    subgraph 之后
        G((30))---H((10))
        G---I((50))
        I---J((40))
        I---K((70))
        H---L((5))
    end
    subgraph 之前
        A((50))---C((30))
        A---B((70))
        C---D((10))
        C---E((40))
        D---F((5))
    end

左—右(LR): 右への双回転図(基本的にRR回転を1回、その後LL回転を1回行う):

graph TD;
    subgraph 之后
        G((40))---H((30))
        G---I((50))
        H---J((10))
        H---K((35))
        J---L((70))
    end
    subgraph 之前
        A((50))---C((30))
        A---B((70))
        C---D((10))
        C---E((40))
        E---F((35))
    end

右—左(RL): 左への双回転図(基本的にLL回転を1回、その後RR回転を1回行う、mermaid描画で二分木として正しく表現できず80が左、70が右に):

graph TD;
    subgraph 之后
        G((72))---I((70))
        G---H((80))
        H---J((75))
        H---K((90))
        I---L((50))
    end
    subgraph 之前
        A((70))---B((50))
        A---C((80))
        C---D((72))
        C---E((90))
        D---F((75))
    end

AVL木は自己平衡化されていますが、ノードの挿入や削除の性能が常に最良とは限りません。より優れた選択肢は赤黒木で、赤黒木はノードを効率的に順序通りに走査できます。

木の基本メソッドのJavaScript実装

  1. 二分木
  2. AVL木
  3. 赤黒木
  4. ヒープ木

グラフ

グラフの基本概念

グラフはネットワーク構造の抽象モデルです。グラフは辺で接続されたノード（または頂点）の集合を表します。あらゆる二項関係はグラフで表現できます。グラフを使用して、2点間の最短経路などの問題を解決できます。

グラフの数学的概念

グラフG=(V, E)は以下の要素で構成されます

  1. V: 頂点の集合
  2. E: Vの頂点を接続する辺の集合

以下はグラフの表現です:

graph TD;
    A---B
    B---E
    B---F
    E---I
    A---C
    A---D
    C---D
    C---G
    D---G
    D---H

グラフ関連の用語

上記のグラフにおいて:

  1. 1つの辺で接続された頂点を隣接頂点と呼ぶ
  2. 頂点の次数は隣接頂点の数で、上図ではAは他の3頂点と隣接しているためAの次数は3; Eの次数は2
  3. 経路は頂点v1, v2,…vkの連続するシーケンスで、viとv(i+1)は隣接している。上図にはABEIやACDGといった経路が含まれる
  4. 単純経路は重複する頂点を含まない。例えばADGは単純経路。最後の頂点を除いて（最初の頂点と同じ頂点に戻るため）、環も単純経路となる。例: ADCA（最後の頂点がAに戻る）
  5. グラフに環が存在しない場合、そのグラフは非環状である。グラフの任意の2頂点間に経路が存在する場合、そのグラフは連結している
  6. グラフは有向（辺に方向がある）または無向（辺に方向がない）にできる。上図は無向グラフ
  7. グラフの任意の2頂点間で双方向に経路が存在する場合、そのグラフは強連結である
  8. グラフは重みなしまたは重み付きにできる。重み付きグラフでは辺に重みが割り当てられる

グラフの表現方法

隣接行列

グラフの最も一般的な実装は隣接行列です。各ノードは整数と関連付けられ、その整数が配列のインデックスとして使用されます。頂点間の接続を2次元配列で表現します。インデックスiのノードとインデックスjのノードが隣接している場合、array[i][j] === 1、そうでなければarray[i][j] === 0となります。上記のグラフを隣接行列で表現すると:

A B C D E F G H I
A 0 1 1 1 0 0 0 0 0
B 1 0 0 0 1 1 0 0 0
C 1 0 0 1 0 0 1 0 0
D 1 0 1 0 0 0 1 1 0
E 0 1 0 0 0 0 0 0 1
F 0 1 0 0 0 0 0 0 0
G 0 0 1 1 0 0 0 0 0
H 0 0 0 1 0 0 0 0 0
I 0 0 0 0 1 0 0 0 0

強連結でないグラフを疎グラフと呼びます。隣接行列で表現する場合、行列には多くの0が含まれるため、実際には存在しない辺を表現するためにコンピュータの記憶領域を無駄に消費してしまいます。

隣接リスト

隣接リストは、グラフ内の各頂点に隣接する頂点のリストで構成されます。このデータ構造を表現する方法はいくつかあります。リスト（配列）/リンクリスト/さらにはハッシュテーブルや辞書を使って隣接頂点リストを表現できます。上記のグラフは以下の隣接リストで表現できます:

A B C D
B A E F
C A D G
D A C G H
E B I
F B
G C D
H D
I E

接続行列(略)

グラフ関連のメソッド

  1. addVertex(v) 新しい頂点を追加
  2. addEdge(v, w) 新しい辺を追加

グラフの走査

グラフの走査は、特定の頂点を探したり、2つの頂点間の経路を見つけたり、グラフが連結しているかどうかを確認したり、グラフに環が含まれているかどうかを調べるために使用できます。グラフ走査アルゴリズムの基本的な考え方は、初めて訪問した各ノードを追跡し、どのノードが完全に探索されていないか（つまり、未探索の子ノードが残っているか）を追跡することです。以下の2つの探索（走査）モードでは、最初に訪問する頂点を明確に指定する必要があります。頂点を完全に探索するには、その頂点のすべての辺を調べ、各辺で接続されている未訪問の頂点を発見済みとしてマークし、訪問待ち頂点リストに追加します。アルゴリズムの効率を保証するため、各頂点を最大2回までしか訪問しないように注意してください。連結グラフでは、すべての辺と頂点が訪問されます。頂点の訪問状態は、未訪問/訪問済みだが未探索/完全に探索済みの3つの状態で表現できます。

グラフの幅優先探索(Breadth-First Search, BFS)

訪問待ち頂点リストのデータ構造はキューで、頂点をキューに格納し、最初にキューに入った頂点から探索されます。

幅優先探索は最短経路を見つけるために使用されます（以下に実装例があります）。Dijkstraのアルゴリズムは単一始点最短経路問題を解決します（貪欲法）。Bellman-Fordのアルゴリズムは辺の重みが負の場合の単一始点最短経路問題を解決します。A*探索アルゴリズムは一対の頂点間の最短経路を求める問題に使用され、ヒューリスティックで探索を加速します。Floyd-Warshallのアルゴリズムは全頂点対間の最短経路問題を解決します（動的計画法）。

グラフの深さ優先探索(Depth-First Search, DFS)

訪問待ち頂点リストのデータ構造はスタックで、頂点をスタックに格納し、頂点は経路に沿って探索されます。新しい隣接頂点があればそれを訪問します。タスクやステップの実行順序を決定する必要がある場合、これはトポロジカルソート(topsort/toposort)と呼ばれ、深さ優先探索を使用してトポロジカルソートを行うことができます。トポロジカルソートは有向非巡回グラフ(DAG)にのみ適用可能で、以下に具体的な実装があります。

最小全域木(MST)

最小全域木はネットワーク設計でよく見られる問題です。例えば、会社に複数のオフィスがあり、電話回線を相互接続するための最低コストを実現し、資金を節約する最良の方法は何でしょうか？これは島と橋の問題にも適用できます。n個の島の間に橋を建設し、すべての島を相互接続するための最低コストを実現したい場合、これらの問題はどちらもMSTアルゴリズムで解決できます：

  1. Primのアルゴリズム

    重み付き無向連結グラフのMST問題を解決する貪欲法で、すべての頂点を含み辺の重みの合計が最小となる木を構成する辺の部分集合を見つけます。

  2. Kruskalのアルゴリズム

    上記と同様に、重み付き無向連結グラフのMST問題を解決する貪欲法です。

JavaScriptによるグラフの実装

  1. グラフ
  2. 最短経路アルゴリズム
  3. 最小全域木

ソートと探索アルゴリズム

ソートアルゴリズム

  1. バブルソート 計算量 O(n2) 二重ループで、条件を満たす場合に内側のループの2つの値を交換
  2. 選択ソート 計算量 O(n2) 二重ループで、内側のループで最小値を見つけ最初の位置に配置、次に2番目に小さい値を見つけ2番目の位置に配置
  3. 挿入ソート 計算量 O(n2) 先頭から開始し、毎回前の部分が既にソートされていると仮定し、現在の値がソート済み配列のどの位置に挿入されるかを判断し、次の値を判断
  4. マージソート 計算量 O(nlogn) 再帰的な考え方で、配列を小さな配列に分割し、各小さな配列を2つずつソート（2組の既にソートされたトランプの並べ替えのように）し、ソートが完了するまで続ける
  5. クイックソート 計算量 O(nlogn) ピボットを選択しデータを2分割、ピボットより大きい値を右側、小さい値を左側に配置し、左ポインタが右ポインタを超えるまで繰り返す
  6. ヒープソート 配列を二分木としてソート、ルールは：
    1. インデックス0が木の根ノード
    2. 根ノード以外、任意のノードNの親ノードはN/2
    3. ノードLの左子ノードは2 * L
    4. ノードRの右子ノードは2 * R + 1
    5. 配列 [3, 5, 1, 6, 4, 7, 2] は以下の木と見なせる：
      graph TD;
A((3))---B((5))
A---C((1))
B---D((6))
B---E((4))
C---F((7))
C---G((2))
  7. 計数ソート
  8. バケットソート
  9. 基数ソート（分配ソート）

探索アルゴリズム

  1. 線形探索
  2. 二分探索

ソート/サーチアルゴリズムのJavaScript実装

  1. 各種ソート/サーチアルゴリズムまとめ

アルゴリズムパターン

動的計画法

  1. ナップサック問題 価値と容量を持つアイテムの集合が与えられ、総容量がナップサックの容量以下という制約のもとで、総価値が最大となるアイテムの組み合わせを見つける
  2. 最長共通部分列 複数のシーケンスから、別のシーケンスから要素を削除しても残りの要素の順序が変わらないような最長の共通部分列を見つける
  3. 行列連鎖乗算 一連の行列が与えられ、これらの行列を乗算する最も効率的な方法（計算回数を最小化）を見つける。実際の乗算は行わず、行列を乗算する順序を見つけることが解決策
  4. コイン両替 額面d1, d2…dnのコインが一定数あり、お釣りの金額が与えられた時、お釣りの出し方が何通りあるかを求める
  5. 全点対最短経路 すべての頂点対(u, v)について、頂点uから頂点vへの最短経路を見つける（Floyd-Warshallアルゴリズムで解決可能）

アルゴリズムパターンのJavaScript実装

  1. 再帰
  2. 最小コイン両替DPアルゴリズム
  3. 最小コイン両替貪欲アルゴリズム
  4. ナップサック問題DPアルゴリズム
  5. ナップサック問題再帰アルゴリズム
  6. ナップサック問題貪欲アルゴリズム
  7. 最長共通部分列DPアルゴリズム
  8. 最長共通部分列再帰アルゴリズム
  9. 行列連鎖乗算DPアルゴリズム
  10. 行列連鎖乗算再帰アルゴリズム

NP完全理論概要

一般的に、アルゴリズムの計算量がO(nk)（kは定数）の場合、そのアルゴリズムは効率的と見なされ、多項式時間アルゴリズムと呼ばれる。与えられた問題に対して多項式時間アルゴリズムが存在する場合、それはP（polynomial、多項式）に分類される。

また、NP（nondeterministic polynomial、非決定性多項式）に分類されるアルゴリズムもある。問題の解が多項式時間で検証可能な場合、それはNPに分類される。

多項式時間アルゴリズムが存在する問題は、当然その解も多項式時間で検証可能であるため、すべてのPはNPに含まれる。しかし、P=NPが成り立つかどうかは未だにわかっていない。

NP問題の中で最も難しいのがNP完全問題で、以下の2つの条件を満たす：

  1. NP問題である（つまり解が多項式時間で検証可能）が、まだ多項式時間アルゴリズムが見つかっていない
  2. すべてのNP問題が多項式時間でこれに帰着可能

さらに、NP完全問題の2番目の条件のみを満たす問題をNP困難問題と呼ぶ。したがって、NP完全問題はNP困難問題の部分集合である。

NP完全ではないNP困難問題の例として停止問題やブール充足可能性問題(SAT)があり、NP完全問題の例としては部分和問題、巡回セールスマン問題、頂点被覆問題などがある。

最後に、前述した問題の中には解けないものもあるが、それでも要求を満たす時間内で近似解を見つける方法が存在する。ヒューリスティックアルゴリズムはその一つで、最適解ではないが問題解決に十分な解を得られる。

ヒューリスティックアルゴリズムの例には局所探索、遺伝的アルゴリズム、ヒューリスティックナビゲーション、機械学習などがある。詳細はこちらを参照

- EOF -
この記事の初出: JavaScriptにおけるデータ構造とアルゴリズム - Xheldon Blog
目次
    ブログ主より：
    人生の重要な選択に直面したとき、最善の方法を誰かが教えてくれて、貴重な時間を無駄にせずに済めばと、私はよく願っています。だからこそ、自分の経験を踏まえて頻繁にブログを書き、広大なインターネットのこの小さな片隅に、私にとって一度きりの人生経験を記録し、助けを求める人々の力になれればと思っています。
    人気のタグ
    技術 生活 いじり コツ チュートリアル 翻訳 Apple 経験 グルメ ProseMirror 初体験 ワークフロー プラグイン ネットワーク Apple Craft JavaScript Vue 使用感 まとめ サーバー ルーター ソフトルーター エッセイ 統合 Git 主食 最適化 ギガビット 大事 ツール バイパスルーター フレームワーク 足湯タイム テスト テスラ エディタ 動画 デバッグ 車 移行 AI AppleScript CI GitHub Jekyll Notion VSCode 東北料理 住宅購入 プロキシ フルスタック 北欧神話 共同編集 圧縮 クレイトス 家庭料理 富強 比較 四川料理 仕事の経験 ギリシャ神話 定番ソフト オープンソース 開封 ゴッド・オブ・ウォー SIMカード トポロジー 物語 データ構造 旅行 日常 日本 サービス フォーマット 夢 ブラウザ ゲーム 愚痴 ユーザープライバシー アルゴリズム 詳細 イヤホン 自由 計画 設定 落とし穴 変換 技術選定 面接 2022 C Chrome Clash CORS ES6 Evernote Linux Nginx Promise R4S Router SDK SlateJS SPA Swift TeslaMate Web Webpack Windows XCode
    コラム
    オープンソース 技術書リスト サブスク＆有料アプリ グルメのおすすめ
    友達