貪欲法で実装されるアルゴリズムまとめ by Python

「貪欲法」という名前の響きからすると、物事を選択するN段階のステップに対して考えられるすべての遷移を走査するような印象を受けますが、さにあらず。それは動的計画法の手法です。

貪欲法は、１ステップ先のみを考えて最適な選択を繰り返す手法です。

そんな貪欲法についてアルゴリズムをまとめます。
①組合せアルゴリズムへの適用
・スケジューリング問題への適用
・最適化問題への適用
②グラフアルゴリズムへの適用
・ダイクストラ法
・クラスカル法

①組合せアルゴリズムへの適用

スケジューリング問題への適用

開始時間と終了時間の指定されたN個の仕事の中から、実行時間を被らせることなく選択できる仕事の最大の数を計算する。

Scheduling.py

# 区間スケジューリング問題を解く貪欲法
# 計算量　：O(NlogN)

# アルゴリズム定義 
def scheduling(N, schedule):
    schedule.sort(key=lambda x:x[1]) 

    res = 0
    current_end_time = 0
    for i in range(N):
        if schedule[i][0] < current_end_time:
            continue

        res += 1
        current_end_time = schedule[i][1]

    return res

# 入力受取
N = int(input())

# スケジュール用意
schedule = []
for i in range(N):
    schedule.append(list(map(int, input().split())))

# アルゴリズム実行
scheduling(N, schedule)

# 入力
# 6
# 9 16
# 11 15
# 10 12
# 15 18
# 19 23
# 13 19

# 出力
# 3

最適化問題への適用

N個のボタンのi番目を1度押すと、N個の数列A（A0,A1,...,AN-1)に対してA0〜Aiの値が1増加する時、数列Aのすべての数字に対して、i番目の数字をN個の数列B（B1,B1,...BN-1）のi番目の数字の倍数にするために、ボタンを押さなければならない最少の回数を計算する。

MultipleArray.py

# AtCoder Grand Contest 009
#  A - Multiple Array

# アルゴリズム定義
def Calc(A, B, N):
    sum_ = 0

    for i in range(N-1, -1, -1):
        A[i] += sum_
        amari = A[i] % B[i]
        D = 0
        if amari != 0:
            D = B[i] - amari
        sum_ += D

    print(sum_)

# 入力受取
A = list(map(int, input().split()))
B = list(map(int, input().split()))
N = len(A)

# アルゴリズム実行
Calc(A, B, N)

# 入力
# 13 34 56
# 4 9 9

# 出力
#11

②グラフアルゴリズムへの適用

ダイクストラ法

N個の頂点とM個の辺からなる非負の有向グラフGにおいて、頂点0を始点として全頂点への最短路長を求める。

Dijkstra.py

# ダイクストラ法
# 計算量：O(|V|^2)

# アルゴリズム定義
def dijkstra(N, G, dist, used):
    for i in range(N):
        min_dist = 10000
        min_v = -1
        for v in range(N):
            if used[v] == False and dist[v] < min_dist:
                min_dist = dist[v]
                min_v = v

        if min_v == -1:
            break

        for e in range(len(G[min_v])):
            if dist[G[min_v][e][0]] > dist[min_v] + G[min_v][e][1]:
                dist[G[min_v][e][0]] = dist[min_v] + G[min_v][e][1]

        used[min_v] = True

    for v in range(N):
        if dist[v] < 10000:
            print(dist[v])
        else:
            print(10000)

# 入力受取
N, M, s = map(int, input().split())

# グラフ生成
G = [[] for i in range(N)]
for i in range(M):
    a, b, w = map(int, input().split())
    G[a].append([b, w])

# dp生成
used = [False for i in range(N)]
dist = [10000 for i in range(N)]
dist[s] = 0

# アルゴリズム実行
dijkstra(N, G, dist, used)

# 入力
# 6 9 0
# 0 1 3
# 0 2 5
# 1 2 4
# 1 3 12
# 2 3 9
# 2 4 4
# 3 5 2
# 4 3 7
# 4 5 8

# 出力
# 0
# 3
# 5
# 14
# 9
# 16

クラスカル法

N個の頂点とM個の辺からなる連結な重み付き無向グラフの各辺の重みをw(i)とする時、全域木Tの重みw(T)として考えられる最小値を求める。

Kruskal.py

# クラスカル法
# 計算量：O(|E|log|V|)

# アルゴリズム定義
def Kruskal(N, M, edges):
    # グラフの並び替え
    # 重みの小さい順に並び替え
    edges.sort()

    res = 0    
    uf = UnionFind(N)
    for i in range(M):
        w = edges[i][0]
        u = edges[i][1][0]
        v = edges[i][1][1]

        if uf.issame(u, v):
            continue

        res += w
        uf.unite(u, v)

    print(res)

# Union-Find木定義
class UnionFind():
    par = []
    siz = []

    def __init__(self, x):
        self.par = [-1 for n in range(x)]
        self.siz = [1 for n in range(x)]

    def root(self, x):
        if self.par[x] == -1:
            return x
        else:
            self.par[x] = self.root(self.par[x])
            return self.par[x]

    def issame(self, x, y):
        if self.root(x) == self.root(y):
            return True
        else:
            return False

    def unite(self, x, y):
        x = self.root(x)
        y = self.root(y)
        if x == y:
            return False
        if self.siz[x] < self.siz[y]:
            x, y = y, x
        self.par[y] = x
        self.siz[x] += self.siz[y]
        return True

# 入力受取
# 頂点数、辺数
N, M = map(int, input().split())

# グラフの生成
# 辺(u,v)と重みwの集合
edges = ["" for i in range(M)]
for i in range(M):
    u, v, w = map(int, input().split())
    edges[i] = [w, [u, v]]

# アルゴリズム実行
# クラスカル法
Kruskal(N, M, edges)

# 入力
# 4 6
# 0 1 10
# 1 2 20
# 2 3 30
# 3 0 40
# 1 3 15
# 0 2 45

# 出力
# 45