二次元配列でマップ問題を解く

二次元配列でマップ問題を解く

次のような問題を考えます。

[問題]

長方形状のマップデータ(文字列)が与えられます。

1マスを1文字のデータで表し、'#'が爆弾、'.'が何もない空間(空きマス)を表現します。

空きマスの上下左右および斜めの8方向に隣接しているマスの中に

爆弾のあるマスが何個あるかを調べて、その数を空きマス'.'に置き換えて

長方形状のマップを出力してください。

[条件]

・マップの縦幅と横幅は1以上かつ50以下です。

・1マスのデータは'#'(爆弾)または'.'(何もない空間)の2種類です。

解法・ソースコード

長方形のマップを表すために、str型のリスト を活用します。

長方形状のマップを上から y番目、左から x番目 のマスを (x, y) と表します。

入力の文字列データを1マスずつの 2次元配列(2次元リスト) に設定します。(14行目)

この問題では、各空きマス (x, y) に対して、その周囲8マスにある爆弾の個数を数えます。

マス(x, y)の周囲8マスは (x+1, y)、(x-1, y)、(x, y+1)、(x, y-1)、(x+1, y+1)、(x+1, y-1)、(x-1, y+1)、(x-1, y-1) と表すことができます。

これらのマスを調べるために、周囲8方向に隣接するマスとの座標の 差分値を表す配列 を用意しておくと便利です。(17行目)

