プログラマーアルゴリズムの基礎 - 貪欲アルゴリズム

序文

貪欲は人間が本来持つ能力であり、貪欲アルゴリズムとは貪欲な意思決定に基づいた全体計画の総称です。

[[231562]]

たとえば、一般的なアルゴリズムの筆記試験の質問 - Jump:

• 一列にn個のボックスがあり、各ボックスには番号a[i]が付いています。これは、最大a[i]個のボックスを右にジャンプできることを示しています。
• シャオミンは左の最初の箱のところに立っています。彼は一番右の箱に届くでしょうか?
• たとえば、[1, 2, 3, 0, 4] は 5 番目のボックスに到達できます。
• [3, 2, 1, 0, 4]は5番目のボックスに到達できません。

自然に解決策を思いつくことができます。それは、できるだけ右にジャンプして、最終的に到達できるかどうかを確認することです。

この記事は、この貪欲な意思決定についての紹介です。

文章

貪欲アルゴリズムの基本概念

狭義では、貪欲アルゴリズムは最適化問題を解決するための特別な方法を指します。解決プロセスでは、常にその瞬間に最良の選択が行われます。最適なサブ構造の特性により、ローカル最適解はグローバル最適解を得ることができます。この貪欲アルゴリズムは、動的プログラミングの特殊なケースです。貪欲法で解決できる問題は、動的計画法でも解決できます。

広い意味では、貪欲とは、現状に基づいて貪欲な決定を下す一般的な貪欲な戦略を指します。ジャンプに関する質問を例に挙げてみましょう。

• 問題の核心は、右へ到達できる最遠距離にあることが分かりました。これを maxRight と表します。

このとき、貪欲な戦略が採用されます。最初のボックスから始めて右に移動し、通過する各ボックスごとに maxRight の値を継続的に更新します。

貪欲アルゴリズムの思考プロセス

貪欲な思考プロセスは動的プログラミングに似ており、大きなものを小さくし、小さなものをゼロにする 2 つのステップで構成されます。

大きな取引を小さくする:

より大きな問題は、サブ問題との重複を見つけることで、複雑な問題を複数の小さな問題に分割します。

それは些細なことだ:

小さな問題から意思決定の核心を見つけ出し、「ジャンプ」で右にどれだけ遠くまで行けるかなど、最適な解決策を得るための戦略を決定します。

数学的な証明は、局所的な最適解が全体的最適解につながるかどうかを証明するのによく使用されます。

貪欲アルゴリズムの具体的な応用

1. 紙幣の両替に関する問題

1元、2元、5元、10元の紙幣がそれぞれ[1]、[2]、[3]、[4]枚あります。m元を作るには何枚の紙幣が必要ですか？

動的プログラミングの場合:

• m元を集めるには、まずm-1元、m-2元、m-5元、m-10元を集める必要があります。i元を集めるのに必要な紙幣の最小枚数を表すためにdp[i]を使用します。
• したがって、dp[i]=min(dp[i-1], dp[i-2], dp[i-5], dp[i-10]) + 1;
• dp[1]=dp[2]=dp[5]=dp[10]=1であることは簡単に分かります。

上記の再帰方程式と初期化情報に基づいて、dp[1〜m]のすべての値を簡単に導出できます。

何かおかしいですね。普通に小銭を両替するのはそんなに複雑なのでしょうか?

貪欲アルゴリズムの観点から見ると、m>10 で 10 元紙幣がある場合、10 元紙幣を優先し、次に 5 元紙幣、2 元紙幣、1 元紙幣を優先します。

• 私たちは日々の経験から、これが正しいことだと知っていますが、なぜでしょうか?
• 質問をこのように変更した場合、元の戦略は依然として機能しますか?
• それぞれ1元、5元、7元の紙幣がa[1]、a[2]、a[3]あります。m元を作るには何枚の紙幣が必要ですか？

次に、この戦略を分析してみましょう。

• m 元紙幣に対して、1 元、2 元、5 元紙幣の a、b、c 枚が使用されることがわかっているので、a+2b+5c=m となります。

1元、2元、5元紙幣の使用枚数がx、y、zである状況があるとします。5元紙幣の使用枚数は（z

k=5*(cz) と設定すると、k 元紙幣には floor(k/2) の 2 元紙幣、k%2 の 1 元紙幣が必要です。(1 元紙幣が 2 枚ある場合、1 枚の 2 元紙幣を使用してそれを置き換えることができるため、1 元紙幣は 0 または 1 のみになります)

