貪欲法

どのような順で選択をするか

どのような基準が適当か

順番に関して

問題で与えられるケース

操作を繰り返した結果の最小化など

マトロイドなどの場合、大きくしたい値の大きいものからなので自明

区間スケジューリングで「区間の終了でソート」は自明でない

こういうケースでどう考えれば良いか

いくつか案はある

最大化したい値の大きい方から

それぞれの選択肢の利得の和を最大化するようなケースで、足し算に単調性があるから

制約が厳しい順

影響範囲の広い方から

後で決めるものが先の選択の最適解に影響しない

影響範囲包含関係の外側から内側へ

選択肢減少の少ない順

最も選択肢をたくさん残すものを選ぶ

選択肢の集合が包含関係にあり、一番外側のものを選ぶ

数直線やグラフの端から

見た目でわかりやすいのでこう考えがちだが、端からであることによって「選択肢減少が少ない」「選択肢が少ない」などが導かれてる

マトロイド上の貪欲法

重みの大きい順に「既に選んだ要素の集合に追加してもFの要素であるなら追加」を繰り返す

閉路を作らないように辺を選んで最小全域木を作る問題

辺の長さが短い順に「既に選んだ辺と閉路を作らないなら選ぶ」を繰り返す

マトロイド上の貪欲法をグラフ的マトロイドに適用したもの

共通部分がないようになるべく多くの区間を選ぶ問題

区間の終了が早い順に「既に選んだものと共通部分がないなら選ぶ」を繰り返す

選ばれた「区間の終了」よりも前に区間の開始がある区間は今後選ぶことができない

つまり最も区間の終了が早いものを選ぶのは、最も選択肢を残すもの

数1に対して2通りの操作のどちらかを行う。操作をN回行った結果の最小値が欲しい

2つの操作のどちらも「操作前の数が小さければ結果も小さい」という性質を持っている

各操作ごとに結果の小さくなる方を選べば良い

単調性

時間軸順に「操作の結果が小さい方を選ぶ」を繰り返す

コインの問題

ある金額をコインで支払いたい、コインの枚数を最小化したい

コインの金額が手前のコインの倍数である、という性質がある

大きいコインで払えるだけ払えばいい

コインが大きい順に「払えるだけ払う」を繰り返す

コインAがコインBの倍数である場合、コインAを1枚減らすことによる金額の不足をBで払う方法が2枚以上のBを使うしかなく、必ず枚数が増える

倍数でない場合、例えば5,4,1で8を払う場合、5を1枚減らして、1も3減らして4を2枚で払うことができて-2枚、というパターンがある

コインの金額が倍数であることで「あまり」がゼロであり、より小さなコインの枚数を気にしなくて良くなる

15,5,3,1みたいなケースも9で同じ

文字列Sの先頭もしくは末尾の1文字を取ってTに追加していく、Tを辞書順最小にしたい

辞書順という基準に「先に出てくる文字が小さければ後の文字がどうであれ辞書順で小さい」という性質がある

Sを反転したS'を用意する

時間軸順に「SとS'のうち辞書順で小さいものを選び先頭文字を取る」を繰り返す

数直線上にN個の点がある。そのうちのいくつかを選び「選ばれた点から距離R以内の範囲」に全ての点が含まれるようにしたい。選ぶ点の数を最小化せよ

数直線を左から順に「既に選んだ点によって覆われてない点を覆える最も右の点を選ぶ」を繰り返す

最短経路を求める問題

訪問済み頂点を始点1つで初期化する

「未訪問で、訪問済み頂点から1本の辺で到達可能な頂点をその始点からの距離が短い順」に「選ぶ」を繰り返す

辺の距離が正であることが前提

辺の距離が正なので「未訪問で、訪問済み頂点から1本の辺で到達可能な頂点のうち始点からの距離が最も短いV」は、他の未到達頂点を経由する最短経路を持たないため

二つの数列A,Bが与えられる、i番目のボタンを押すとA0〜Aiがインクリメントされる。全てのiについてAiをBiの倍数にしたい。ボタンを押す回数を最小化せよ

