アルゴリズム4)グリディ

グリディ

グリディは、瞬間ごとに最高に見えるアルゴリズムを選択します.

現在の選択は今後の影響を考慮しておらず、一瞬ごとに良いものを選んだのではなく、最終的に良いものを選んだ.

階調アルゴリズム問題は、基準に基づいて選択されたアルゴリズムであり、問題の中で「最大順」、「最小順」などの基準を知らない場合には、ソートを使用する必要があるため、階調アルゴリズムの問題はソートアルゴリズムとペアで発生することが多い.

1)Griddyアルゴリズム例-おつり

質問する

カウンターにはお釣りに使える500元、100元、50元、10元硬貨が無限に存在します.お客様に渡すお金はN元のペアでお探しのコインの最低個数です.△でも、おつりはいつも10の倍数です.

問題の説明

グリディアルゴリズムでこの問題を解決すれば、最大の通貨単位からお金を探すことができます.N元を探す時、まず500元を探して、それから100元、50元、10元の順序で探して、最も少ない硬貨の数はすべて探すことができます.

問題を解く

n = 1260
count = 0

# 큰 단위의 화폐부터 차례로 확인
coin = [500, 100, 50, 10]

for i in coin:
    count += n // i
    n %= i
    
print(count)

小銭を探す問題で、グリディアルゴリズムの正確性

グリディアルゴリズムで問題の解法を見つけるときは,その正しさを研究すべきである.小銭を探す問題は、持っている硬貨の中の大きな単位が常に小さい単位の倍数であるため、小さな単位の硬貨を総合して他の解を導くことができないため、GRADYアルゴリズムで最適解を求めることができる.
800元を探す場合、通貨単位は500元、400元、100元で、GRIDアルゴリズムは4つの硬貨(500元+100元)です.×3)探す必要があるが、この場合、最適な年は2枚の硬貨(400ウォン)だ.×2)おつりを出す.
したがって,Griddyアルゴリズムを用いて問題を解決する際には,Griddyアルゴリズムが常に最適解の正当性を求めることができるかどうかを調べる必要がある.

2)グリディアルゴリズムと動的プログラミングの比較

グリディアルゴリズムと動的プログラミングは最適な局所構造問題を解決する上で類似している.

の違いは次のとおりです.

グリディアルゴリズムは,各段階において局所最適解を探索し,問題を縮小した.

Dynamic Programmingサブ問題の最適な解決策を探し、これらの結果を組み合わせた情報に基づいてグローバル最適な解決策を選択します.

上図では、ステップ毎に局所最適解を選択する階調アルゴリズムで解くと、9+20+32=61となる.

上図で最適解を見つけ、最適解の情報に基づいてダイナミックプログラミングを使用してグローバル最適解を選択する場合は、9+12+99=120を選択します.