欲張りアルゴリズムについて話しましょう

前言
前にダイナミックな計画を話して、資料をめくっている間に貪欲なアルゴリズムについて話しているのを見ましたが、この2つのアルゴリズムにも似ています.ちょうど最近貪欲な問題ができたので、今日は文章を書いて話します.
欲張りアルゴリズム(英語:greedy algorithm)は、欲張りアルゴリズムとも呼ばれ、ステップ選択ごとに現在の状態で最良または最良(すなわち最も有利)の選択を行い、結果が最良または最良になることを望むアルゴリズムである.
欲張りアルゴリズムは最適サブ構造の問題において特に有効である.最適サブ構造は,局所最適解エネルギーがグローバル最適解を決定することを意味する.簡単に言えば,問題はサブ問題に分解して解決することができ,サブ問題の最適解は最終問題の最適解にプッシュできる.
欲張りアルゴリズムとダイナミックプランニングの違いは、サブ問題ごとに解決策を選択し、後退できないことです.ダイナミックプランニングでは、以前の演算結果が保存され、以前の結果に基づいて現在が選択され、ロールバック機能があります.
貪欲法はいくつかの最適化問題を解決することができて、例えば:図の中の最小生成木を求めて、ハフマン符号化を求めます......その他の問題に対して、貪欲法は一般的に私たちが要求した答えを得ることができません.一つの問題が貪欲法で解決できると、貪欲法は一般的にこの問題を解決する最善の方法である.欲張り法の効率性とその求めた答えが最良の結果に近いため、欲張り法は補助アルゴリズムとして使用したり、要求結果が特に正確ではない問題を直接解決したりすることもできる.
——ウィキペディアより
動的計画と貪欲アルゴリズムはよく似ており,それらの記述には問題をサブ問題に分解する説があり,実は分治法もこのようなモデルである.しかし、動的計画は実質的に窮屈な方法であり、計算を繰り返すのを省くだけで、貪欲なアルゴリズムは、その名前のように、貪欲で、毎回局所的な最適解を選択し、この局所的な最適選択がグローバルに与える影響を考慮しない.欲張りアルゴリズムは動的計画の特例であり、欲張りアルゴリズムがサブ問題の最適解だけを考慮しているからこそ、欲張りアルゴリズムが実際に解決できる問題は限られており、目が短いアルゴリズムであり、現在だけを考慮し、このような局所的な最適選択が最終的に全体の最適解をもたらす場合にのみ欲張りアルゴリズムで解決できると言える.
やっぱり栗を挙げて
leetcodeの問題を見てみましょう.
もしあなたが素晴らしい保護者だとしたら、子供たちにクッキーをあげたいです.しかし、子供1人につき最大1枚のビスケットしかあげられません.子供iごとに、食欲値giがあります.これは子供たちが食欲を満たすビスケットの最小サイズです.そしてビスケットjごとに、サイズsjが1つあります.もしsj>=giであれば、私たちはこのビスケットjを子供iに割り当てることができて、この子供は満足します.あなたの目標は、できるだけ多くの子供を満たし、この最大値を出力することです.
注意:
食欲値が正だと仮定することができます.
子供はせいぜいビスケットを1枚しか持っていない.
出典:力ボタン(LeetCode)
リンク:https://leetcode-cn.com/probl...
著作権はインターネットの所有に帰属する.商業転載は公式の授権に連絡してください.非商業転載は出典を明記してください.
はい、これは素晴らしい(けちな)親で、できるだけ少ないビスケットで多くの子供を満足させなければなりません.例えば、今3人の子供の食欲が[1,2,3]であれば、保護者の手に1のサイズのビスケットが100枚あっても、1人の子供を満たすしかありません.彼の子供にはビスケットが1つしか与えられないからです.どうやって「欲張り」するか考えてみましょう.ビスケットを最も節約するには、ビスケットのサイズと子供の食欲の2つのデータを昇順に並べ替えて、毎回最小のビスケットで食欲の最小の子供を満たすことができるかどうかを試してみることができます.そうすれば、2つのインデックスを維持する必要があります.
コード実装:

class Solution:
    def findContentChildren(self, g: List[int], s: List[int]) -> int:
        count = 0
        g.sort()
        s.sort()
        gi, si = 0, 0
        while gi < len(g) and si < len(s):
            if s[si] >= g[gi]:
                count += 1
                gi += 1
                si += 1
            elif s[si] < g[gi]:
                si += 1
        return count