5元紙幣を(cz)減らすには、2元紙幣を(5*(cz)/2)枚、紙幣を(5*(cz))%2枚増やす必要があることは容易にわかります。これにより、x+y+zは必ずa+b+cより大きくなります。

このことから、5元紙幣を少なく使うことよりも良い解決策はないことがわかります。

したがって、高額紙幣を優先することは正しい貪欲な選択です。

例えば、1元、5元、7元紙幣で10元を作る場合、最初に7元紙幣を使うと紙幣の枚数は4枚になります（1+1+1+7）。

しかし、5元紙幣のみを使用する場合、紙幣の数は2枚です（5+5）

この場合、高額紙幣を優先するのは間違った貪欲な選択です。 （しかし、動的プログラミングでは最適な解決策を得ることができます）

2. サーバータスクのスケジュールの問題

サーバーには実行するタスクが n 個あります。各タスクの開始時間は Si 秒、終了時間は Ti 秒です。同時に実行できるタスクは 1 つだけです。

できるだけ多くのタスクを時間内に完了できるようにタスクを配置するにはどうすればよいでしょうか?

動的プログラミングの場合:

最初の i 秒間に完了したタスクの数は、前の 1 秒間から i-1 秒間に完了したタスクの数から推測できます。

• 最初のi秒間に完了できるタスクの数を表すためにdp[i]を使用します。

最初の i 秒間に完了できるタスクの数を計算する場合、j 番目のタスクに対して 2 つの決定があります。

1. このタスクが実行されない場合、dp[i]は変更されません。
2. このタスクを実行するには、(Sj、Tj) 時間を解放する必要があるため、dp[i] = max(dp[i]、dp[ S[j] ]) + 1 となります。

たとえば、タスク j が 5 秒目に開始し、10 秒目に終了する場合、i>=10 であれば、dp[i]=max(dp[i], dp[5] + 1) となります (5 秒目から i 秒目までの時間をタスク j に割り当てることに相当)。

貪欲戦略をもう一度考えてみると、人々は現実の生活の中でこのようなマルチタスクをどのようにこなしているのでしょうか? 別の言い方で説明しましょう。

• シャオミンは学校でパートタイムで働いています。1日10時間働いています。
• 現在、複数のパートタイムの職があり、それぞれに開始時間と終了時間があり、シャオミンは同時に 1 つのパートタイムの仕事しかできません。

シャオミンは毎日いくつのアルバイトをすることができますか？

早く終わるアルバイトを先にやろう！という戦略が自然に浮かびます。

なぜ？

なぜなら、この仕事を先に終わらせれば、他のアルバイトをする時間が増えるからです。

私たちは、意思決定を最適化する能力を持って生まれています。

3. キャンディーの共有問題

n 人の子供たちがゲームを終えた後、先生は彼らにキャンディーをあげるつもりでした。

各人にはスコアa[i]があります。スコアが左右の人よりも高ければ、左右の人よりも多くのキャンディーがもらえ、各子供は少なくとも1つのキャンディーを受け取ります。

少なくとも何個のキャンディーを用意する必要があるかを先生に尋ねます。

これはLeetCodeに関する質問です。

この問題は、たとえば dp[i] を使用して最初の i 人に必要なキャンディーの最小数を表すなど、動的プログラミングを使用して直接解決することはできません。

状態（最初の i 人のキャンディーの最小数）は、i+1 人目の人によって影響を受けることを示しているためです。a[i]>a[i+1] の場合、i 人目の人は i+1 人目の人よりも多くのキャンディーを持っているはずです。

つまり、この状態は後遺症がないことを意味します。

キャンディーを配るとしたら、どのように配りますか？

答えは、最も低いスコアから始めることです。

スコアが低いものから順に並べ替え、そのたびに、スコアが左側と右側のスコアよりも高いかどうかを判断します。

各人が c[i] 個のキャンディーを獲得すると仮定すると、i 番目の人については、c[i]=max(c[i-1],c[c+1])+1 となります (c[i] のデフォルトは 0 です。i を計算するときに c[i-1] が 0 の場合、i-1 のスコアが i よりも高いことを意味します)

ただし、このソリューションの時間計算量は O(NLogN) であり、主なボトルネックはソートです。

