インタビュアー: 貪欲アルゴリズムとバックトラッキングアルゴリズムについて、どのように理解していますか?応用シナリオ?

[[429460]]

この記事はWeChatの公開アカウント「JS Daily Question」から転載したもので、著者はHuihuiです。この記事の転載についてはJS Daily Question公式アカウントまでご連絡ください。

1. 貪欲アルゴリズム

貪欲アルゴリズムは、貪欲アルゴリズムとも呼ばれ、アルゴリズム設計における考え方の一種です。

各段階は局所的な最適選択であり、全体最適を達成することを期待しているが、結果は必ずしも最適ではない。

コイン交換の例を見てみましょう。1元、2元、5元のコインを複数持っていて、それを一定の金額に交換したいのですが、必要なコインの最小数は

今 11 元を両替したい場合、貪欲アルゴリズムの考え方に従って、まず最も額面が大きい 5 元硬貨を選択して両替します。すると、11 = 5 + 5 + 1 となり、これが最適な選択肢となります。

しかし、持っている硬貨の額面が 1、3、または 4 で、それを 6 元に交換したい場合、貪欲アルゴリズムによれば、6 = 4 + 1 + 1 が選択されますが、これは最良の選択ではありません。

上記の例から、貪欲アルゴリズムにはいくつかの欠点があることがわかります。貪欲アルゴリズムが使用されるシナリオには、次のような特徴があります。

貪欲法によって問題を解決できる場合、貪欲法が一般的にその問題を解決する最善の方法となります。

貪欲アルゴリズムを選択するかどうかは、主に次の 2 つの特性があるかどうかによって決まります。

貪欲な選択: 問題に対する全体的な最適解が一連の局所的最適解を通じて達成され、各選択が前の選択に依存できるが、後で行われる選択に依存する必要がない場合。
最適なサブ構造: 問題に対する最適な解決策にそのサブ問題に対する最適な解決策が含まれている場合、その問題は最適なサブ構造という特性を持ちます。問題の最適なサブ構造プロパティは、その問題が貪欲アルゴリズムによって解決できるかどうかの鍵となります。

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

バックトラッキングアルゴリズムもアルゴリズム設計におけるアイデアです。問題の解決策を徐々に見つけて構築する戦略です。

バックトラッキングアルゴリズムは、問題に対する可能な解決策から始まります。それが機能しない場合は、問題が解決されるまでバックトラックして別のアクションを選択します。

バックトラッキングアルゴリズムを使用する問題には、次の特性があります。

行列の方向や木のパスなど、パスはたくさんある
これらの道の中には行き止まりと人生の道があり、アイデアは質問の要件を満たさない道であり、人生の道は要件を満たしています。
通常、再帰はすべてのパスをシミュレートするために使用されます

一般的な疑似コードは次のとおりです。

結果 = []
関数backtrack(path, selectlist):
  終了条件が満たされた場合:
    result.add (パス)
戻る  
 
選択リストの選択の場合:
    選択する
    backtrack(パス、オプションリスト)
    選択を元に戻す

次の 3 つの問題の解決に重点を置きます。

パス：つまり、選択されたもの
選択リスト
終了条件

たとえば、古典的なバックトラッキングアルゴリズムは、次のように完全な順列問題を解決するために使用されます。

重複する数字のない配列 nums の場合、すべての可能な順列を返したいとします。この問題を解決するアイデアは次のとおりです。

再帰ですべてのケースをシミュレートする
重複した要素に遭遇した場合はバックトラックする
再帰エンドポイントに到達して戻るすべての状況を収集し、

コードは次のとおりです。

 var permute =関数(数値) {
    const res = []、パス = [];
    バックトラッキング(nums, nums.length, []);
 resを返します。 
     
関数バックトラッキング(n, k, used) {
        パスの長さがkの場合
            res.push( Array.from (パス));
戻る;
        }
 ( i = 0; i < k; i++ とします) {
            if(used[i])継続する;
            パスをプッシュします(n[i]);
            used[i] = true ; // 同じブランチ
            バックトラッキング(n, k, 使用済み);
            パスをポップします。
            使用済み[i] = false ;
        }
    }
 };