貪欲アルゴリズムについて質問するのはやめてください。

[[323204]]

序文

三角形の最短経路と和を求めるとき、貪欲アルゴリズムを使用して解決できますか?したがって、この記事では貪欲アルゴリズムについて簡単に紹介したいと思います。紹介の後、この三角形の最短経路問題が貪欲アルゴリズムを使用して解決できるかどうかを見てみましょう。

この記事では、貪欲アルゴリズムを以下の観点から紹介します。

貪欲アルゴリズムとは何か
貪欲アルゴリズムの例詳細な質問
貪欲アルゴリズムの適用シナリオ
貪欲アルゴリズムを使用して三角形の最短経路を解決できるかどうかを見てみましょう。

貪欲アルゴリズムとは何か

貪欲アルゴリズムは、各段階で現在の段階 (または状態) に最適な選択を行い、その結果がグローバル最適解 (必ずしもグローバル最適解ではない) になることを期待するアルゴリズムです。

貪欲アルゴリズムは、実際には動的プログラミングの一種です。その「貪欲さ」により、現在の段階での最適解にのみ焦点を当てるため、各サブ問題は 1 回だけ計算されます。これによってグローバル最適解が得られる場合、各サブ問題に対してグローバル最適解を見つける必要がある動的プログラミングと比較して、時間の複雑さは間違いなく 1 桁減少します。

簡単な例を見てみましょう。たとえば、ある金額（250など）と100、50、10、5、1（無制限）などの紙幣がある場合、この金額と交換するのに必要な紙幣の枚数を最小限に抑えるにはどうすればよいでしょうか。当然、各交換はより大きな紙幣から始める必要があります。1回目は100、2回目は100、3回目は2番目に大きい50元を選択します。毎回、残額よりも小さい最大の額面の紙幣を選択します。このようにして得られた解は、グローバルな最適解に違いありません。時間の複雑さは間違いなく線形です。

まず、貪欲アルゴリズムを使用して解決できるいくつかの例を見てみましょう。

貪欲アルゴリズムの例詳細な質問

キャンディーをシェアする

キャンディーはm個、子供はn人います。私たちはこれらの子供たちにキャンディーを配りたいのですが、キャンディーの数は少なく、子供の数は多い (m < n) ため、キャンディーは一部の子供たちにしか配ることができません。それぞれのキャンディーの大きさは異なります。これらのm個のキャンディーの大きさは、s1、s2、s3、...、smです。さらに、キャンディーの大きさに対するニーズは子供ごとに異なります。キャンディーの大きさが子供のキャンディーの大きさに対するニーズ以上である場合にのみ、子供は満足します。 n 人の子供のキャンディーのサイズに対する要求がそれぞれ g1、g2、g3、...、gn であると仮定します。では、できるだけ多くの子供たちを満足させるために、キャンディーをどのように配布すればよいのでしょうか?

解決策: 貪欲法を使用してこの問題を解決する場合、解決策は非常に明白です。各子供の需要 gn に対して、gn より大きいサイズのキャンディーの最小値を与えるだけで済みます。このようにして、需要が大きい子供に大きなキャンディーを与えることができます。コード全体は次のようになります。

パブリッククラスソリューション{
    /**
     * 子供たちに配れるキャンディーの最大数を獲得し、条件を満たす
     */
    プライベートスタティック  intディスパッチキャンディ( int [] gList, int [] sList) {
        Arrays.sort(gList); // 子供たちのキャンディーのニーズを小さいものから大きいものの順に並べます
        Arrays.sort(sList); // キャンディーを昇順に並べます
 
 int最大キャンディ数 = 0;
 ( int i = 0; i < gList.length; i++) {
 ( int j = 0; j < sList.length; j++) {
                // 子供のニーズに最も近いキャンディーを選択してください。そうすれば、より大きなキャンディーがより大きなニーズを持つ子供を満足させることができます。
                gList[i] <= sList[j] の場合 {
                    最大キャンディ数++;
                    // キャンディーが選択されている場合は、無効であることを示す -1 に設定します
                    sList[j] = -1;
                    // 現在の子キャンディーが選択されました。
                    壊す;
                }
            }
        }
最大CandyNumを返します。
    } 
 
公共 静的void main(String[] args) {
        // 子どものキャンディーへの欲求
int [] gList = {1,2,4,6};
        // キャンディーの実際のサイズ
int [] sList = {1,2,7,3};
 int結果 = dispatchCandy(gList, sList);
        システム.out.println ( "結果 = " + 結果);
    }
 }