送信すると、時間制限を超えたことを示すプロンプトが表示されます。

貪欲な戦略を最適化する必要があります。

• 左と右の状況を別々に見てみましょう。

左側の人よりもスコアが高い場合のみを考えれば、戦略は簡単に得られます。

• 左から右にトラバースして、a[i]>a[i-1]の場合、c[i]=c[i-1]+1、それ以外の場合はc[i]=1になります。

右側の人よりもスコアが高い人を検討する場合、配列の右端から始めて左に移動する必要があります。

• a[i]>a[i+1]の場合、c[i]=c[i+1]+1となり、それ以外の場合はc[i]は変更されません。

2 回の走査の後、時間計算量が O(N) の割り当て計画を取得できます。

4. 川を渡る小型船の問題

n人が川を渡りたいのですが、船は1隻しかありません。船は一度に2人しか乗れず、各人が単独で船に乗るにはa[i]の横断時間が必要です。2人 (xとy) が一緒に船に乗る場合、横断時間はa[x]とa[y]の大きい方になります。

全員が川を渡るのに必要な最短時間はどれくらいでしょうか?

この質問から、重要な情報が得られます: 1. 2 人が川を渡るには長い時間がかかります。

隠された情報もあります: 2. 2 人が川を渡った後、1 人がボートを運転して戻る必要があります。

合計時間をできるだけ短くするためには、2 人の間の時間差をできるだけ小さくすること (無駄を減らすため)、およびボートが戻ってくるまでの時間もできるだけ短くすること (待ち時間を短縮するため) という 2 つの重要な原則があります。

空の船が戻ってくる状況を無視して、船が無限にある場合、どのように割り当てるべきでしょうか?

答え: 毎回、残った人の中から最も時間がかかった人を選び、次にその人の時間に最も近い時間をかけた人を選びます。

ボートが1隻しかない場合を考えてみましょう。3人の人A/B/Cがいて、Aが

すると、最速の解決法は次のようになります: A+B 進み、A 戻り、A+C 進み、合計時間は A+B+C です。 （Aが一番速いので、他の人が行ったり来たりするのは時間がかかるだけ、待ち時間を減らす原則）

A/B/C/Dの4人がいて、Aが

• 誰かを往復させる最も速い方法は、A+B が行き、A が戻り、A+C が行き、A が戻り、A+D が行き、合計時間は B+C+D+2A です (待機時間を減らす原則)
• 人々を一緒に送る最も速い方法と 2 番目に速い方法は、A+B が最初に行き、A が戻る、C+D が行き、B が戻る、A+B が行く、合計時間は 3B+D+A です (無駄を減らす原則)

オプション 1 と 2 の選択肢を比較すると、違いは A+C と 2B のみであることがわかりました。

オプション 1 と 2 の違いに D がないのはなぜですか?

なぜなら、D は最終的に川を渡らなければならず、それにかかる時間は D でなければならないからです。

A/B/C/D/Eの5人がいて、Aが

まだ最も遅い E を見ています。 （船舶数は無制限です）

• 計画1、待ち時間を短縮し、まずEを送り、その後4人の状況を考慮します。
• プラン 2、無駄を減らす。まず E/D を送信し、次に A/B/C の状況を考慮する。(プラン 2、4 人用)

参加者が 5 人になった時点で、私たちはすでに明らかな特徴を発見していました。それは、質問が繰り返し行われ、サブ質問によって解決できるという点です。

5人の状況に応じて、状態遷移方程式dp[i] = min(dp[i - 1] + a[i] + a[1], dp[i - 2] + a[2] + a[1] + a[i] + a[2])を導き出すことができます。

検討した1人、2人、3人、4人の状況に基づいて、それぞれdp[i]の初期値を計算できます。

 dp[1] = a[1];  
 dp[2] = a[2];  
 dp[3] = a[2]+a[1]+a[3];  
 dp[4] =最小(dp[3] + a[4] + a[1]、dp[2]+a[2]+a[1]+a[4]+a[2]);

上記の状態遷移方程式と初期化値から、dp[n]の値を推測できます。

これは貪欲計画法と動的計画法を組み合わせたものです。貪欲戦略は動的計画法の意思決定プロセスで使用されます。

要約する

貪欲な学習プロセスは、自分の思考を最適化することです。

既存の情報を把握し、最善の判断を下すことです。

練習用に集めた貪欲な練習問題をいくつか紹介します。