Lainbo's Blog

再帰アルゴリズム#

アルゴリズム戦略#

再帰アルゴリズムは、自身の関数またはメソッドを直接または間接的に呼び出すアルゴリズムです。

再帰アルゴリズムの本質は、問題を規模を縮小した同類の問題の部分問題に分解し、再帰的にメソッドを呼び出して問題の解を表現することです。再帰アルゴリズムは、多くの問題を解決するのに非常に効果的で、アルゴリズムを簡潔で理解しやすくすることができます。

利点と欠点：

• 利点：実装が簡単で扱いやすい
• 欠点：再帰アルゴリズムは、通常のループなどの一般的なアルゴリズムに比べて実行効率が低い；また、再帰呼び出しの過程で、システムは各レベルの戻り点、局所変数などのためにスタックを確保するため、再帰が深すぎるとスタックオーバーフローが発生しやすい。

適用シーン#

再帰アルゴリズムは一般的に次の三つの問題を解決するために使用されます：

• データの定義が再帰的に定義されている。（フィボナッチ数列）
• 問題の解法が再帰アルゴリズムで実装されている。（バックトラッキング）
• データの構造形式が再帰的に定義されている。（木の遍歴、グラフの探索）

再帰の解法戦略：

• 第一歩：この関数の入力と出力を明確にし、関数内のコードは無視して、まずこの関数の入力が何で、出力が何で、機能が何で、どのようなことを達成するのかを理解する。
• 第二歩：再帰の終了条件を探す。再帰がいつ終了するかを見つけ、その後直接結果を返す。
• 第三歩：再帰関係式を明確にし、さまざまな再帰呼び出しを通じて現在の問題を解決する方法を組み合わせる。

再帰アルゴリズムを使用して解決するいくつかの古典的な問題#

• フィボナッチ数列
• ハノイの塔問題
• 木の遍歴および関連操作

DOM ツリーの例#

以下に DOM ツリーを例にして、document.getElementById機能を実装します。

DOM は木構造であり、木の定義自体が再帰的に定義されているため、再帰的な方法で木を処理するのは非常に簡単で自然です。

第一歩：この関数の入力と出力を明確にする

DOM ツリーの根ノードから一層ずつ再帰し、現在のノードの id が私たちが探しているid='d-cal'であるかどうかを判断します。

入力：DOM ツリーの根ノードdocument、私たちが探しているid='d-cal'

出力：id='sisteran'を満たす子ノードを返す

function getElementById(node, id){}

第二歩：再帰の終了条件を探す

document から下に向かって、すべての子ノードを再帰的に探し、その子ノードを一層ずつ探します：

• 現在のノードの id が検索条件に合致する場合、現在のノードを返します。
• もし葉ノードに達しても見つからなかった場合は、null を返します。

function getElementById(node, id){
    // 現在のノードが存在しない、葉ノードに達しても見つからなかった場合、nullを返す
    if(!node) return null
    // 現在のノードのidが検索条件に合致する場合、現在のノードを返す
    if(node.id === id) return node
}

第三歩：再帰関係式を明確にする

現在のノードの id が検索条件に合致しない場合、各子ノードを再帰的に探します。

function getElementById(node, id){
    // 現在のノードが存在しない、葉ノードに達しても見つからなかった場合、nullを返す
    if(!node) return null
    // 現在のノードのidが検索条件に合致する場合、現在のノードを返す
    if(node.id === id) return node
    // 現在のノードのidが検索条件に合致しない場合、各子ノードを探し続ける
    for(var i = 0; i < node.childNodes.length; i++){
        // 各子ノードを再帰的に探す
        var found = getElementById(node.childNodes[i], id);
        if(found) return found;
    }
    return null;
}

こうして、私たちのdocument.getElementById機能が実装されました：

function getElementById(node, id){
    if(!node) return null;
    if(node.id === id) return node;
    for(var i = 0; i < node.childNodes.length; i++){
        var found = getElementById(node.childNodes[i], id);
        if(found) return found;
    }
    return null;
}
getElementById(document, "d-cal");

再帰を使用する利点は、コードが簡単で理解しやすいことですが、欠点は非再帰的な実装に比べて効率が劣ることです。Chrome ブラウザの DOM 検索は非再帰的な実装を使用しています。非再帰的に実装するには、以下のコードのようになります：

function getByElementId(node, id){
    // すべてのノードを遍歴
    while(node){
        if(node.id === id) return node;
        node = nextElement(node);
    }
    return null;
}

