座標圧縮

座標圧縮

座標圧縮 というアルゴリズムを使うと、効率的に問題を解くことができるケースがあります。

[問題]

２次元のマップがあり、何もない通り抜けのできる空間(.)と通り抜けのできない壁(#)が設定されています。

壁によって分断されている領域は何個あるでしょうか。

解法・ソースコード

この問題では、前後の行または列に 変化がない場合 その行または列を省いても、壁によって分断される 領域の個数 は変わりません。

まず、同じ行があったらその行を削除し、次に同じ列があったらその列を削除するという処理を行います。

[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
#---------- 入力例 ----------
# .が空間、#が壁
mp = '''...#....#.
...#....#.
...#....#.
######..#.
...#....#.
...#.....#
...#.....#
##########
...#.....#
...#.....#'''
#----------------------------

mp_compress = {}  # 縦と横を圧縮したデータ

print(' 【 圧縮前 】 ')
print(mp)
print()

# 縦を圧縮
lst = []    # 縦を圧縮したデータ
pre = ''    # １行前のデータ（初期化）
for line in mp.split():
    if pre != line:
        lst.append(line)
    pre = line
# 横を圧縮
pre = ''  # １列前のデータ（初期化）
w = 0
for col in range(len(lst[0])):  # 列ごとにループ
    row = [l[col] for l in lst] # 1列分のデータを取得
    line = ''.join(row)
    if pre != line:
        for y, s in enumerate(list(line)):
            mp_compress[w, y] = s
        w += 1
    pre = line

print(' 【 圧縮後 】 ')
for y in range(len(lst)):
    for x in range(w):
        print(mp_compress[x,y], end='')
    print()

[実行結果]

 【 圧縮前 】
...#....#.
...#....#.
...#....#.
######..#.
...#....#.
...#.....#
...#.....#
##########
...#.....#
...#.....#

 【 圧縮後 】
.#..#.
###.#.
.#..#.
.#...#
######
.#...#

問題なく座標が圧縮され、壁に分断されている領域の数も変わっていないことが確認できました。

次に、圧縮されたマップに対して分断されている領域のカウントを行います。

これは、まず壁ではない地点をみつけ、そこからつながっている部分を 壁（#） に置き換えるという操作を繰り返します。

一回の深さ優先探索で、始めの壁ではない地点からつながっている空間(.)が全て壁(#)に変わるので、深さ優先探索を行った回数 が解となります。

[Google Colaboratory]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
# 深さ優先探索(Depth-First Search)
def dfs(x, y):
    global mp_compress
    # 今いるところを#に置き換え
    mp_compress[x, y] = '#'
    for dx, dy in [(1,0), (-1,0), (0,1), (0,-1)]:
        pos = (x + dx, y + dy)
        if pos in mp_compress and mp_compress[pos] == '.':
            dfs(pos[0], pos[1])
# 領域を数える
cnt = 0
for pos,v in mp_compress.items():
    if v == '.':
        dfs(pos[0], pos[1])
        cnt += 1
print('解：', cnt)

[実行結果]

解： 6

解は 6 となり、壁により分断されている空間が６つであることが確認できました。

二分探索④：平均最大化（全４回）

平均最大化

二分探索 を使って、平均最大化問題 を解いてみます。

問題

重さと価値がわかっている品物が複数あります。

この中から、ｋ個選んだ時の重さあたりの価値の最大値を求めてください。

ソースコード

この問題は 重さあたりの価値がｘ以上となるように選ぶことができるかどうか という関数を定義し、二分探索で最大のｘを求める ことで解くことができます。

関数としては、それぞれの品物に対して（価値 - 重さあたりの価値[x] × 重さ）を計算し、この結果の大きいほうからｋ個の和を求めて、それが０以上かどうかで判定します。

[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
#------ 入力例 ------
k = 2           # 選択する個数
# それぞれの品物の重さと価値
items = [{'weight':2, 'value':2},
         {'weight':5, 'value':3},
         {'weight':2, 'value':1}]
#--------------------
# 重さあたりの価値[x]が実現可能かどうか
def check(x):
    # それぞれの品物に対して、（価値 - 重さあたりの価値[x] × 重さ）を計算する
    res = [item['value'] - x * item['weight'] for item in items]
    res = sorted(res, reverse=True) # 大きいほうからソート
    return sum(res[:k]) >= 0  # 大きいほうからｋ個の和が０以上かどうか

# 解の存在範囲を初期化
lb, ub = 0, 999
for _ in range(100):      # 十分な回数繰り返す
    mid = (lb + ub) / 2   # 解の存在範囲の中央値
    if check(mid):        # 中央値が実現可能かどうか
        lb = mid
    else:
        ub = mid
print('解：', lb)

[実行結果]

解： 0.75

解は 0.75 となりました。

品物の価値と重さを確認すると、１つめと３つめの品物を選んで重さあたりの価値を計算すると (2 + 1) / (2 + 2) = 0.75 となり 最大値 となっていることが確認できます。

二分探索③：最小値の最大化（全４回）

最小値の最大化

前回に引き続き、二分探索 を使って 最小値の最大化 を求める問題を解いてみます。

問題

おじいさんがＮ個の小屋を作りました。小屋は直線状に並んでいます。

おじいさんは馬をＭ頭飼っていますが、それぞれの馬ができるだけ離れるように

小屋にいれたいと考えています。

最も近い２頭の馬の間隔を 最大化 するためには馬をどのように

小屋に入れたらよいでしょうか。

ソースコード

この問題は、ある条件を満たす最大値を求める問題です。

下記のような手順で問題を解いていきます。

  1. 小屋の位置を昇順にソートする。
  2. 最初の馬を１番目の小屋に入れる。
  3. 次の馬を２番目の小屋にいれて、ある間隔を確保できるかどうかチェックする。
  4. もし間隔があけられなければ、次の小屋に移動し再び間隔のチェックを行う。
  5. ある間隔を確保できたら、（間隔を確保できた）小屋の位置を基準にして次の馬を入れる小屋の位置を同じようにチェックする。
  6. 途中で小屋がなくなったら、条件を満たすことができなかったと判定する。
  7. 最後の馬まで小屋にいれることができたら条件を満たせたと判定する。
  8. 2～7の判定を二部探索を使って、解の存在範囲（馬同士の間隔）を狭めながらチェックする。

[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
#------ 入力例 ------
m = 3       # 馬の頭数
lst = [1, 2, 8, 4, 9]   # 小屋の位置
#--------------------
n = len(lst)    # 小屋の数

# 条件を満たす距離かどうかを判定
def check(d):
    last = 0              # 小屋の位置①
    for _ in range(m - 1):# 最初の馬は１番目の小屋に入れるので（馬の頭数 - １頭）分ループする
        crt = last + 1    # 小屋の位置②
        # 小屋の位置が存在し かつ
        # 小屋の位置①と小屋の位置②がある距離[d]未満だったら
        while crt < n and lst[crt] - lst[last] < d:
            crt += 1      # 小屋の位置２を後ろにずらす（距離[d]を確保するため）
        if crt == n:      # 最後の小屋の位置をこえたら
            return False  # 条件を満たさない
        last = crt        # 条件を満たしたので、小屋の位置①を小屋の位置②に移動
    return True           # すべての馬を小屋にいれられたので条件を満たす

lst = sorted(lst)   # 小屋の位置を昇順にソート

# 解の存在範囲を初期化
lb = 0
ub = 9999
# 条件を満たすかどうか解の存在範囲を狭めながらチェックする
while ub - lb > 1:
    mid = (lb + ub) // 2
    if check(mid):
        lb = mid
    else:
        ub = mid
print('解：', lb)

[実行結果]

解： 3

馬の間隔を３ずつあければうまく馬をいれられることが分かりました。

つまり 位置１，４，９ の小屋に馬を格納すれば、最も近い２頭の馬の 間隔を最大化 することができることになります。

二分探索②：解を仮定して判定（全４回）

解を仮定して判定（最大値）

二分探索 を使うと、ある条件を満たす最大値を求めるときに非常に有用です。

問題

Ｎ本の紐 があり長さはそれぞれ異なります。

これらの紐を切って、同じ長さの紐をＫ本 作るときの 最長の長さ を求めなさい。

答えは小数点以下２桁までを切り捨ててください。

ソースコード

区間の 下端ｌｂを条件満たす値 に、上端ｕｂを条件を満たさない値 にそれぞれ初期化し、解の存在範囲（ｌｂ、ｕｂ）が十分小さくなるまで、中央の値が条件を満たすかどうか判定し存在範囲を狭めていきます。

最終的に、ｌｂが求めたい 最大の値 となります。

[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
#------ 入力例 ------
lst = [8.12, 7.53, 4.47, 5.29]  # 各紐のながさ
k = 11           # 作りたい同じ長さの紐の本数
#--------------------
n = len(lst)    # 紐の本数

# 長さｘの紐をｋ本作れるかどうか
def check(x):
    cnt = sum([int(l / x) for l in lst])
    return cnt >= k

lb = 0         # 初期化（下限の範囲）
ub = 999999    # 初期化（上限の範囲）

# 解の存在範囲が十分狭くなるまで繰り返す
for _ in range(99):
    mid = (lb + ub) / 2
    if check(mid):
        lb = mid
    else:
        ub = mid

# 小数点第２までを切り捨て
print(('解: {:.2f}').format(lb * 100 // 100))

[実行結果]

解: 2.00

長さが２ であれば、１１本の同じ長さの紐 が作れることを導き出すことができました。

解を仮定して判定（最小値）

上記の処理と同様にある条件を満たす 最小値 を求めることもできます。

区間の 下端ｌｂを条件満たさない値 に、上端ｕｂを条件を満たす値 にそれぞれ初期化し、解の存在範囲（ｌｂ、ｕｂ）が十分小さくなるまで、中央の値が条件を満たすかどうか判定し存在範囲を狭めていきます。

最終的に、ｕｂ が求めたい 最小の値 となります。

二分探索（全４回）

二分探索とは

二分探索 とは、解の存在範囲を狭めていくことにより最適解を求める手法（アルゴリズム）です。

二分探索で検索

二分探索 で解けるもっとも基本的な問題は、数列から 特定の数字を検索 する問題です。

数列は昇順にソートされている必要があります。

問題

昇順にソートされた数列から、ある数字ｋ以上となるような最小のインデックス（数字の位置）を求めてください。

ソースコード

処理としては、まず中央の値に着目します。

中央の値がｋ以上であれば 解が中央の位置よりも下 にあることがわかるので、上限の位置を中央に ずらします。

中央の値がｋ以下であれば 解が中央の位置よりも上 にあることがわかります、下限の位置を中央に ずらします。

こうすることにより、１回の比較で解の存在の範囲を 半分に絞る ことができます。

これ以降、句点の中点での比較を繰り返すことで解の存在の範囲を絞っていき解を求めます。

[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
#----- 入力例１ -----
lst = [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15]
k = 5
#----- 入力例２ -----
# lst = [-10,4,6,100,200,400,500]
# k = 10
#----- 入力例３ -----
# lst = range(99999999999)
# k = 30000
#--------------------
n = len(lst)

# 解の存在範囲を初期化
lb = -1   # 下限の範囲
ub = n    # 上限の範囲

while ub - lb > 1:
    mid = (lb + ub) // 2
    if lst[mid] >= k:
        ub = mid
    else:
        lb = mid
print('解', ub)

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

解 4

インデックス4 の位置の数値は5であり、ｋと一致します。

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

解 3

数列に10は存在しませんが、インデックス3 の位置の数字100はｋ(=10)よりも大きくなります。

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

解 30000

非常に大きな数列 に対しても、二分探索であれば効率的に検索することができます。

次回からは 二分探索 を応用していろいろな問題を解いていきます。

NetworkX⑥（最短経路問題）

最短経路問題

複数の経路の中から、最も効率の良い経路 を求める問題を 最短経路問題 といいます。

「効率のよい」という意味としては、「時間が短い、費用が安い、距離が短い」などさまざまな基準があります。

NetworkX では、このような基準を weight として数値化します。

まず、最短経路を求めるグラフを定義し、図示してみます。

[Google Colaboratory]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
import networkx as nx

G = nx.DiGraph()

# 始点ノード、終了ノード、重さ(weight)を定義
G.add_weighted_edges_from(
    [('A', 'B', 4), ('A', 'C', 3), ('B', 'C', 1), ('B', 'D', 1), ('B', 'E', 5), 
     ('C', 'F', 2), ('D', 'E', 3), ('F', 'E', 1), ('E', 'G', 2), ('F', 'G', 4), ]
)

# ノードの位置（グラフ描画用） => ノード名:(横位置, 縦位置)
pos = {'A': (0, 1), 'B': (1, 2), 'C': (1, 0), 'D': (2, 1), 'E': (3, 2),
       'F': (3, 0), 'G': (4, 1)}

edge_labels = {}
for (i, j) in G.edges():
    edge_labels[i, j] = f"{ G[i][j]['weight'] }"

nx.draw(G, pos=pos, with_labels=True, node_size=500)
nx.draw_networkx_edge_labels(G, pos, edge_labels=edge_labels)

[実行結果]

ダイクストラ法

最短経路問題 を解くためには、NetworkX の dijkstra_path_length関数 を使います。

[Google Colaboratory]

1
2
3
4
5
6
7
8
# ダイクストラ法で最短経路とその重み（最小コスト）を求める
start, end = "A", "G"
shortest_path = nx.dijkstra_path(G, start, end)
shortest_path_weight = nx.dijkstra_path_length(G, start, end)

# 出力
print("Shortest Path:", shortest_path)
print("Weight:", shortest_path_weight)

[実行結果]

Shortest Path: ['A', 'C', 'F', 'E', 'G']
Weight: 8

最短経路は ‘A’ ➡ ‘C’ ➡ ‘F’ ➡ ‘E’ ➡ ‘G’ となり、最小コスト（トータルの重さ）は 8 であることを導き出すことができました。

NetworkX⑤（最小カット問題）

NetworkXを、使って 最小カット問題 を解いてみます。

最小カット問題

グラフに対してｓからｔへのパスが存在しなくなるために除去しなければいけない辺の 容量の和の最小値 を求める問題を 最小カット問題 といいます。

前回記事で使ったグラフをもう一度作成します。

[Google Colaboratory]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
import networkx as nx

G = nx.DiGraph()

#(始点，終点，重み)でエッジを設定
G.add_edges_from([('s', '1', dict(capacity=10)),
                  ('s', '2', dict(capacity=2)),
                  ('1', '2', dict(capacity=6)),
                  ('1', '3', dict(capacity=6)),
                  ('3', '2', dict(capacity=3)),
                  ('2', 't', dict(capacity=5)),
                  ('3', 't', dict(capacity=8)),
])

#エッジラベルの描画時に'capacity'の表示を無くすための工夫
edge_labels = {(i, j): w['capacity'] for i, j, w in G.edges(data=True)}
pos = nx.spring_layout(G, k=10)
nx.draw_networkx_edge_labels(G,pos, edge_labels=edge_labels)

# グラフの描画
nx.draw_networkx(G, pos)

[実行結果]

解法

最小カット問題 を解くためには、minimum_cut関数 を使います。

引数には、グラフオブジェクト、始点ノード、終了ノード を設定します。

[Google Colaboratory]

1
2
3
4
5
cut_value, partition = nx.minimum_cut(G, 's', 't')
print(f'cut value: {cut_value}')

S, T = partition
print(f'  (S, T): ({S}, {T})')

[実行結果]

cut value: 11

  (S, T): ({'1', '2', 's'}, {'3', 't'})

始点側のノードの集合は {‘1’, ‘2’, ‘s’} で、終点側の集合は {‘3’, ‘t’} となりました。

この集合２つをつなぐエッジ（辺）の容量の和は 11 であり、これが最小となります。

最小カット問題 の解は 最大流問題 と解は同じとなり、最大流最小カット定理 と呼ばれます。

NetworkX④（最大流問題）

NetworkXを、使って 最大流問題 を解いてみます。

最大流問題

グラフ間に流れる数値を最大化させる問題を 最大流問題 といいます。

[最大流問題の例]

ネットワーク上の２台のコンピュータｓ、ｔがありｓからｔにデータを送ります。

このネットワークには全部でＮ台のコンピュータがあり、いくつかのコンピュータ間は一方向性の

通信ケーブルで接続されていて、それぞれ１秒間に通信できる最大のデータ量が決まってきます。

ｓからｔへ１秒間で最大どれだけのデータを送信することができるでしょうか。

まず、ネットワーク上のコンピュータとデータ量をグラフに表示してみます。

[Google Colaboratory]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
import networkx as nx

G = nx.DiGraph()

#(始点，終点，重み)でエッジを設定
G.add_edges_from([('s', '1', dict(capacity=10)),
                  ('s', '2', dict(capacity=2)),
                  ('1', '2', dict(capacity=6)),
                  ('1', '3', dict(capacity=6)),
                  ('3', '2', dict(capacity=3)),
                  ('2', 't', dict(capacity=5)),
                  ('3', 't', dict(capacity=8)),
])

#エッジラベルの描画時に'capacity'の表示を無くすための工夫
edge_labels = {(i, j): w['capacity'] for i, j, w in G.edges(data=True)}
pos = nx.spring_layout(G, k=10)
nx.draw_networkx_edge_labels(G,pos, edge_labels=edge_labels)

# グラフの描画
nx.draw_networkx(G, pos)

[実行結果]

解法

最大流問題 を解くためには、maximum_flow関数 を使います。

引数には、グラフオブジェクト、始点ノード、終了ノードを設定します。

[Google Colaboratory]

1
2
3
4
5
6
7
flow_value, flows = nx.maximum_flow(G, 's', 't')
print(f'maximum flow: {flow_value}')

caps = nx.get_edge_attributes(G, 'capacity')
for u in nx.topological_sort(G):
    for v, flow in sorted(flows[u].items()):
        print(f'  ({u}, {v}): {flow}/{caps[(u, v)]}')

[実行結果]

maximum flow: 11

  (s, 1): 9/10

  (s, 2): 2/2

  (1, 2): 3/6

  (1, 3): 6/6

  (3, 2): 0/3

  (3, t): 6/8

  (2, t): 5/5

ｓからｔへの最大流は 11 と導き出すことができました。

また、最大流が流れる際に各ノード間に流すデータ通信も表示しています。

NetworkX③（パス／閉路／放射状の描画）

NetworkX を使っていろいろなタイプの描画を行ってみます。

パス

まずは パス を描画します。

add_path関数 に複数のノード番号を設定します。

[Google Colaboratory]

1
2
3
4
5
6
7
8
import networkx as nx

G = nx.DiGraph()  # 有向グラフ (Directed Graph)

# 指定したパス上の頂点と辺を追加
nx.add_path(G, [1, 2, 3, 4, 5])  # 1 → 2 → 3 → 4 → 5

nx.draw_networkx(G)

[実行結果]

順番に ノードを辿ったグラフ が描画されました。

閉路

次に 閉路 を描画します。

add_cycle関数 に複数のノード番号を設定します。

[Google Colaboratory]

1
2
3
4
5
6
7
8
import networkx as nx

G = nx.DiGraph()  # 有向グラフ (Directed Graph)

# 指定した閉路上の頂点と辺を追加
nx.add_cycle(G, [1, 2, 3, 4, 5])  # 1 → 2 → 3 → 4 → 5 → 1

nx.draw_networkx(G)

[実行結果]

順番にノード番号を辿り、最後のノードから最初の番号に戻る 閉路グラフ を描画することができました。

放射状

最後に 放射線状 のグラフを描画します。

add_star関数 に複数のノード番号を設定します。

[Google Colaboratory]

1
2
3
4
5
6
7
8
import networkx as nx

G = nx.DiGraph()  # 有向グラフ (Directed Graph)

# 放射状に頂点と辺を追加
nx.add_star(G, [1, 2, 3, 4, 5])  # 1 → 2, 1 → 3, 1 → 4, 1 → 5

nx.draw_networkx(G)

[実行結果]

最初のノードから、２番目以降のノード全てにエッジのある 放射上のグラフ を描画することができました。

NetworkX②（ノード削除、エッジ削除）

ノード削除

今回はグラフからノードを削除してみます。

まずは、前回記事と同様のグラフを描画します。

[Google Colaboratory]

1
2
3
4
5
6
7
8
9
10
11
12
13
import networkx as nx

G = nx.DiGraph()  # 有向グラフ (Directed Graph)

# 頂点の追加
G.add_node(1)                
G.add_nodes_from([3, 4, 5])

# 辺の追加 (頂点も必要に応じて追加されます)
G.add_edge(1, 2)     
G.add_edges_from([(1, 3), (2, 5), (3, 4), (4, 5)])

nx.draw_networkx(G)

[実行結果]

上記のグラフから、ノード（頂点）を削除してみます。

[Google Colaboratory]

1
2
3
# 頂点の削除 (削除された頂点に接続されている辺も削除されます)
G.remove_node(5)            # 頂点を１つ削除
G.remove_nodes_from([3, 4]) # 頂点を複数削除

[実行結果]

ノードが削除されました。

また削除されたモードに合わせてエッジも削除されていることが確認できます。

エッジ削除

今度はグラフからエッジを削除してみます。

まずグラフ図を描画します。

[Google Colaboratory]

1
2
3
4
5
6
7
8
9
10
11
12
13
import networkx as nx

G = nx.DiGraph()  # 有向グラフ (Directed Graph)

# 頂点の追加
G.add_node(1)                
G.add_nodes_from([3, 4, 5])

# 辺の追加 (頂点も必要に応じて追加されます)
G.add_edge(1, 2)     
G.add_edges_from([(1, 3), (2, 5), (3, 4), (4, 5)])

nx.draw_networkx(G)

上記のグラフから、エッジ（辺）を削除してみます。

[実行結果]

[Google Colaboratory]

1
2
3
# # 辺の削除
G.remove_edge(3, 4)                   # 辺を１つ削除
G.remove_edges_from([(1, 3), (2, 5)]) # 辺を複数削除

[実行結果]

エッジ（辺）が削除されました。