貪欲法が失敗する場合を見抜く
信頼する前に反例を見つけます
「貪欲法が失敗する場合を見抜く」はCoddyKit上の無料Competitive Programming Academyレッスンです。 これはレッスン4/4です。 下記で完全なレッスンを無料で読むことができます。その後、ブラウザ内の組み込みコードエディタと24時間対応のAIチューターでハンズオン演習できます。 これはCompetitive Programming Academy学習パスの一部であり、ウェブとCoddyKitアプリ全体で進捗が同期されます。 Competitive Programming Academyコースには全4レッスンが含まれています。
貪欲法は魅力的
貪欲法は短く、高速で、明らかに正しそうに見えます。だからこそ、あなたを陥る罠にかけることがあります。きれいなアイデアが正しいとは限りません。⚠️
コイン交換の罠
コインが1、3、4の場合、貪欲法で6を作ると4を選び、次に1を2枚使うため、合計3枚になります。本当の最適解は3を2枚使う方法です。
何が間違っていたのか
最大のコインを選ぶことは局所的には有利でしたが、全体最適を妨げました。貪欲法は選択を取り消せないため、2枚で済む解を見逃したのです。
反例を見つける
最も速い確認方法は、小さな反例を探すことです。つまり、貪欲法と真の最適解が異なる小さな入力です。1つ見つかれば、その方法を退けられます。
0/1ナップサック再び
分割できないアイテムでは、比率による貪欲法は失敗します。価値密度の高い小さなアイテムが、それを合わせると上回る2つのアイテムを締め出すことがあるからです。分割できる自由が欠けていたのです。
選択が影響し合うとき
1つのアイテムを選ぶことで、ほかのアイテムがまだ選ぶ価値があるかどうかが変わるなら、貪欲法はしばしば破綻します。複雑に絡み合う依存関係があるなら、DPを検討してください。
ストレステストを行う
遅い全探索とランダムなジェネレーターを書き、何千もの小さなケースで両者を比較してください。1つでも不一致があれば、問題点が明らかになります。
for _ in range(10000):
t = random_case()
assert greedy(t) == brute(t)交換テスト
貪欲法を信頼するには、交換論法を証明できるか試してみてください。貪欲法で選んだものが、ある最適解に適合することを示せないなら、疑ってかかるべきです。
サブルーチンとしての貪欲法
貪欲法だけで答え全体を求められない場合でも、大きなDPや探索の中の構成要素として使えることがあります。証明によって安全だと分かる箇所で使ってください。
制約を読む
Nが小さいなら、そもそも貪欲法は必要ないことがよくあります。全探索やDPで間に合う場合があり、正しさに関するリスクも完全に避けられます。
得点を守る習慣
貪欲法でよさそうだと判断して提出する前に、1分だけ反例を探してください。この小さな確認が、つらい誤答判定を防ぎます。
クイックチェック
貪欲法が間違っているかもしれないと考えています。
まとめ
一部のコイン集合や0/1ナップサックのように、局所的な勝利が全体最適を妨げると、貪欲法は失敗します。信頼する前に反例を探し、ストレステストを行いましょう。🚀
AI チューターと学ぶ Python — 無料
ブラウザでリアルコードを書いて実行し、24/7 の AI チューターから瞬時にサポートを受け、ウェブまたはアプリで続きから学習できます。
- コース
- 30
- レッスン
- 120
よくある質問
「貪欲法が失敗する場合を見抜く」レッスンは無料ですか？
はい。「貪欲法が失敗する場合を見抜く」の完全なテキストはこのウェブで無料で読めます。インタラクティブに演習し（組み込みコードエディタと24時間対応のAIチューター）、Competitive Programming Academyコースの残りをアンロックするには、CoddyKit PROにアップグレードしてください。 Competitive Programming Academyコースには全4レッスンが含まれています。
「貪欲法が失敗する場合を見抜く」で何を学びますか？
信頼する前に反例を見つけます ブラウザで直接実行するハンズオンコードでCompetitive Programming Academyを演習し、24時間対応のAIチューターがレッスンを進める中での質問に答えます。
Competitive Programming Academyを始めるのに経験は必要ですか？
事前経験は必要ありません。CoddyKitのCompetitive Programming Academyは初級者から上級者向けに構成されているため、ここから始めるか最初から始めて、自分のペースで進むことができます。 これはレッスン4/4です。
「貪欲法が失敗する場合を見抜く」レッスンにはどのくらい時間がかかりますか？
ほとんどのCoddyKitレッスンは約5～10分かかります。各レッスンはコンパクトでインタラクティブなので、着実に進歩し、ウェブとアプリ全体で正確に前回の場所から再開できます。
このCompetitive Programming Academyレッスンでコードを書いて実行できますか？
はい。すべてのCompetitive Programming Academyレッスンに組み込みコードエディタが含まれているため、ブラウザでリアルコードを書いて実行し、即座のAIフィードバックを取得できます。ローカル設定は不要です。
このコースのすべてのレッスン
- 貪欲法の考え方
- 終了時刻が早い順のアクティビティ選択
- 比率による分割可能ナップサック
- 貪欲法が失敗する場合を見抜く