すべてのDOMノードを順に遍歴しますが、今回はwhileループに変更し、関数nextElementが次のノードを見つける役割を果たします。したがって、重要なのはこのnextElementがどのように非再帰的にノードを検索する機能を実装するかです：

// 深さ優先探索
function nextElement(node){
    // まず子ノードがあるかどうかを判断
    if(node.children.length) {
        // あれば最初の子ノードを返す
        return node.children[0];
    }
    // 次に隣接ノードがあるかどうかを判断
    if(node.nextElementSibling){
        // あれば次の隣接ノードを返す
        return node.nextElementSibling;
    }
    // そうでなければ、親ノードの次の隣接要素を返す。これは上記の再帰実装のforループのiを1増やすことに相当します。
    while(node.parentNode){
        if(node.parentNode.nextElementSibling) {
            return node.parentNode.nextElementSibling;
        }
        node = node.parentNode;
    }
    return null;
}

このコードをコンソールで実行すると、同様に正しい結果が出力されます。非再帰的であれ再帰的であれ、どちらも深さ優先探索です。実際には、getElementByIdブラウザはハッシュマップを使用して、id に基づいて DOM ノードに直接マッピングしています。また、getElementsByClassNameはこのような非再帰的な検索を使用しています。

分割統治アルゴリズム#

アルゴリズム戦略#

コンピュータサイエンスにおいて、分割統治アルゴリズムは非常に重要なアルゴリズムであり、クイックソートやマージソートなどは分割統治戦略に基づいて実装されています。したがって、理解し習得することをお勧めします。

分割統治とは、分けて治すという意味であり、複雑な問題を 2 つ以上の類似の部分問題に分割し、部分問題をさらに小さな部分問題に分け、最終的に小さな部分問題を簡単に解決できるようにし、部分問題を解決することで元の問題の解を得ることです。

適用シーン#

以下の条件を満たす問題が発生した場合、分割統治戦略を使用して解決を試みることができます：

• 元の問題を複数の類似の部分問題に分割できる
• 部分問題は非常に簡単に解決できる
• 元の問題の解は部分問題の解の結合である
• 各部分問題は相互に独立しており、同じ部分問題を含まない

分割統治の解法戦略：

• 第一歩：分解し、元の問題をいくつかの規模の小さい、相互に独立した、元の問題と同じ形式の部分問題に分解する
• 第二歩：解決し、各部分問題を解決する
• 第三歩：結合し、各部分問題の解を元の問題の解に結合する

分割統治法を使用して解決するいくつかの古典的な問題#

• 二分探索
• マージソート
• クイックソート
• ハノイの塔問題
• React の時間分割

二分探索#

折半探索アルゴリズムとも呼ばれ、これはシンプルで理解しやすい迅速な探索アルゴリズムです。例えば、0 から 100 の間の数字をランダムに書き、あなたに私が書いた数字を当てさせるとします。あなたが 1 回当てるごとに、私はあなたが大きすぎるか小さすぎるかを教え、当たるまで続けます。

第一歩：分解

毎回の推測で、前回の結果を大きいグループと小さいグループに分け、両グループは相互に独立しています。

• 配列の中間数を選択します。

function binarySearch(items, item) {
    // low、mid、highで配列を2つのグループに分ける
    var low = 0,
        high = items.length - 1,
        mid = Math.floor((low + high) / 2),
        elem = items[mid]
    // ...
}

第二歩：部分問題を解決する

探している数と中間数を比較します。

• 中間数より低ければ、中間数の左側の部分配列を探します；
• 中間数より高ければ、中間数の右側の部分配列を探します；
• 等しい場合は、探索成功を返します。

while(low <= high) {
    if(elem < item) { // 中間数より高い
        low = mid + 1
    } else if(elem > item) { // 中間数より低い
        high = mid - 1
    } else { // 等しい
        return mid
    }
}

第三歩：結合

function binarySearch(items, item) {
    var low = 0,
        high = items.length - 1,
        mid, elem
    while(low <= high) {
        mid = Math.floor((low + high) / 2)
        elem = items[mid]
        if(elem < item) {
            low = mid + 1
        } else if(elem > item) {
            high = mid - 1
        } else {
            return mid
        }
    }
    return -1
}

最後に、二分法は配列が整列されている場合にのみ適用できます。配列が無秩序である場合、二分探索は機能しません。

function binarySearch(items, item) {
    // クイックソート
    quickSort(items)
    var low = 0,
        high = items.length - 1,
        mid, elem
    while(low <= high) {
        mid = Math.floor((low + high) / 2)
        elem = items[mid]
        if(elem < item) {
            low = mid + 1
        } else if(elem > item) {
            high = mid - 1
        } else {
            return mid
        }
    }
    return -1
}

