Union Find木を使って問題を解く

前回記事で実装した Union Find木 を使って、下記の問題を解いてみます。

[問題]

人 1 から 人 N までのN 人の人がいます。

「人Ai と人 Bi は友達である」という情報が M 個与えられます。

同じ情報が複数回与えられることもあります。

X と Y が友達、かつ、Y と Z が友達ならば、X と Z も友達です。

また、M 個の情報から導くことができない友達関係は存在しません。

いじわるな高橋君は、このN人をいくつかのグループに分け、全ての人について「同じグループの中に友達がいない」という状況を作ろうとしています。

最小でいくつのグループに分ければ良いでしょうか？

[条件]

・人数Nは、2以上 200000以下です。

・友達関係の数Mは、0以上 200000以下です。

・AiとBiは、1以上 N以下です。

・AiとBiは、異なる数字です。

[解き方]
Union Find木 を使って友達同士のグループを作ります。

同じグループの中に友達がいない 状況を作るためには、友達の数が一番多いグループの人数分グループ数に分ければよいことになります。

[Google Colaboratory]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

n = 5
lst = [(1, 2), (3, 4), (5, 1)]
#-----------入力２---------------
# n = 4
# lst = [(1, 2), (2, 1), (1, 2), (2, 1), (1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4)]
#-----------入力３---------------
#n = 10
#lst = [(3, 1), (4, 1), (5, 9), (2, 6)]
#--------------------------------
uf = UnionFind(n)   # 前回記事で実装した「Union Find木」を使う

for l in lst:       # 友達関係から友達グループを作成する
    uf.union(l[0]-1, l[1]-1)

ans = 0             # 友達がいない状況をつくるためのグループ数
for g in uf.all_group_members().values():   # 友達グループごとにループ
    print(f'友達グループ', g)               # 友達グループのメンバー
    g_size = len(g)         # 友達の数
    # 友達の数が「友達がいない状況をつくるためのグループ数」より大きかったら
    if g_size > ans:
        ans = g_size        # グループ数に友達数を設定

print('答え =>', ans)

[実行結果（入力１の場合）]

友達グループ [0, 1, 4]
友達グループ [2, 3]
答え => 3

１つ目の友達グループが３人ともっとも人数が多いので、３グループに分ければよいことになります。

例えば｛0, 2｝｛1, 3｝｛4｝と分ければ、だれも友達がいないグループとなります。

[実行結果（入力２の場合）]

友達グループ [0, 1, 2, 3]
答え => 4

４人全員が友達なので、４グループに分けて全員をばらばらにする必要があります。

[実行結果（入力３の場合）]

友達グループ [0, 2, 3]
友達グループ [1, 5]
友達グループ [4, 8]
友達グループ [6]
友達グループ [7]
友達グループ [9]
答え 3

１つめの友達グループが３人ともっとも人数が多いので、３グループに分けます。

友達が２人の場合は、３グループのうちいずれかの２グループに振り分ければよいですし、友達がいない人は、３グループのどこに分けても友達関係はできません。

Union Find木

Union Find木 は、グループ分けを管理することができるデータ構造です。

次のようなことを効率的に行うことができます。

• 要素aと要素bが同じグループに属しているかどうかをチェックする。
• 要素aと要素bのグループを一つにまとめる。

グループ同士をまとめることはできますが、要素をグループから除いたり、グループを分けたりすることはできません。

Union Find木 を実現するためのクラスは以下のようになります。

[Google Colaboratory]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

from collections import defaultdict

# n個の要素を0 ～ n - 1のインデックスで管理する
class UnionFind():
    def __init__(self, n):
        self.n = n                # 要素の数
        self.parents = [-1] * n   # 各要素の親要素の番号を格納するリスト

    def find(self, x):            # 要素[x]が属するグループの親を返す
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):        # 要素[x]が属するグループと要素yが属するグループとを併合
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.parents[x] > self.parents[y]:
            x, y = y, x
        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):            # 要素[x]が属するグループのサイズ（要素数）を返す
        return -self.parents[self.find(x)]

    def same(self, x, y):         # 要素[x],要素[y]が同じグループに属するかどうかを返す
        return self.find(x) == self.find(y)

    def members(self, x):         # 要素[x]が属するグループに属する要素をリストで返す
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):              # すべての親の要素をリストで返す
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):        # グループの数を返す
        return len(self.roots())

    def all_group_members(self):  # 全グループの全要素を返す
        group_members = defaultdict(list)
        for member in range(self.n):
            group_members[self.find(member)].append(member)
        return group_members

    def __str__(self):  # printでの表示用。ルート要素: [そのグループに含まれる要素のリスト]を文字列で返す
        return '\n'.join(f'{r}: {m}' for r, m in self.all_group_members().items())