重複する間隔はありません

間隔のコレクションが与えられた場合、残りの間隔が重複しないように削除する必要がある間隔の最小数を見つけます。注: 間隔の終了点は常に開始点よりも大きいと想定できます。区間[1,2]と[2,3]の境界は互いに「接」していますが、重なり合っていません。
例 1: 入力: [ [1,2], [2,3], [3,4], [1,3] ] 出力: 1 説明: [1,3] を削除すると、残りの間隔は重複しません。
例 2: 入力: [ [1,2], [1,2], [1,2] ] 出力: 2 説明: 残りの間隔が重複しないようにするには、2 つの [1,2] を削除する必要があります。
例 3: 入力: [ [1,2], [2,3] ] 出力: 0 説明: すでに重複していないため、間隔を削除する必要はありません。

間隔の重複は、タスクのスケジュール設定など、生活のさまざまな場面で見られます。作業者は、一定期間内に複数のタスクを完了する必要があります。各タスクの完了にかかる時間は異なります。作業者は、この期間内にできるだけ多くのタスクを完了するにはどうすればよいでしょうか? (タスク間の時間は重複できず、作業者は同じ期間内に 2 つのタスクを同時に実行することはできません)

解決策: この問題を解決するために、動的プログラミングと貪欲アルゴリズムをそれぞれ使用し、2 つの時間の計算量を比較して、貪欲アルゴリズムの方が時間の計算量の点で優れているかどうかを確認します。

動的プログラミングソリューション

まず、解法を容易にするために、図に示すように、区間の開始点から各区間を小さいものから大きいものへと並べ替えます。

次に、前回の記事で説明した動的プログラミング問題解決の 4 つのステップを適用して、動的プログラミングを使用して問題を解決する方法を確認します。

1. 再帰を使って問題を解決できるかどうかを判断する

実際、上記のソートされた区間を直感的に見ると、これは組み合わせではないでしょうか。各区間は、選択されるか、選択されないかのどちらかです。すべての組み合わせが尽きてから、どの組み合わせが質問の条件を最もよく満たすかを確認します。したがって、再帰は間違いなく使用できます（再帰を使用して組み合わせを解決する方法については、この記事を読むことを強くお勧めします）。

ただし、この問題の組み合わせは少し特殊です。前後の 2 つの間隔は条件付きで制限されています。現在の間隔が前の間隔と重複している場合は、2 つのうち 1 つしか選択できません (重複を防ぐためにもう 1 つは削除する必要があります)。そのため、次のアイデアがあります。

それぞれ前の間隔と現在の間隔を表す2つの値preとcurを定義します。次の手順が必要です。

前の間隔の終了値と現在の間隔の開始値を比較します
前の間隔の終了値が現在の間隔の開始値より小さい場合、2 つの間隔は重複していないことを意味します。次に、pre を cur に設定し、cur を cur + 1 に設定して、次の 2 つの隣接する間隔の判定を開始します (つまり、手順 1 を繰り返します)。
前の間隔の終了点が現在の間隔の開始値より大きい場合、2 つの間隔が重複していることを意味します。その場合、pre は変更されず、cur は cur + 1 に設定されます (つまり、cur に対応する間隔が削除されます)。削除された間隔の数は 1 ずつ増加し、次の pre、cur+1 間隔の判断が開始されることに注意してください (つまり、手順 1 を繰り返します)。

注: 最初の区間トラバーサルでは、pre = -1、cur = 0 と定義します。

以上の説明から、再帰現象が起きているのは明らかですので、以下のようなコードを書き、キーとなるコードについては詳細にコメントしています。