[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
#---------- 入力例 ----------
# .が空間、#が爆弾
mp = '''........
..#...#.
........
....#...
.....#..'''
#----------------------------
print('【 元のマップ 】 ')
print(mp)
print()

# 入力データを二次元配列に設定
res = [list(line) for line in mp.split('\n')]

# 隣接8方向への相対位置を定義
dxy = [(1, 0), (-1, 0), (0, 1), (0, -1), (1, 1), (1, -1), (-1, 1), (-1, -1)]

for y, row in enumerate(res): # 縦ループ
for x, s in enumerate(row): # 横ループ
if s == '.': # 空きマスの場合
res[y][x] = 0 # 初期化(周囲の爆弾数)
for dx, dy in dxy: # 8方向をループ
x1, y1 = x + dx, y + dy # マスの周囲をx1,y1とする
# マップ外の場合はパス
if x1 < 0 or x1 > len(row) - 1 or y1 < 0 or y1 > len(res) - 1:
pass
elif res[y1][x1] == '#': # 周囲が爆弾'#'の場合
res[y][x] += 1 # 爆弾数カウントアップ

print('【 隣接する爆弾の個数を表示したマップ 】 ')
for row in res:
print(*row, sep='')

[実行結果]

【 元のマップ 】 
........
..#...#.
........
....#...
.....#..

【 隣接する爆弾の個数を表示したマップ 】 
01110111
01#101#1
01121211
0001#210
00012#10

空きマスの周辺にある 爆弾数をカウント してマップを表示することができました。

全探索

全探索

次のような問題を考えます。

[問題]

500円玉がA枚、100円玉がB枚、50円玉がC枚あります。

これらの硬貨の中から何枚かを選び、合計金額をちょうどX円にする方法は

何通りありますか。

[条件]

・それぞれの枚数A、B、Cは0以上かつ50以下の整数。

・目標金額Xは50以上かつ20000以下の50の倍数。

・それぞれの枚数の合計(A+B+C)は1以上。

解法・ソースコード

この問題は、各硬貨の枚数分 それぞれループを回して 目標の金額 になるかどうかをチェックすることで解くことができます。(三重ループしながら金額をチェック)

それぞれの硬貨数は 0枚 の時があるので、ループ回数は 各硬貨の枚数分 + 1 となることに注意してください。

[Google Colaboratory]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#---------- 入力例 ----------
a = 2 # 500円玉の枚数
b = 2 # 100円玉の枚数
c = 2 # 50円玉の枚数
x = 100 # 目標金額
#----------------------------
res = 0 # 何通りあるかという解
# 全探索
for a1 in range(a + 1): # 500円玉の枚数分ループ
for b1 in range(b + 1): # 100円玉の枚数分ループ
for c1 in range(c + 1): # 50円玉の枚数分ループ
# 合計金額がX円に一致した場合
if 500 * a1 + 100 * b1 + 50 * c1 == x:
# それぞれの硬貨の枚数を出力
print(f'500円{a1}枚、100円{b1}枚、50円{c1}枚')
res += 1 # 解をカウントアップ
print('解:', res)

[実行結果]

500円0枚、100円0枚、50円2枚
500円0枚、100円1枚、50円0枚
解: 2

解は 2通りとなりました。

硬貨の組み合わせは、合計金額が一致 した場合のそれぞれの硬貨数を表示することで確認できます。

反転

反転問題

次の問題を解いていきます。

[問題]

N頭の牛 が1列に並んでいて、それぞれの牛は前か後ろのいずれかを向いています。

農夫は全ての牛を前向きにするために、牛を回転する機械を買うことにしました。

この機会は購入時に 数K を設定する必要があり、1回の操作で K頭の連続する

牛 の向きを反転させることができます。

全ての牛を前向きにするために必要な最小の 操作回数M と、それを達成する

最小のK を求めてください。

解法・ソースコード

まず、一番左端の牛 に注目します。この牛を含む区間は1つしかありません。

したがって、この牛が前を向いているならば、その区間は反転させる必要がありません。

逆に、この牛が後ろを向いているならば、その区間は反転させる必要があります。

そして、これ以降はこの1番左の区間は考える必要がなくなります。

これを繰り返し行うことによって、必要な最小の反転回数を求めることができます。

また、計算量 を落とすためにリストfを定義し、区間を反転させた場合はそうでない場合はを設定し、その合計値が奇数である場合は最初の向きとは逆に、そうでなければ最初の向きのままとなっていることを確認しています。

[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
#---------- 入力例 ----------
cows = 'BBFBFBB' # F:前向き、B:後ろ向き
#----------------------------
n = len(cows) # 牛の頭数
k = 1 # 求める最小の牛を回転させる連続頭数(初期化)
m = n # 求める最小の操作回数(初期化)

# 牛を回転させる連続頭数kを固定した時の最小操作回数を求める
# 解が存在しない場合は -1 を返す
def calc(k):
# 区間[i, i + k - 1 ]を回転させたかどうか
f = [0 for _ in range(n)]
res = 0 # 操作回数
total = 0 # リストfの和
for i in range(n - k + 1):
if (dir[i] + total) % 2 != 0: # 先頭の牛が後ろを向いている場合
# 回転操作を行う
res += 1
f[i] = 1
total += f[i]
if i - k + 1 >= 0:
total -= f[i - k + 1]
# 残りの牛が前を向いているかどうかチェック
for i in range(n - k + 1, n):
if (dir[i] + total) % 2 != 0:
return -1
if i - k + 1 >= 0:
total -= f[i - k + 1]
return res

# 牛の方向を0(F:前向き),1(B:後ろ向き)に変換
dir = [0 if x == 'F' else 1 for x in list(cows)]

for i in range(1, n + 1): # 牛の頭数分ループする
print(i, '頭回転させる機械の場合')
x = calc(i)
if x >= 0 and m > x: # 牛を全部前向きにでき、かつ操作回数がより少ない場合
print(x, '回操作で牛を全部前向きにできる。')
m = x # 最小の操作回数を更新
k = i # 回転させる最小の連続頭数を更新
else:
print('牛の向きを全部前向きにするとはできない。')
print()

print(f'解:回転させる最小の連続頭数={k} 最小の操作回数={m}')

[実行結果]

1 頭回転させる機械の場合
5 回操作で牛を全部前向きにできる。

2 頭回転させる機械の場合
牛の向きを全部前向きにするとはできない。

3 頭回転させる機械の場合
3 回操作で牛を全部前向きにできる。

4 頭回転させる機械の場合
牛の向きを全部前向きにするとはできない。

5 頭回転させる機械の場合
牛の向きを全部前向きにするとはできない。

6 頭回転させる機械の場合
牛の向きを全部前向きにするとはできない。

7 頭回転させる機械の場合
牛の向きを全部前向きにするとはできない。

解:回転させる最小の連続頭数=3 最小の操作回数=3

牛を連続で 3頭回す機械 を購入すれば、最小3回の操作 で牛を全部前向きにできることが分かりました。

座標圧縮

座標圧縮

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

[問題]

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

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

解法・ソースコード

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

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

[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 = '' # 1行前のデータ(初期化)
for line in mp.split():
if pre != line:
lst.append(line)
pre = line
# 横を圧縮
pre = '' # 1列前のデータ(初期化)
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()

[実行結果]

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

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

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

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

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

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

[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 となり、壁により分断されている空間が6つであることが確認できました。

二分探索④:平均最大化(全4回)

平均最大化

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

[問題]

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

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

ソースコード

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

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

[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 # 大きいほうから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 となりました。

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

二分探索③:最小値の最大化(全4回)

最小値の最大化

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

問題

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

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

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

最も近い2頭の馬の間隔を 最大化 するためには馬をどのように小屋に入れたらよいでしょうか。

ソースコード

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

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

 1. 小屋の位置を昇順にソートする。
 2. 最初の馬を1番目の小屋に入れる。
 3. 次の馬を2番目の小屋にいれて、ある間隔を確保できるかどうかチェックする。
 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 # 小屋の位置1
for _ in range(m - 1):# 最初の馬は1番目の小屋に入れるので(馬の頭数 - 1頭)分ループする
crt = last + 1 # 小屋の位置2
# 小屋の位置が存在し かつ
# 小屋の位置1と小屋の位置2がある距離[d]未満だったら
while crt < n and lst[crt] - lst[last] < d:
crt += 1 # 小屋の位置2を後ろにずらす(距離[d]を確保するため)
if crt == n: # 最後の小屋の位置をこえたら
return False # 条件を満たさない
last = crt # 条件を満たしたので、小屋の位置1を小屋の位置2に移動
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

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

つまり 位置1,4,9 の小屋に馬を格納すれば、最も近い2頭の馬の 間隔を最大化 することができることになります。

二分探索②:解を仮定して判定(全4回)

解を仮定して判定(最大値)

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

[問題]

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

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

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

ソースコード

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

最終的に、[lb] が求めたい 最大の値 となります。

[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) # 紐の本数

# 長さxの紐をk本作れるかどうか
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

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

[実行結果]

解: 2.00

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

解を仮定して判定(最小値)

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

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

最終的に、[ub] が求めたい 最小の値 となります。

二分探索①(全4回)

二分探索とは

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

基本

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

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

問題

昇順にソートされた数列から、ある数字k以上となるような最小の

インデックス(数字の位置)を求めてください。

ソースコード

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

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

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

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

これ以降、範囲内にある中央位置の値 で比較を繰り返すことで解の存在の範囲を絞っていき解を求めます。

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

[実行結果](入力例1)

解 4

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

[実行結果](入力例2)

解 3

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

[実行結果](入力例3)

解 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)

[実行結果]

ダイクストラ法

最短経路問題 を解くためには、NetworkXdijkstra_path関数dijkstra_path_length関数 を使います。(3~4行目)

[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を、使って 最小カット問題 を解いてみます。

グラフに対してs(始点ノード)からt(終了ノード)へのパスが存在しなくなるために除去しなければいけない辺の 容量の和の最小値 を求める問題を 最小カット問題 といいます。

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

[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)

[実行結果]

解法

最小カット問題 を解くためには、NetworkXの 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’} となりました。

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

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

© 2022 PythonとRPAで遊ぶ All Rights Reserved.