動作確認

実装した Union Find木 の動作を確認してみます。

要素数5個（0,1,2,3,4）のUnion Find木を定義し、[0,1]のグループと[2,3,4]のグループに分けます。

[Google Colaboratory]

1
2
3
4
5
6

uf = UnionFind(5)
uf.union(0, 1)
uf.union(2, 3)
uf.union(3, 4)

print(uf)

[実行結果]

0: [0, 1]

2: [2, 3, 4]

２つのグループに分けることができました。

親の要素(一番もとになる要素)がグループのキーとなっていることが確認できます。

次に、要素1と要素3が所属するグループを調べてみます。

[Google Colaboratory]

1
2

print(uf.find(1))
print(uf.find(3))

[実行結果]

0

2

要素1がグループ0に所属し、要素3がグループ2に所属していることが分かりました。

今度は、要素0,要素2が同じグループに属するかどうかと、要素3,要素4が同じグループに属するかどうかを調べます。

[Google Colaboratory]

1
2

print(uf.same(0, 2))
print(uf.same(3, 4))

[実行結果]

False

True

要素0,要素2は違うグループであり、要素3,要素4は同じグループに属することを確認できました。

最後に、要素3が所属するグループの全要素を表示します。

[Google Colaboratory]

1

print(uf.members(3))

[実行結果]

[2, 3, 4]

要素3が所属するグループの全要素は、2,3,4であることが分かりました。

次回は、Union Find木 を使って問題を解いてみます。

線形計画問題

線形計画問題 は、ある条件下での 領域の最大・最小 を求める問題です。

数理最適化ライブラリのPuLP を使うと、線形計画問題 を解くことができます。

[問題]

ある工場では製品 p と製品 q を製造しています。

製品 p と製品 q を製造するには原料 m と原料 n が必要で、次のような条件となっています。

・製品 p を１ｋｇ製造するには原料 m が１ｋｇ、原料 n が２ｋｇ必要。

・製品 q を１ｋｇ製造するには原料 m が３ｋｇ、原料 n が１ｋｇ必要。

・原料 m の在庫は３０ｋｇ、原料 n の在庫は４０ｋｇあります。

・単位量当たりの利益は、製品 p が１万円、製品 q が２万円です。

この条件で利益を最大にするためには、製品 p と製品 q をそれぞれ何ｋｇ製造すればよいでしょうか。

製品 p の製造量を x ｋｇ、と製品 q の製造量を y ｋｇとすると以下のように不等号をつかった式にまとめることができます。

x + 3y ≦ 30
2x + y ≦ 40
x ≧ 0、y ≧ 0

連立方程式との違いは、等号（==） が 不等号（≧、≦） になっている点です。


 ソースコード

上記の条件式をもとにソースコードを作成すると下記のようになります。

[Google Colaboratory]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
import pulp

# 第１引数は任意の名前、第２引数は最大化問題を解く指定
problem = pulp.LpProblem('Test', pulp.LpMaximize)

x = pulp.LpVariable('x')    # 製品pを製造する量。変数xをpulp.LpVariable関数を定義。
y = pulp.LpVariable('y')    # 製品qを製造する量。変数yをpulp.LpVariable関数を定義。

# 線形計画問題の条件式
problem += 1 * x + 3 * y <= 30
problem += 2 * x + 1 * y <= 40
problem += x >= 0
problem += y >= 0

problem += x + 2 * y        # 目的関数。最大化する式。

status = problem.solve()    # 数理モデルを解く

