アルゴリズムをどのように設計するか?一般的なアルゴリズム パラダイムの紹介

アルゴリズムを設計するには?次の記事では、一般的なアルゴリズム パラダイムを分析します。困っている友人が参考になれば幸いです。

最初に 3 つの概念を明確にします。

アルゴリズム: 問題を段階的に解決するプロセス。

パラダイム: 問題についての思考様式。

アルゴリズム パラダイム: 問題に対する効率的な解決策を構築するための一般的なアプローチ。

この記事では、

• 分割統治アルゴリズム
• 動的プログラミング
• 貪欲アルゴリズム
バックトラッキング アルゴリズム

分割統治

ソート アルゴリズムのうち、マージとクイック ソートの 2 つのアルゴリズムの共通点は、分割統治アルゴリズムです。

分割統治 は、問題を元の問題に似た小さなサブ問題に分解するという考え方です。通常、部分問題は再帰的に解決され、部分問題の解決策を組み合わせて元の問題を解決します。

分割統治法のロジックは 3 つのステップに分割できます。

元の問題をより小さなサブ問題に分割します。
1. 部分問題を再帰的に解き、解決が完了したら、その解を部分問題に戻します。
2. 部分問題の解決策を元の問題の解決策にマージします。

分割統治法の例: 二分探索

以下は分割統治を使用して実装された二分探索です。

function binarySearchRecursive(array, value, low, high) {
    if (low <= high) {
        const mid = Math.floor((low + high) / 2);
        const element = array[mid];

        if (element < value) {
            return binarySearchRecursive(array, value, mid + 1, high);
        } else if (element > value) {
            return binarySearchRecursive(array, value, low, mid - 1);
        } else {
            return mid;
        }
    }
    return null;
}

export function binarySearch(array, value) {
    const sortedArray = quickSort(array);
    const low = 0;
    const high = sortedArray.length - 1;

    return binarySearchRecursive(array, value, low, high);
}

上記の

関数は他の人が呼び出すためのものであり、binarySearch は分割統治メソッドが実装される場所であることに注意してください。 binarySearchRecursive

動的プログラミング

動的プログラミング は、複雑な問題をより小さな部分問題に分割することで解決するために使用される最適化手法です。これは分割統治によく似ていますが、問題を独立したサブ問題に分解してから結合するのではなく、動的計画法は問題を 独立した サブ問題に分解するだけです。

アルゴリズム ロジックは 3 つのステップに分かれています:

サブ問題を定義します。
これを繰り返してサブ問題を解決します。
基本的な問題を特定して解決します。

動的プログラミングのケース: 最小コイン小銭問題

これは、コイン小銭問題と呼ばれる一般的な面接の質問です。コインつり銭問題は、おつりの金額を考慮して、おつりを支払うために特定の枚数のコインを使用できるかを見つける方法です。最小コイン両替問題は、特定の金種を使用するために必要な最小コイン数を見つけることです。たとえば、37 セントの両替が必要な場合は、1 2 セント、1 5 セント、1 1 ダイム、1 2 セントを使用できます。

function minCoinChange(coins, amount) {
    const cache = [];
    const makeChange = (value) => {
        if (!value) {
            return [];
        }
        if (cache[value]) {
            return cache[value];
        }
        let min = [];
        let newMin;
        let newAmount;
        for (let i = 0; i < coins.length; i++) {
            const coin = coins[i];
            newAmount = value - coin;
            if (newAmount >= 0) {
                newMin = makeChange(newAmount);
            }
            if (newAmount >= 0 && 
            (newMin.length < min.length - 1 || !min.length) && (newMin.length || !newAmount)) {
                min = [coin].concat(newMin);
            }
        }
        return (cache[value] = min);
    }
    return makeChange(amount);
}

上記のコードでは、パラメーター

は金種 (人民元の [1, 2, 5, 10, 20, 50]) を表します。二重カウントを防ぐために、coins が使用されます。 cache 関数は再帰的に実装され、makeChange にアクセスできる内部関数です。 cache

console.log(minCoinChange([1, 2, 5 10, 20], 37)); // => [2, 5, 10, 20]
console.log(minCoinChange([1, 3, 4], 6)) // => [3, 3]

Greedy アルゴリズム

Greedy アルゴリズム は、現在の最適解に関連しており、全体的な最適解を見つけようとします。動的プログラミングとは異なり、全体的な状況は考慮されません。貪欲なアルゴリズムはシンプルで直感的である傾向がありますが、全体的に最適なソリューションではない可能性があります。

貪欲アルゴリズムのケース: 最小コイン小銭問題

上記の動的計画法によって解決されたコイン問題は、貪欲アルゴリズムによっても解くことができます。この解決策が最適かどうかは、使用される金種によって異なります。

function minCoinChange(coins, amount) {
    const change = [];
    let total = 0;
    for (let i = coins.length; i>= 0; i--) {
        const coin = coins[i];
        while (total + coin <= amount) {
            change.push(coin);
            total += coin;
        }
    }
    return change;
}

ご覧のとおり、貪欲アルゴリズムは動的プログラミング ソリューションよりもはるかに単純です。 2 つの違いを理解するために、同じ解決策のケースを見てみましょう:

console.log(minCoinChange([1, 2, 5 10, 20], 37)); // => [2, 5, 10, 20]
console.log(minCoinChange([1, 3, 4], 6)) // => [4, 1, 1]

貪欲アルゴリズムは最初の問題に対して最適な解決策を提供しますが、2 番目の問題は最適な解決策ではありません (

になります)。 [3，3]

貪欲アルゴリズムは動的計画法アルゴリズムよりも単純で高速ですが、得られる解は最適解ではない可能性があります。

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

バックトラッキング アルゴリズムは、ソリューションを段階的に見つけて構築するのに最適です。

問題を一方の方法で解決してみます。
1. うまくいかない場合は、適切な解決策が見つかるまで、手順 1 を繰り返してください。

バックトラッキングアルゴリズムについては、より複雑なアルゴリズムを紹介するために別の記事を書きます。何を書くかはまだ決まっていませんが、おそらく数独を解くためのプログラムを書くことです。興味のある方は公式アカウントをフォローしてください。

アルゴリズムには終わりがありません。この記事が一般的なアルゴリズム パラダイムの理解に役立つことを願っています。

関連する無料学習の推奨事項: js ビデオ チュートリアル

以上がアルゴリズムをどのように設計するか?一般的なアルゴリズム パラダイムの紹介の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。