// テスト
var arr = [2, 3, 1, 4]
binarySearch(arr, 3)
// 2

binarySearch(arr, 5)
// -1

貪欲アルゴリズム#

アルゴリズム戦略#

貪欲アルゴリズムは、常に現在の最適な選択を行うことを意味し、局所的な最適選択を通じて全体の最適選択を得ることを期待します。

ある意味で、貪欲アルゴリズムは非常に貪欲で、目先の利益しか考慮せず、全体を考慮しないため、選択は局所的な最適に過ぎません。しかし、貪欲アルゴリズムは多くの問題で最適解または良好な解を得ることができるため、その存在には意味があります。

適用シーン#

日常生活の中で、貪欲アルゴリズムを使用することは非常に多いです。例えば：

100 種類の異なる額面の紙幣から 10 枚を抽出し、どのようにすれば最大の価値を得られるか？

私たちは、毎回残りの紙幣の中から最大の額面を選択するだけで、最終的には最適解を得ることができます。これが貪欲アルゴリズムの使用であり、最終的に全体の最適解を得ました。

しかし、私たちは依然として明確にする必要があります。局所的な最適選択を通じて全体の最適選択を得ることは期待に過ぎず、最終的に得られる結果が必ずしも全体の最適解であるとは限りません。

では、一般的にいつ貪欲アルゴリズムを選択することができるのでしょうか？

以下の条件を満たす場合に使用できます：

• 元の問題の複雑度が高すぎる
• グローバルな最適解の数学モデルを構築するのが難しいか、計算量が大きすぎる
• グローバルな最適解を必ずしも求める必要がなく、「比較的良い」解で十分である

貪欲アルゴリズムを使用して最適解を求める場合、以下の手順で解決できます：

• まず、最適解（期待）とは何かを明確にします。
• 次に、問題を複数のステップに分け、各ステップが以下の条件を満たす必要があります：
• 実行可能性：各ステップが問題の制約を満たす
• 局所最適：各ステップで局所的な最適選択を行う
• 取り消し不可：選択が一度行われると、後でどんな状況に遭遇しても取り消すことはできない
• 最後に、すべてのステップの最適解を合計すると、グローバルな最適解になります。

古典的なケース：活動選択問題#

貪欲アルゴリズムを使用して解決する古典的な問題には：

• 最小生成木アルゴリズム
• 単一ソース最短経路のダイクストラアルゴリズム
• ハフマン圧縮符号
• ナップサック問題
• 活動選択問題などがあります。

バックトラッキングアルゴリズム#

アルゴリズム戦略#

バックトラッキングアルゴリズムは、探索法であり、試行錯誤法です。各ステップで選択を行い、この選択が期待される結果を得られないことがわかると、戻って再度選択を行います。深さ優先探索は、バックトラッキングアルゴリズムの考え方を利用しています。

適用シーン#

バックトラッキングアルゴリズムは非常にシンプルで、解を得るまで試行を繰り返すだけです。このアルゴリズムの考え方により、通常は広範囲の探索問題を解決するために使用されます。すなわち、可能な解のセットから、要件を満たす解を選択します。

バックトラッキングアルゴリズムを使用した古典的なケース#

• 深さ優先探索
• 0-1 ナップサック問題
• 正規表現マッチング
• 八皇后
• 数独
• 全順列

ここでは、正規表現マッチングを例にして紹介します。

正規表現マッチング#

var string = "abbc"
var regex = /ab{1,3}c/
console.log(string.match(regex))
// \\["abbc", index: 0, input: "abbc", groups: undefined\\]

そのマッチングプロセス：

5 ステップ目でマッチングに失敗した場合、b{1,3}はすでに 2 つのbにマッチしており、3 つ目のbを試みているところで、次にcが来ることがわかります。この時、前のステップに戻り、b{1,3}のマッチングが完了した（bbにマッチした）後、再度cをマッチさせ、マッチングが終了します。

動的計画法#

アルゴリズム戦略#

動的計画法は、複雑な問題を小さな問題に分解して解決する戦略であり、分割統治アルゴリズムとは異なり、分割統治アルゴリズムは各部分問題が相互に独立していることを要求しますが、動的計画法では各部分問題が相互に関連しています。

したがって、動的計画法は部分問題が重複する場合に適しています。すなわち、異なる部分問題が共通の部分問題を持つ場合、この状況では分割統治戦略が多くの不必要な作業を行います。なぜなら、共通の部分問題を何度も解決するからです。一方、動的計画法は各部分問題を一度だけ解決し、それを表に保存します。一致する問題に遭遇した場合は、表から取得すればよいので、すべての部分問題を解決する必要がなく、大量の不必要な操作を回避できます。