iの大きい順に「AiとBiが条件を満たす最小限の回数押す」を繰り返す

影響範囲の包含関係で、iの大きなものは小さなものを包含するので、小さなものは大きなものに影響を与えない

ナップサックっぽい問題

商品が何種類かあり、その価値と個数が与えられる、商品がN個入るナップサックがある、ナップサックに入れた商品の価値を最大化せよ

いわゆるナップサック問題と違って「1個の分割できない商品の重さ」ではなく「個数」なので分割ができるところが重要

価値の大きい順に「あるだけ選ぶ」を繰り返す

二つの頂点集合A,Bと、その頂点の位数が与えられる。条件を満たす二部グラフがあるか判定せよ

Aの適当な順に「Bから最も残り位数の高い頂点を選び接続する」を繰り返す

最も選択肢を減らさない行動

人が荷物を持っている、荷物を交換して本来の持ち主が持ってる状態にしたい。人によって持てる最大の重さが異なり、重いものを持つとその後交換できなくなる

荷物を重い順に「本来の持ち主と交換」を繰り返す

「本来の持ち主と交換」は常にできる

それによって受け手が行動不能になるかもしれないが、既に本来の荷物を持ってるから問題ない

送り手が受け取るものは常に「持っていたものより軽い」

それ以外の順番だと「戻ってきたものが重すぎる」が発生しうる

二択の差でソート

選択肢A/Bの利得がそれぞれAi/Bi、K個Aを選ぶ、利得を最大化したい

「Ai-Biの大きい順」にK個「Aを選ぶ」を繰り返す

「Aを選ぶ」したAi+Bi, しない時 -Ai, 最小の選択で合計を正にしたい

「2*Ai+Biの大きい順」に合計が正になるまで「Aを選ぶ」を繰り返す

与えられた列を昇順に並び替える

値が小さい順に「先頭に持ってくる」を繰り返す

数のペアの差の最小化

偶数個の数がある、2個ずつペアにして、差を最小化したい

値が小さい順に「次の数とペアにする」を繰り返す

最小の数を次の数以外とペアにした場合、必ず損をする

0/1の列S,Tが与えられる、Sに対して、1を一つ左にずらすか、2つ並んだ1を0にするかのどちらかの操作を行える、最小手数でTに一致させよ

Sの前から順に「Tの自分より左に未解決の1があるならずらす、ないなら消す」を繰り返す

区間がたくさん与えられる、ある点を指定すると、その点を含む区間が全て取り除かれる。最小個数の点ですべての区間を取り除きたい

区間の終了の早い順に「終了の直前を選ぶ」を繰り返す

これは「終了が最も早い区間」を取り除く方法の中で、一番他の区間への影響が大きい選択肢である

正の数列H,Sが与えられる、添え字iがKi番目に選ばれ、H+SKの最大値を最小化したい、Kを構成せよ

Hの順でもSの順でもダメ

最大値の上界Xを導入して実現できるかどうかの判定問題にする

(X-H)/Sの小さい順に「選択」を繰り返す

意味合い: Xを超えない選択肢の少ない順に選択

正の数列Ai,Biがある、添え字をK個選んで、ABそれぞれの和の比率を最大化したい

比率がX以上かどうかの判定問題にすれば式変形によって(Bi-XAi)の単なる和になる、これの最大化は大きい方から選ぶ貪欲法でOK

(Bi-XAi)の大きい順に「選ぶ」を繰り返す

---

たくさんの問題へのリンク

POJ3253

蟻本p.49

ちょっと複雑

貪欲法の正当性の検証的なやり方で2 択に絞り込まれる

桁DPで解いたが貪欲でもできる

貪欲法で最適解が導ける問題とそうでない問題

コイン問題「大きな額のコインから使えるだけ使う」で最適になるコインとそうでないコイン

1,4,5はダメ

離散最適化基礎論 第 5 回 マトロイドとグラフの全域木

離散凸解析の理論とアルゴリズム