パブリッククラスソリューション{
    //開始値と終了値を含む間隔クラス
    プライベート静的クラス Interval {
開始整数;
整数 終わり;
        間隔( int開始, int  終わり） {
            this.start = 開始;
            this.end =終了;
        }
    } 
 
    プライベートスタティック 整数removeDuplicateIntervas(Interval[] intervals) {
        // 開始点に従って間隔を小さいものから大きいものへと並べ替えます
        Arrays.sort(間隔、Comparator.comparingInt(a -> a.start));
        // 最初のトラバーサルは -1,0 から始まります
removeSubDuplicate(-1, 0, 間隔) を返します。
    } 
 
    プライベートスタティック 整数removeSubDuplicate( int pre, int cur,Interval[] intervals) {
        （cur == 間隔.長さ）の場合{
 0を返します。
        } 
 
 int notRemove = Integer.MAX_VALUE ;
        pre == -1 || 間隔[pre] .end <= 間隔[cur].start の場合{ 
 
            /**
             * これが最初のトラバーサルである場合、または事前間隔の終了点が現在の間隔の開始点よりも小さい場合（つまり、間隔が重複していない場合）、
             * この場合、pre = cur、cur = cur+1
             */
            重複したサブオブジェクトを削除しない
        } 
 
        /**
         * pre間隔の終了点がcur間隔の開始点より大きい場合、2つの間隔が重なり、curは後者の間隔を指すことを意味します。つまり、cur = cur + 1です。
         * は cur が削除されることを意味するため、1 を追加する必要があります (この間隔が削除されたことを示します)
         */
 int削除 = removeSubDuplicate(pre, cur+1, 間隔) + 1; 
 
        // 2つの値のうち小さい方を取る
Math.min ( notRemove,remove)を返します。
    } 
 
公共 静的void main(String[] args) {
        // 間隔を初期化する
        間隔[] 間隔 = {
                新しい区間(1, 2)
                新しい区間(3, 5)
                新しい区間(4, 7)
                新しい区間(8, 10)
                新しい区間(9, 11)
        };
 int結果 = removeDuplicateIntervas(間隔);
        システム.out.println ( "結果 = " + 結果);
    }
 }

2. 再帰プロセスに多数の繰り返しサブ問題が存在するかどうかを分析する

繰り返されるサブ問題が多数あるかどうかを判断するにはどうすればよいでしょうか。動的プログラミングの問題解決スキルの学習に関する論文で、再帰ツリーを描くという解決策を提案しました。ただし、この問題に対して再帰ツリーを描くのは面倒です。実際、組み合わせ問題の場合は、単純に分析することができます。各区間について、選択するかしないかのいずれかです。区間が選択されていることを表すには 1 を使用し、区間が選択されていないことを表すには 0 を使用します。次に、次の 2 つの組み合わせを検討します。

 11010
 11001

よく見てください、赤枠の部分が繰り返されるサブ問題です!

この分析はちょっと難しいと思う人もいるかもしれないので、もう1つのコツ、印刷をお教えしましょう。写真のように

再帰関数で出力し、出力ルールを分析する

ご覧のとおり、確かに繰り返しサブ問題があります。時間計算量はどれくらいでしょうか? 各区間は選択されるか選択されないかのどちらかで、合計 2 つの状態があります。区間が n 個ある場合、2^n なので、時間計算量は O(2^n) で指数関数的であることがわかります。明らかに受け入れられません。

繰り返し部分問題があるため、動的計画法の 3 番目のステップに進みましょう。

3. 繰り返し計算を避けるために、メモを使用してサブ問題の解決策を保存する（剪定）

上記の分析では、preとcurに多くの重複がある可能性があることがわかります。そのため、preとcurに対応する中間結果を次のように保存します。

 // 中間結果を保存する
プライベート静的HashMap<String, Integer > map = new HashMap();
プライベートスタティック 整数removeSubDuplicate( int pre, int cur,Interval[] intervals) {
    文字列キー= pre + "," + cur;
    map.get(キー) != nullの場合
map.get(キー)を返します。
    } 
     
    （cur == 間隔.長さ）の場合{
 0を返します。
    } 
 
 int notRemove = Integer.MAX_VALUE ;
    pre == -1 || 間隔[pre] .end <= 間隔[cur].start の場合{
        重複したサブオブジェクトを削除しない
    } 
 
 int削除 = removeSubDuplicate(pre, cur+1, 間隔) + 1;
 int結果 = Math.min ( notRemove, remove);
    map.put(キー、結果);
結果を返します。
 }

メモメソッドを使用してサブ問題の中間結果をキャッシュすると、時間の計算量は O(n^2) に急激に低下します (2 つの変数 pre と cur が常に後方に移動されるため、つまり 2 つのループレイヤーがあるため、O(n^2) になります)。

4. 再帰にボトムアップアプローチ、つまり動的プログラミングを使用する