適用シーン#

動的計画法は最適解問題を解決するのに適しています。例えば、額面が不定の 100 枚のコインから任意の数を選んで 10 元を作る場合、どのようにコインを選べば最後に選んだコインの数が最小でちょうど 10 元になるかを求めることができます。これは典型的な動的計画法の問題です。これは、コインを選ぶという部分問題に分解でき、各部分問題には共通の部分問題（コインを選ぶ）があり、部分問題同士は相互に関連しています（選んだコインの合計金額は 10 元を超えてはいけない）、境界条件は最終的に選んだコインの合計金額が 10 元であることです。

この例に対して、バックトラッキングアルゴリズムを使用して、解を探し続けることもできるかもしれませんが、バックトラッキングアルゴリズムは広範囲の解（要件を満たす解）を求めるために使用されます。バックトラッキングアルゴリズムを使用する場合、条件を満たすすべての解を探し、最適解を見つける必要があり、時間計算量は O (2^n) となり、性能は非常に悪いです。動的計画法に適用される問題のほとんどはバックトラッキングアルゴリズムを使用できますが、バックトラッキングアルゴリズムの時間計算量は比較的高いだけです。

最後に、動的計画法を使用して問題を解決する際には、以下の重要なステップに従う必要があります：

• 部分問題を定義する
• 繰り返し実行する必要がある部分問題の部分を実装する
• 境界条件を識別し、解決する

動的計画法を使用して解決するいくつかの古典的な問題#

• 階段登り問題：あなたが階段を登っていると仮定します。頂上に到達するには n 段が必要です。毎回 1 段または 2 段を登ることができます。あなたは何通りの異なる方法で頂上に登ることができますか？
• ナップサック問題：いくつかのリソース（総量と価値がある）を与え、ナップサック（総容量がある）を与え、ナップサックにリソースを詰め込み、目標はナップサックが総容量を超えない範囲で、より多くの価値を詰め込むことです。
• コインの釣り銭：額面が不定の一定数量の小銭と、釣り銭の金額を与え、何通りの釣り銭の方案があるかを求めます。
• グラフの全源最短経路：あるグラフに u、v の頂点が含まれ、頂点 u から頂点 v への最短経路を求めます。
• 最長共通部分列：一組の列の最長共通部分列を求めます（別の列から要素を削除することによって、残りの要素の順序を変更せずに実現できます）。

ここでは、最長共通部分列を例にします。

階段登り問題#

ここでは、動的計画法の古典的な問題である階段登り問題を例にして、動的計画法の問題を解決する手順を紹介します。

第一歩：部分問題を定義する

dp[n]を第 n 段の方案数を表すとし、問題から知ることができるのは、最後のステップで 2 段を登ることも 1 段を登ることもできるため、すなわち第 n 段の方案数は第 n-1 段の方案数と第 n-2 段の方案数の合計になります。

第二歩：繰り返し実行する必要がある部分問題の部分を実装する

dp[n] = dp[n−1] + dp[n−2]

第三歩：境界条件を識別し、解決する

// 第0段は1通りの方案
dp[0] = 1
// 第1段も1通りの方案
dp[1] = 1

最後のステップ：尾コードを翻訳して、いくつかの境界条件を処理する

let climbStairs = function(n) {
    let dp = [1, 1]
    for(let i = 2; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2]
    }
    return dp[n]
}

複雑度分析：

• 時間計算量：O (n)
• 空間計算量：O (n)

空間計算量の最適化：

let climbStairs = function(n) {
    let res = 1, n1 = 1, n2 = 1
    for(let i = 2; i <= n; i++) {
        res = n1 + n2
        n1 = n2
        n2 = res
    }
    return res
}

空間計算量：O (1)

列挙アルゴリズム#

アルゴリズム戦略#

列挙アルゴリズムの考え方は、問題のすべての可能な解を一つ一つ列挙し、条件に基づいてこの解が適切かどうかを判断し、適切なものを保持し、不適切なものを破棄することです。

解法の考え方#

• 列挙対象、列挙範囲、判定条件を確定する。
• 可能な解を一つ一つ列挙し、各解が問題の解であるかどうかを検証する。

まとめ#

アルゴリズムはプログラミングの「根幹」であり、フロントエンドであれバックエンドであれ、コンピュータエンジニアとして一定のアルゴリズム能力を持つことは基本的な要件です。