Python3で実装問題解決力を鍛える！アルゴリズムとデータ構造【第７章】設計技法(5)：貪欲法

貪欲法のポイント

単調増加など、単調性が構造的にみられる（ことが多い）。

ソートすれば貪欲でいけるなということがままある。

問題設定によっては必ずしも最適解にならない。

貪欲法によって最適解が求められる理由を考えられることが重要。（少なくとも例外が思いつかないにしても感覚的にこう考えれば、次ステップのことだけ考えれば十分だなと思えるなど）

章末問題

7.1 有名問題

$n$ 個の整数列 $a$ からいくつかと $n$ 個の整数列 $b$ からいくつかを選んでペアを作る。
ただし、各ペア $a_i \lt b_j$ を満たす必要がある。
この時、最大で何ペア作れますか？

ちょっと問題を把握し切れていない・・・例が欲しい。

7.2 2D Plane 2N Points

出典は、この問題。

atcoder.jp 詳細は出典をみてもらうとして、ポイントは、

青い点で、最もx座標が小さいものにおいて、赤の点と仲良しペアになれる点が存在したら、
そのような点のうち最も y 座標が大きいものと仲良しペアする。

これが最適解かということが重要であるので、考えてみる。

手元にあるx座標が最も小さい青い点で、条件に合う赤の点の候補があるが、ペアになっていない場合。
- 候補のうち最もy座標が小さい赤の点(r1)をペアにする。
- 仮に、別の青い点と上記がペアになっているなら解消して組み換える。
- ペア数は少なくとも変わらないか、増えることになる。
手元にあるx座標が最も小さい青い点(b1)で、条件に合う赤の点の候補ではあるが、最もy座標が小さい赤い点ではないもの(r2)とペアになっている場合。
- r1がどれともペアじゃなければ、b1-r1と組み換える。
- r1が別の点b2とペアだった場合もb1-r1, b2-r2と組み換える。
  - b2はr1とペアになっていたのならば、 r1よりy座標が小さいr2とはペアに必ずなれる。(x座標もb2はb1よりも大きいので)

実装の流れは、

赤点の配列 $red$ を $b$ つまり、 $y$ 座標を基準に昇順にソートする。
青点の配列 $blue$ を $c$ つまり、 $x$ 座標を基準に降順にソートする。
$blue$ をforで回しながら、条件に合う $a$ を見つけたら、その $a$ をペアにしたよっていう辞書に書き込む。
$a$ のforをbreakする。

実装ができたが、これが $O(nlogn)$ になっているのか？これは $O(n^2)$ だよなー・・・わからん。
誰か教えて欲しいOrz

入力例は

def main():
    n = int(input())
    r = sorted([list(map(int, input().split())) for i in range(n)], \
        key=lambda x: x[1], reverse=True)
    b = sorted([list(map(int, input().split())) for i in range(n)])    
    done = dict()
    cnt = 0
    print('最大数の仲良しペアの例は')
    for bx, by in b:
        for rx, ry in r:
            if (rx, ry) in done:
                continue
            if rx < bx and ry < by:
                print('a:', rx, ry, 'b:', bx, by)
                done[(rx, ry)] = True
                cnt += 1
                break
    print(cnt)
if __name__ == '__main__':
    main()

7.3 Megalomania

問題の出典は以下。 atcoder.jp 概要は、

$n$ 個の仕事があり、 $i$ 番目の仕事は、 $d_i$ かかる。
締め切りは $t_i$ で同時に複数の仕事はできない。
時刻0から始めて、仕事が全て終わるかどうかを判定する。
ただし計算量が $O(Nlog(N))$ で。

締め切りが早い順に、こなしていって、終わらなかったら無理でしょ。ということで。手順としては、以下のように。

$[[d_0, t_0], [d_1, t_1], [d_2, t_2]...[d_{n-1}, t_{n-1}]]$ こんな感じで持つことになるので、 $t_i$ を基準にソートする。
その時点での仕事にかかった総合計時間( $d\_sum$ )とその仕事の締め切り時刻( $t$ )を比較して、総合計時間が大きくなったら、無理。
無事、総合計時間( $d\_sum$ )がその仕事の締め切り時刻( $t$ )を上回ることなく全てが終われば、可能。

入力は以下のような形を想定

def main():
    n = int(input())
    dt = [list(map(int, input().split())) for _ in range(n)]
    # O(nlogn)
    dt_s = sorted(dt, key=lambda x: x[1])
    print('bを基準にソート')
    print(dt_s)
    d_sum = 0
    # O(n)
    for d, t in dt_s:
        d_sum += d
        print('仕事時間の合計:', d_sum, 'この仕事の締め切り:', t)
        if d_sum > t:
            print('No')
            exit()
    print('Yes')
if __name__ == '__main__':
    main()

まとめ

貪欲は未来のことは考えず、すぐ次のステップのことだけ考えて今の最善を繰り返し行うことなので比較的イメージしやすい。
貪欲が必ずしも最善とは限らないことがあるので注意（今の選択が未来の選択に影響してしまう場合など）

終わりに

貪欲は比較的やりやすいが、前提が間違っていることもあって、その場合は、ミスるので貪欲でいけそうかどうかはしっかり考えてコードを書き始めるのがいい。

問題解決力を鍛える!アルゴリズムとデータ構造 (KS情報科学専門書)

作者:大槻兼資
発売日: 2020/10/02
メディア: 単行本（ソフトカバー）

くろたんく雑記帳

日常とか、わんちゃんとか、機械学習とか、競プロとか、