dp[i]を0からi番目の区間までの重複しない区間の最大数として定義すると、状態遷移方程式が得られる。

 dp[i] = max {dp[j]} + 1、ただし0 <=j < iかつinterval[i].start > interval[j].endを満たす必要があります。つまり、iとjが指す間隔は重複しません。

最終的なdp[区間の総数 - 1]は、連続する重複しない区間の最大数です。そして、区間の総数 - 連続する重複しない区間の最大数が、削除する区間の最小数です。dp方程式を使用すると、次のようにコードをすばやく記述できます。

 /**
 * 2 つの間隔が重なり合っているかどうかを判断します。間隔 i の開始点は、間隔 j の開始点よりも大きいです。間隔 j の終了点が間隔 i の開始点よりも大きい場合、それらは重なっています。
 */
プライベート静的ブール値isOverlapping(間隔i、間隔j) {
 j.end > i.startを返します。
 } 
 
 /**
 * 動的プログラミングソリューション
 */
プライベートスタティック 整数removeSubDuplicateWithDP(Interval[] intervals) {
    // 開始点に従って間隔を小さいものから大きいものへと並べ替えます
    Arrays.sort(間隔、Comparator.comparingInt(a -> a.start)); 
 
 int [] dp = 新しいint [intervals.length];
    配列.fill(dp, 0);
    dp[0] = 1; // すべての区間が重なっていても、連続する重なり合わない区間の数は少なくとも1なので、dp[0]を1に設定します。 
 
 int結果 = 1;
 ( int i = 1; i < 間隔の長さ; i++) {
整数 最大値= 0;
 ( int j = 0; j < i; j++)の場合{
            if (!isOverlapping(intervals[i], intervals[j])) {
最大値= Math.max ( dp [j],最大値);
            }
        }
        dp[i] =最大値+ 1;
    }
 intervals.length - dp[intervals.length - 1]を返します。
 }

空間計算量はどれくらいですか? dp 1 次元配列は 1 つしかないので、O(n) です。時間計算量はどれくらいですか? ループが 2 つあるので、O(n^2) です。時間計算量は再帰＋メモ化と同じであることがわかります。ただし、何度も述べているように、再帰はスタックオーバーフローにつながりやすいため、動的プログラミングを使用して解決することをお勧めします。

それでは、貪欲アルゴリズムを使用してこれを解決する方法を見てみましょう。まず、次のように、間隔の終点に応じて間隔を小さいものから大きいものへと並べます。

私たちのアイデアは、上記の記事の動的プログラミングと同じです。まず、重複しないサブ間隔の最大数を見つけ、次に「間隔の合計数 - 重複しないサブ間隔の最大数」を、削除する重複間隔の最小数として使用します。

貪欲アルゴリズムを使用して、重要でないサブ区間の最大数を見つける手順は次のとおりです。

最小の終点を持つ間隔を選択し、それを現在の間隔 cur として設定します。
小さい間隔から大きい間隔までの終了点に従って、間隔 cur と重複しない次の間隔を検索し、この間隔を現在の間隔 cur として設定し (この時点で重複しないサブ間隔の最大数は 1 ずつ増加することに注意してください)、すべての間隔が走査されるまで手順 2 を繰り返します。

アニメーション画像は以下の通りです。アニメーション画像を見ていただいた方が分かりやすいかと思います。

問題を解決する方法がわかれば、コードを書くのは非常に簡単になります

/**
 * 貪欲アルゴリズムの解
 */
プライベートスタティック 整数removeSubDuplicateWithGreedy(Interval[] intervals) {
    // 区間の終点を小さいものから大きいものの順に並べ替える
    Arrays.sort(間隔、Comparator.comparingInt(a -> a.end )); 
 
 int cur = 0; // 最初のものを現在の間隔に設定します
整数  count = 1; // 重複しない間隔の最大数、最小は 1
 ( int i = 1; i < 間隔.長さ; i++) {
        // 重複なし
        （間隔[cur] .end < 間隔[i].start）の場合{
            カーソルをiに合わせる
カウント++;
        }
    }
    // 区間の総数から重複しない区間の最大数を引いたものが、削除される重複する区間の最小数です
間隔の長さ -カウントを返します。
 }