ビスケットのサイズがちょうど子供の食欲に等しいとき、カウント+1、2つのインデックス値+1、さもなくば、ビスケットのサイズリストのインデックス+1、もっと大きいビスケットが現在の子供を満たすことができるかどうかを見てみましょう.余談:よく見られるPythonコードでは、あるリストの長さ値をある変数に保存し、size = len(alist)のようにlen()関数にかかるのはO(1)定数時間です.Pythonの設計ではすべてオブジェクトであり、リストももちろんオブジェクトであり、リストを作成した後、len()は実質的にこのリストインスタンスの長さ属性値を抽出しただけで、リストなどの操作は行われていません.
じっこう
もう一つのテーマを見てみましょう.
1本のループにはN個のガソリンスタンドがあり、そのうちi番目のガソリンスタンドにはガソリンgas[i]リットルがある.
ガソリンタンクの容量が無限の車を持っていて、i番目のガソリンスタンドからi+1番目のガソリンスタンドに行くにはガソリンcost[i]リットルを消費する必要があります.その中のガソリンスタンドから出発すると、最初はガソリンタンクが空いていました.
ループを一周できる場合は、出発時のガソリンスタンドの番号に戻ります.そうしないと-1に戻ります.
説明:
もし問題に解があれば、その答えは唯一の答えです.
入力配列はすべて空ではない配列で、長さは同じです.
入力配列の要素はすべて負ではありません.
まず、ガソリンスタンドの油量の合計が道路で消費される総油量より小さい場合、完全な距離を走ることは不可能であることが考えられます.つまり、sum(gas) < sum(cost)であれば、-1に戻ります.2つ目は、1つのガソリンスタンドiを始点とし、このガソリンスタンドで得られる油量が次のガソリンスタンドに行くのにかかる油量、すなわちgas[i] < cost[i]よりも小さい場合、このガソリンスタンドが起点とならないことを示す.
コード実装:

class Solution:
    def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
        total, curr = 0, 0
        start = 0
        for i in range(len(gas)):
            total += gas[i] - cost[i]
            curr += gas[i] - cost[i]
            if curr < 0:
                start = i + 1
                curr = 0

        return start if total >= 0 else -1

ここでは最終的な油量をtotalで保存し、currは現在のタンク油量を表し、startは起点を表し、初値はいずれも0とし、リスト全体を遍歴し、ガソリンスタンドi,gas[i] - cost[i] < 0であれば、i+1番目のガソリンスタンドを起点とし、最後にtotalが0より小さい場合は-1に戻り、そうでなければstartに戻る.

時間複雑度:O(n)

空間複雑度:O(1)

欠陥を見る
次の例は、ユーザー@チェン行止を知っていることから来ています.
まず、生活の中でよく出会うことを見てみましょう.もしあなたが土豪だとしたら、1、5、10、20、50、100元の札を持っています.今あなたの目標はある金額wを集めることで、できるだけ少ない紙幣を使う必要があります.生活経験に基づいて、私たちは明らかにこのような戦略を取ることができます:100を使うことができるのはできるだけ100を使うことができて、さもなくばできるだけ50を使う......順番に類推します.この戦略の下で666=6×100+1×50+1×10+1×5+1×1、全部で10枚の札を使いました.この戦略を「貪欲」と呼ぶ:私たちが直面している局面が「wを出す必要がある」と仮定すると、貪欲戦略はできるだけ早くwを小さくすることができる.wを100少なくすることができるなら、できるだけ100を少なくすることができます.そうすれば、私たちが次に直面する局面はw-100を集めることです.長期的な生活経験は、貪欲な策略が正しいことを示している.しかし、もし私たちが紙幣の額面を変えたら、貪欲な策略は成立しないかもしれません.奇抜な国の紙幣の額面がそれぞれ1、5、11であれば、私たちが15を集めたとき、貪欲な策略は間違います:15=1×11+4×1(欲張り策略で5枚の札を使った)15=3×5(正しい策略で、3枚の札しか使わない)
作者:チェン行止
リンク:https://www.zhihu.com/questio...
出典:知っている
著作権は作者の所有である.商業転載は著者に連絡して許可を得てください.非商業転載は出典を明記してください.
1つ目の場合,貪欲な戦略を用いるとすぐに答えが得られるが,条件が少し変わると正解が得られないことがわかる.欲張りアルゴリズムこの問題では,毎回最も額面の大きい紙幣を選択し,最終的に調達するWの量を急速に減少させたが,例の特殊な状況では,初めて最大の額面11の紙幣を選択すると,後に1元札を4枚しか選択できず,最終的に得られる解は正しくない.動的計画は暴力的列挙に基づいて計算を繰り返すことは避けられたが,各サブ問題は考慮され,貪欲アルゴリズムは毎回,残りの状況を考慮せずに現在の最適解を短視的に選択したと言える.最後に考えて、この特殊な額面札の問題をダイナミックな計画で解決してみましょう.
スキャンコードは微信の公衆番号に注目する.