print('Status:', pulp.LpStatus[status])   # 結果
print('x =', x.value(), 'y =', y.value(), 'obj =', problem.objective.value()) # xとyの解と利益の関数値


[実行結果]
Status: Optimal

x = 18.0 y = 4.0 obj = 26.0


製品 p の製造量を １８ｋｇ、と製品 q の製造量を ４ｋｇとしたときに利益を最大にできることが導きだされました。
obj = 26.0 は最大化しようとした利益の関数値です。（15行目）
x + 2 * y = 26 となることが確認できます。

      
    

数理最適化

数理最適化ライブラリ PuLP を使って、連立一次方程式を解いてみます。

本来の数理最適化ライブラリの使い方とは少々異なりますが、数理モデルを初めて実装するにはとてもよい題材です。

[問題]

１個１２０円のリンゴと１個１５０円のミカンを合わせて１０個買ったら代金の合計が１４４０円でした。

リンゴとミカンをそれぞれ何個買ったでしょうか。

この問題は、リンゴの個数を x、ミカンの個数を y として連立一次方程式を立てることができます。

120x + 150y = 1440
x + y = 10

 ソースコード

まずは 数理最適化ライブラリ PuLP をインストールできます。

[Google Colaboratory]
1
!pip install pulp


連立一次方程式をソースコードにすると下記のようになります。

[Google Colaboratory]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
import pulp

# 第１引数は任意の名前、第２引数は最大化問題を解く指定（今回は連立一次方程式を解くのでとくに意味はない）
problem = pulp.LpProblem('Test', pulp.LpMaximize)

x = pulp.LpVariable('x')    # 変数xをpulp.LpVariable関数を定義
y = pulp.LpVariable('y')    # 変数yをpulp.LpVariable関数を定義

problem += 120 * x + 150 * y == 1440    # 連立一次方程式を定義
problem += x + y == 10                  # 連立一次方程式を定義

status = problem.solve()    # 数理モデルを解く

print('Status:', pulp.LpStatus[status])   # 結果
print('x =', x.value(), 'y =', y.value()) # xとyの解


[実行結果]
Status: Optimal
x = 2.0 y = 8.0


Optimal は、最適化計算をした結果最適解が得られたという意味です。
リンゴの個数は2、ミカンの個数は8となり、合わせて１０個 であり、代金の合計も １４４０円 で、連立一次方程式の解として正しいことが確認できます。

      
    

部分和問題

深さ優先探索では、一番はじめの状態から遷移を繰り返すことで 全ての状態 を生成します。

したがって、すべての状態に対して操作 を施したり、全状態を列挙 することが可能です。

[問題]

整数が n個 与えられます。

その中からいくつか選び、その和をちょうど k にすることができるか判定してください。

[条件]

・整数の個数 n は、1以上20以下
・各整数の値は、-100000000以上100000000以下
・目標とする数値（部分和） k は、-100000000以上100000000以下

[解き方]
各整数を１つ目から順番に加えるかどうかを決めていき、n個すべてについて決め終わったら、その和が k に等しいかどうかを判定します。

再帰関数を使用します。

[Google Colaboratory]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

# ------------ 入力例１ ----------
lst = [1, 2, 4, 7]    # 各要素
k = 13                # 目標とする数値（部分和）
# ------------ 入力例２ ----------
# lst = [1, 2, 4, 7]  # 各要素
# k = 15              # 目標とする数値（部分和）
# --------------------------------
def dfs(i, total):
    print(i,total)
    if i == len(lst):       # 全部決め終わった場合
        return total == k   # 今までの和が[目標とする数値]と等しいかどうかを返す
    
    if dfs(i + 1, total):   # lst[i]を使わない場合
        return True
    
    if dfs(i + 1, total + lst[i]):  # lst[i]を使う場合
        return True

    # lst[i]を使うか使わないかにかかわらず[目標とする数値]がつくれないので False を返す
    return False

if dfs(0, 0):
    print('Yes')
else:
    print('No')

[実行結果（入力例1）]

Yes

2 + 4 + 7 を足し合わせると 13 になるので Yes が解となります。

[実行結果（入力例2）]

No

どんな組み合わせを行っても 15 となることはないので No が解となります。