タイムの複雑さは何ですか？それは、o（n）です。これは、貪欲なアルゴリズムが非常に速い理由を簡単に分析しています。動的プログラミング（DP [i] = max {dp [j]} + 1）の動的プログラミングについては、それぞれのIに溶液が最適であることを見つけるために、最大値を見つけるために最適なプログラミックを見つけるために、ソリューションを最下位から測定する必要があります。バックトラッキングプロセスでは、貪欲なアルゴリズムが目の前の最適なソリューションを追求するため、貪欲なアルゴリズムを節約できない場合、いくつかのサブ問題の計算があります。

貪欲アルゴリズムの適用シナリオ

貪欲アルゴリズムを簡単にまとめると、各ステップで最良の解のみが選択され、各ステップで選択された最適解がグローバル最適解を達成できると期待されることを意味します。正直に言うと、これは難しすぎます。なぜなら、サブ問題が完全に独立していて無関係でない限り、一般的に1つの問題の選択は次の問題の選択に影響を与えるからです。たとえば、記事の冒頭の釣り銭を作る例では、ある国の紙幣がかなり奇妙で、1、5、11の3つの額面しかない場合、最小の紙幣で15を作るにはどうすればよいでしょうか。貪欲法を使用して最初に11を選択した場合、その後は4つの1しか選択できません。つまり、15 = 1 x 11 + 4 x1です。実際、最適解は 5 元紙幣 3 枚です。なぜこの場合貪欲法は適用できないのでしょうか? 11 の最初の選択が後続の紙幣の選択に影響するからです。言い換えれば、サブ問題は独立しているのではなく、互いに制限し、影響し合っています。したがって、貪欲法を選択するときは、適用可能なシナリオに注意する必要があります。

貪欲アルゴリズムを使用して三角形の最短経路を解決できるかどうかを見てみましょう。

冒頭の質問に戻りましょう。三角形の最短経路は貪欲アルゴリズムを使用して解くことができますか?

まずトピックを確認しましょう:

図に示すように、上の三角形は一連の数字で構成されています。頂点 2 から下端までの最短経路が必要です。毎回、現在のノードの下にある 2 つのノードにしか移動できません。たとえば、3 は 6 または 5 に移動できますが、7 に直接移動することはできません。

図に示すように、ノード 2 から一番下までの最短パスが必要です。考慮するのはノード 9 と 10 だけです。前の層のノードは考慮する必要はありません。9 と 10 はすでに最適なサブ構造であるため、各層のノードの最大値 (つまり、1 次元配列) のみが保存されます。

貪欲アルゴリズムを使用して解決する方法

1. ステップ 1: 2 から下に進みます。3 は 4 より小さいので、3 を選択します。

2. ステップ 2: 3 から下に進みます。5 は 6 より小さいので、5 を選択します。

ステップ3: 5から下へ進み、1が8より小さい場合は1を選択します

答えは 11 で、動的プログラミングによって得られる解とまったく同じです。これは、この問題が貪欲アルゴリズムを使用して解決できることを意味しますか?

答えはノーです。上記の解が正しい理由は、これらの数値が貪欲な解法によって得られたグローバル最適解であるからです。数値を変更すると何が起こるか見てみましょう。

図に示すように、数字を図のように変更すると、貪欲によって得られる最短経路は66になりますが、実際の最短経路は、下の図に示すように16になるはずです。

なぜ貪欲は機能しないのでしょうか? 貪欲は各ステップで最適な解決策を追求するからです。一度選択すると、後続のサブ問題の選択に影響します。たとえば、3 を選択した場合、7 は選択できなくなります。したがって、もう一度、貪欲の適用可能なシナリオと、サブ問題が互いに制限し、影響し合うかどうかに注意する必要があります。

要約する

この記事では、貪欲アルゴリズムの適用可能なシナリオについて簡単に説明します。貪欲の長所と短所を誰もがより明確に理解する必要があると思います。貪欲は、この選択が後続のサブ問題に与える影響に関係なく、現時点での最適解（現時点での最善！）を追求します。したがって、貪欲によって得られた解は、グローバルな最適解ではない可能性があります。これは、キャリアプランニングを行うときのようなものです。一時的な利益のために現在の利益だけを考慮するのではなく、長期的なキャリアに継続的に利益をもたらす選択を行う必要があります。したがって、貪欲の使用シナリオは比較的小さく、動的計画法の特殊なケースです。したがって、貪欲で解決できる場合は、動的計画法でも解決できます。

<<: AIはインフラの応用と開発を定義する

>>: AIの5つの本当の危険性