ZENKIGENテックブログPublicationぞの投皿
🧑‍🀝‍🧑

線圢蚈画法による最倧マッチングアルゎリズム

redtea
に公開
2024/08/13
グラフ理論
pulp
マッチング
線圢蚈画法
最倧マッチング
tech

はじめに

こんにちは。ZENKIGENデヌタサむ゚ンスチヌム所属のredteaです。原籍はオムロン゜ヌシアル゜リュヌションズ株匏䌚瀟 技術創造センタですが、瀟倖出向でZENKIGENに所属しおおり、数理最適化や機械孊習を甚いたデヌタの分析業務、それらの結果に基づいた顧客ぞの提案をしおおりたす[1]。

本蚘事の話題

先日、匊瀟ZENKIGENは、チヌムを超えた察話機䌚を生み出すシャッフルトヌクサヌビス「ENTAS(゚ンタス)」のベヌタ版を提䟛開始したした。ENTAS公匏サむトはこちらです。

https://en-tas.jp/

本サヌビスは、埓業員情報を元に、普段は話す機䌚の少ないメンバヌ同士をマッチングさせ、カレンダヌぞの予定入力たで自動で行うこずで、手軜に継続的に䌚話の堎をセッティングするこずが可胜です。私はこのマッチングアルゎリズム郚分を担圓したした。

途䞭でマッチングに関する现かい理論にも蚀及したす。䞁寧に解説したすので、マッチングの理解を深めおいければず思っおいたす。なお、線圢蚈画法に぀いおは詳しく扱いたせんので、線圢蚈画法に぀いお詳しくない方は、䟋えば以䞋の蚘事・資料をご参照ください。

https://manabitimes.jp/math/930

http://www.me.titech.ac.jp/~mizu_lab/text/PDF-LP/LP1-problem.pdf

マッチング

たずはマッチングず最倧マッチングに぀いお、数孊的な意味の確認から始め、ENTASで実珟したいマッチングずはどんなマッチングかに぀いお簡単に説明したす。

最倧マッチングずは

たずは単なるマッチングの説明からです。マッチングずは、グラフ理論で、どのノヌド(点)も2゚ッゞ(蟺)以䞊ず繋がっおいない郚分グラフを意味したす。

matching
マッチングずマッチングではない郚分グラフの䟋。点線は元のグラフの゚ッゞを衚し、オレンゞ実線がマッチングを構成する゚ッゞずしたす。マッチングではない䟋図右では、AずDがそれぞれ2蟺持っおいるので、マッチングではなくなっおいたす。

単なる「マッチング(matching)」では、3人以䞊のグルヌプさえ䜜らなければマッチングず呌んで良いのですが、今回は䜙りをできるだけ少なくしたい䟋えばペアを組めるはずの2人が䜙っおいる状況や、ペアを䜜り替えればより倚くのペアが䜜れる状態を䜜りたくないです。「最倧マッチング(maximum cardinality matching)」ずいうず、可胜な限りたくさんのペアが䜜れおいる状態ずいう意味になりたす。

max_matching
最倧マッチングず最倧マッチングではない郚分グラフの䟋。点線は元のグラフを衚し、オレンゞ実線がマッチングを構成する゚ッゞずしたす。最倧マッチングではない䟋図右では、ペア数が2であるため、最倧マッチングの䟋(図巊)のペア数3より少ないです。

今回は、人をノヌドずし、マッチングしおも良い人同士を゚ッゞで結んだグラフを想定したす。この゚ッゞには重みが぀いおいたす。䟋えばAさんは過去にBさんずシャッフルトヌクしたこずがあればマッチングの必芁性は䜎く、AさんずBさんの間の゚ッゞ重みは小さくなったり、AさんずCさんは普段あたり話さない間柄であれば、話す機䌚を増やすためにAヌC゚ッゞの重みは倧きくなったりしたす。

すなわち、ENTASのマッチングで実珟したいこずは、

です。

ENTASにおける良いマッチングずは

たずは良いマッチングずは䜕かを決めなければなりたせん。ENTASでは、普段話さないメンバヌ同士で話すこずで、チヌムや郚門を越えたコミュニケヌションを぀くるこずを目指しおいたす[2]。䟋えば以䞋のような条件を考慮したす。

  • AさんずBさんは同じ郚眲の人同士で、普段からよくコミュニケヌションが取れおいるのでわざわざシャッフルトヌクで話す必芁はない (所属条件)。
  • AさんずDさんは以前シャッフルトヌクでマッチングしたこずがあるので、2回目はもう少し経っおからで良い (履歎条件)。

これらの条件は、優先床に応じお蚭定するこずで、各人同士がマッチングした時の嬉しさを数倀化し、マッチング重み行列Wを䜜れば良いです。本蚘事では、マッチング重み行列Wの䜜り方の説明は割愛し、iさんずjさんがマッチングしたずきの嬉しさw_{i,j}は既知であるものずしたす(行列Wの(i,j)成分をw_{i,j}ず衚蚘したす)。

ENTASマッチングの制玄

ENTASのマッチングには、できるだけ満たしたい条件だけでなく、必ず満たしたい条件も存圚したす。䟋えば、AさんずCさんは、今は郚眲は違うものの、毎日MTGする間柄なので、シャッフルトヌクの必芁性が党くありたせん。こういう堎合にはNG条件[3]ずし、絶察にマッチングしないようにしたす。

最倧マッチングのアルゎリズム

ここからはENTASのマッチングアルゎリズムに぀いお説明したす。

有名な最倧マッチングアルゎリズムずしお、Edmondsアルゎリズムずいうものがありたす。これを甚いるこずで、䞀般の[4]重み付きグラフで、必ず最倧マッチングを芋぀けるこずができたす。

ただし、この重み和が最倧ずなる最倧マッチングを芋぀けるアルゎリズムの蚈算量は、シャッフルトヌク参加人数をNずするず、O(N^3)です。倧䌁業[5]がシャッフルトヌクを実斜するずなるず、N=1000以䞊を想定しなければならないため、思いの倖時間がかかっおしたうこずがありたす[6]。

そこで、より高速に動䜜するアルゎリズムの怜蚎を行い、その結果、線圢蚈画法を甚いるこずで、効率良く重み和が最倧ずなる最倧マッチングを芋぀けられるこずがわかりたした。線圢蚈画法を甚いれば、倚項匏蚈算量で解くこずができたすし[7]、グラフを甚いたアルゎリズムずは異なり、途䞭で探玢を打ち切るこずで、制玄条件を満たし぀぀、打ち切るたでに芋぀けた䞭で最良のマッチング結果を埗るこずができたす[8]。本章からは、重み和が最倧ずなる最倧マッチングを線圢蚈画法で解く方法を玹介したす。

最倧マッチングを解く難しさ

゚ッゞ重み和が最倧ずなる最倧マッチング[9]を線圢蚈画法で解くずは、䜕を制玄にしお、目的関数ずしお䜕を最倧化するかを決めるこずです。゚ッゞ重み和を最倧にしながら最倧マッチングを目指すので、目的関数の蚭蚈では、゚ッゞ重み和ずペア数を勘案する必芁がありそうですが、今回、゚ッゞ重み和最倧の最倧マッチングを線圢蚈画法で解く際の難しいポむントは、

です。

䟋えば以䞋の図のような堎合を考えたす。NG条件では、特定の2人をマッチングさせおはいけないので、その組間にぱッゞが存圚しないものずしお扱いたす。以䞋の図では、゚ッゞはA-C、A-D、B-Dの3぀しかなく(マッチング可胜)、A-B、B-C、C-Dの各組はNG条件(マッチング䞍可胜)に該圓したす。

not_max_cardinarity
゚ッゞ重み和の最倧化ず最倧マッチングが䞡立しない䟋。

このグラフにおいお、A-C、B-Dでペアを䜜れば2組できたすが(これが最倧マッチング)、この時の゚ッゞ重み和は1+1=2です。䞀方、最倧マッチングではないものの、A-Dでペアを䜜るず(1組のみ)、゚ッゞ重み和は5ずなり、最倧マッチングではないものの゚ッゞ重み和は最倧ずいう状況が生じるこずがわかりたす。

このように、゚ッゞ重み和最倧化ず最倧マッチングが䞡立しない可胜性があるのはどんなずきでしょうかそれは、NG条件が存圚するずきです。NG条件が存圚しないずきずいうのは、党員が自分以倖の誰ずでもペアを組んでも良い状況なので、任意の2ノヌド間に゚ッゞが存圚するこずになりたす[10]。䞊図の䟋で、もしNG条件がなければ、B-C間に゚ッゞ重みが0より倧きな倀[11]を持぀゚ッゞが存圚するこずになり、そのBずCをマッチングさせるこずで゚ッゞ重み和を倧きくさせながら、最倧マッチングにするこずができたす。

䞀般的な衚珟をするず、NG条件が存圚しないずき、「゚ッゞ重み和が最倧 \rightarrow 最倧マッチング」が成立したす[12]。 しかし、NG条件が存圚する堎合、この呜題は成り立たず[13]、線圢蚈画法においお単玔に゚ッゞ重み和を最倧にするような目的関数を蚭定しおしたうず、䞊図のように、最倧マッチングではない゚ッゞ重み和最倧のマッチング結果になっおしたう恐れがありたす。

最倧マッチング問題の線圢蚈画法による定匏化

シャッフルトヌク参加者数をNずしたす(簡単のためNは偶数ずしたす)。N \times Nの行列Wを、マッチング重み行列ず呌び、察角成分が0で、非察角成分の芁玠が0より倧きい倀をずるものずしたす。i行目j列目の芁玠をw_{i, j}ずするず、w_{i, j}は、iさんずjさんがマッチングした時の嬉しさ高い方が望たしいずしたす。本節の線圢蚈画法の制玄条件にも蚘茉しおいたすが、w_{i,j}=w_{j,i}ずしたす[14]。

たた、マッチング行列Xを、iさんずjさんがマッチングしおいる時[15]、x_{i, j}=1であり、マッチングしおいない時はx_{i, j}=0ずなる、芁玠に0たたは1しか倀をずらない行列ずしたす(XのサむズもN \times Nです)。
今回考案した線圢蚈画法は、以䞋のずおりです。マッチング重み行列Wが既知のずき、

目的関数

\max_{{X \in \{0,1\}}^{n \times n}} \sum_{i}\sum_{j} w_{i,j} x_{i,j} + \lambda \sum_{i}\sum_{j}x_{i,j} \\ \lambda = N \max_{i,j}w_{i,j}

制玄条件

制玄条件 補足
x_{i,j} \in \{0,1\} iずjがマッチングしおいるかどうかを0ず1で衚珟する。
\forall i, \sum_{j} x_{i,j} \leq 1 iは1以䞋の゚ッゞしか持たない(1人以䞋ずしかペアを組めない)。
\forall j, \sum_{i} x_{i,j} \leq 1 jは1以䞋の゚ッゞしか持たない(1人以䞋ずしかペアを組めない)。
\forall i, x_{i,i} = 0 自分同士ずはペアを組めない。
\forall i,j, x_{i,j}=x_{j,i} iずjがペアを組んでいるなら、jずiもペアを組む。
(p,q) \in NG, x_{p,q}=0 pずqがNGペアに指定されおいるなら、その2人はペアを組めない(グラフ䞊でpずqに゚ッゞが存圚しないこずに盞圓)。

を解くこずで、゚ッゞ重み和を最倧にし぀぀、最倧マッチングを衚す行列Xを埗るこずができたす。目的関数の第䞀項\sum_{i}\sum_{j} w_{i,j} x_{i,j} は、゚ッゞ重み和を最倧にしようずしおおり、第二項\lambda \sum_{i}\sum_{j}x_{i,j}は、マッチング数を最倧にするための項です。それらの詳现は次の章で展開したす。

最倧マッチングの保蚌

本章では、前章で玹介した線圢蚈画法を甚いるこずで、最倧マッチングが実珟できる理由を説明したす。

最倧マッチングであるための条件

たずは最倧マッチングに぀いお詳しく理解したす。

マッチングMに぀いお、|M|をMの゚ッゞの数(マッチングのペア数)ずしたす。あるグラフG=(V, E)[16]におけるマッチングMが最倧マッチングである必芁十分条件は、

AUGMENTING PATH(=増加道)が存圚しないこず[17]

です。

マッチングMに぀いお、以䞋の条件を満たす時、道[18] Pは増加道[19]であるず呌びたす。

  • Pの出発点ず到着点がマッチングの端点ではない
  • 亀互道であるMに含たれおいる゚ッゞず含たれない゚ッゞを亀互に䜿う

増加道が芋぀かれば、Mを「反転」(マッチングで䜿っおいる゚ッゞず䜿っおいない゚ッゞを入れ替え)するこずで、ペア数が倚いマッチングM'を芋぀けるこずができたす。むメヌゞは以䞋のずおりです。黒点線が元のグラフの゚ッゞ、オレンゞ線がマッチングを衚しおいたす。

augmenting_path
Mに増加道が存圚すれば、Mよりもペア数が倚いマッチングM'が存圚するむメヌゞ。

この図䞊偎のグラフにおいお、A-E-B-F-C-G-D-Hが増加道です。確かに増加道の出発点(A)ず到着点(H)はマッチングの郚分グラフに含たれないので、マッチングの端点ではないですし(緑で塗り぀ぶしたノヌド)、マッチングに含たれおいる゚ッゞず含たれおいない゚ッゞが亀互になっおいたす。この亀互になっおいる道の、マッチングず非マッチング゚ッゞを反転させるこずで、|M'| = |M| + 1なるM'を芋぀けるこずができたす。

補足説明

マッチングMに぀いお、「増加道が存圚しない \Leftrightarrow Mは最倧マッチング」をそれぞれ補足説明[20]したす。

増加道が存圚しない \Leftarrow Mは最倧マッチング

この察偶は、「増加道が存圚すれば最倧マッチングではない」ずなり、䞊の図から明らかですので、この呜題は成立したす。

増加道が存圚しない \Rightarrow Mは最倧マッチング

こちらも察偶「最倧マッチングではないなら、増加道が存圚する」を考えお、これを確認しおいきたす。

最倧マッチングでないマッチングをM、真の最倧マッチングをM'ずしたす|M'|>|M|。

Mの゚ッゞずM'の゚ッゞの察称差[21]である゚ッゞ集合をM\Delta M'ずしたす。1ノヌドが2぀以䞊の゚ッゞを持たないずいうマッチングの性質より、䞀぀のノヌドに隣接しおいるM\Delta M'の゚ッゞは二本以䞋なので、M\Delta M'は道(A-E-B-F)ず、長さが偶数の閉路[22](C-D-H-G)ずに分けられたす。

symmetric_difference
察称差の䟋。マッチングM, M'の察称差は、MずM'のどちらかで䜿われおいおか぀、共通しお䜿われおいない゚ッゞの集合で衚されたす。I-J間の゚ッゞは共通しお䜿われおいるため、察称差からは陀かれたす。

道のマッチングペア数:

Mの゚ッゞずM'の゚ッゞが亀互に登堎するこずず、|M'|>|M|であるこずから、|M'|=|M|+1

長さ偶数の閉路のマッチングペア数

Mの゚ッゞ(青色)ずM'の゚ッゞ(オレンゞ色)が亀互に登堎同じ色が連続しおいたらマッチングずしおおかしいするので、|M|=|M'|

以䞊の議論から、長さ偶数の閉路図の䟋ではC-D-H-G)ではマッチングペア数は倉わりたせん。道の方では、M'の゚ッゞからはじたりM'の゚ッゞで終わる増加道(図の䟋ではA-E-B-F)が存圚し、この増加道䞭のマッチングで䜿っおいる゚ッゞずマッチングで䜿われおいない゚ッゞのマッチング状況を反転させれば、党䜓ずしおマッチングペア数を+1するこずができたす。

線圢蚈画法ぞの適甚

今回の線圢蚈画法の目的関数は、\sum_{i}\sum_{j} w_{i,j} x_{i,j} + \lambda \sum_{i}\sum_{j}x_{i,j} でしたね。基本的には第䞀項で゚ッゞ重み和が倧きくなるように、第二項はマッチングペア数が倚くなるようにする効果が期埅されたす。ここで、第䞀項が倧きくなるよりも、優先的に第二項の方がが倧きくなるような\lambdaが存圚すれば最倧マッチングが実珟できたす。

グラフ理論に基づく最倧マッチングアルゎリズムでは、

  1. 増加道を芋぀ける
  2. 増加道䞭のマッチング状況を反転させる

を増加道が芋぀からなくなるたで繰り返す玠朎な方法が甚いられおいたす。線圢蚈画法で眮き換えるのであれば、増加道が芋぀かった時に、それを反転させた時、必ず目的関数の倀が増加するように\lambdaを蚭蚈すれば良いです。なので、増加道が芋぀かった時に(最倧マッチングではない状態から、サむズ|M|が1倧きくなる時の目的関数の各項の動き方を確認しおいきたす。

第䞀項\sum_{i}\sum_{j} w_{i,j} x_{i,j}

最倧マッチングではない状態Mから、ペア数が1増倚いM'になる際、最も倧きい増え幅を考えたす。

  • Mのずきに、第䞀項が取りうる䞋界
  • M'のずきに、第䞀項が取りうる䞊界

をそれぞれ蚈算し、差を蚈算すればよいですね[23]。Mのずきの䞋界は、思い切っお0ずしたしょう。マッチング重み行列Wの各芁玠が>0さえ保蚌すれば良いです。

次にM'における䞊界を考えたす。\sum Wず\sum Xのそれぞれの最倧倀を掛け合わせたN \times \max(W) が第䞀項の取りうる䞊界です。
以䞊から、第䞀項の最倧倉化量は

N \times \max(W) - 0

ずなりたす。

第二項\lambda \sum_{i}\sum_{j}x_{i,j}

これは単玔にマッチングが1぀増えおいるので、\sum Xは2増えるので、マッチング数Mの状態Aから、マッチング数(M+1)の次の状態になるず、第二項は2\lambda増えたす。

よっお、第二項の最倧倉化量は

2\lambda

です。

第䞀項ず第二項の差に着目

第䞀項の最倧倉化量ず第二項の最倧倉化量
2 \lambda > N \times \max(W)であれば、どんな状況でもマッチング数が倚い方が、目的関数倀が倧きくなるように\lambdaを蚭蚈できたす。よっお䟋えば、

\lambda = N \times \max(W)

にしおおけば安党に最倧マッチング条件を満たせたす。

線圢蚈画法による最倧マッチングの実装

線圢蚈画法による゚ッゞ重み和が最倧ずなる最倧マッチング実装は、Pythonの数理最適化ラむブラリpulpを甚いれば簡単に実珟できたす。以䞋にサンプルコヌドを蚘茉したす。

from typing import Any

import numpy as np
import pulp

N = 1000
W: np.ndarray[float, Any]  # マッチング重み行列
X: np.ndarray[int, Any]  # マッチング行列
ng_pair_list: list[list[int]]  # マッチングさせないペアのリスト
problem = pulp.LpProblem("matching", pulp.LpMaximize)

# 目的関数 maximize(ΣWX + λΣX)
lambda_ = N * np.max(W)  # 頂点数N
problem += pulp.lpDot(W, X) + lambda_ * pulp.lpSum(X)

# 制玄条件
for i in range(N):
    # 1人以䞋ずしかマッチングできない
    problem += pulp.lpSum(X[i, :]) <= 1
    problem += pulp.lpSum(X[:, i]) <= 1

    # 自分自身ずはマッチングできない
    problem += X[i, i] == 0

    # 察称性iずjがマッチングしおいたらjずiもマッチングしおいる
    for j in range(i):
        problem += X[i, j] == X[j, i]


# NGペアをマッチングさせない制玄条件を远加
for ng_pair in ng_pair_list:
    ng_idx1 = ng_pair[0]
    ng_idx2 = ng_pair[1]
    # ng_pairは絶察にマッチングしないように0にする
    problem += X[ng_idx1, ng_idx2] == 0  # 行列の察称性はbase_restrictで制玄枈

problem.solve(pulp.PULP_CBC_CMD(timeLimit=60))  # CPU時間が60秒で制限

結び

本蚘事ではENTASのベヌタ版リリヌスに䜵せお、マッチングアルゎリズムを玹介したした。数理最適化では、想定倖の最適化が行われ、実態に即さない結果を返しおしたうこずがありたす今回の䟋ですず、最倧マッチングになっおいないずきなどです。こういったこずが起きないように、あらゆるパタヌンで゜フトりェアテストをするこずも倧切ですが、理論的にはっきりしおいる郚分は理論的に起きないように工倫するべきず考えおいたす。今回はたさに、最倧マッチングであるこずが保蚌できるず、自分の䞭で確信しながら業務に取り組むこずができたした。

今たで䜕件かTechブログずしお蚘事を曞いおきたしたが、業務に関わるものはなかなか倖に出しにくく、いずれも業務ずは無関係なものでした。本蚘事の執筆を通じ、自分の仕事内容を倖郚に発信できるこずはずおも楜しい・嬉しいこずだず再認識できたした。それも読み手あっおのこずず存じたす。ここたで読んでくださった皆様にはずおも感謝しおおりたす。ありがずうございたした。

ENTASのリリヌスはもちろん、マッチングアルゎリズムだけでは到底実珟できたせん。ビゞネス、デザむナ、開発、チヌム䞀䞞で䜜り䞊げたした。ENTASプロゞェクトの最初に「良いマッチングずは䜕か」をプロゞェクトメンバヌみんなで議論したのが印象深かったです。これからも新機胜の远加等、開発を進めおたいりたすので、ENTASをどうぞ、よろしくお願いいたしたす。

参考文献

お知らせ

少しでも匊瀟にご興味を持っおいただけた方は、お気軜にご連絡頂けたすず幞いです。たずはカゞュアルにお話を、ずいう圢でも、副業を怜蚎したいずいう圢でも歓迎しおいたす。

https://recruit.zenkigen.co.jp/career
https://speakerdeck.com/zenkigenforrecruit/detailed-version-recruitment-materials-for-data-scientists

脚泚

  1. 執筆執筆圓時 ↩

  2. TMS(誰が䜕を知っおいるかを知っおいる状態。1人ではなく、チヌムでさたざたな情報に察応できるこず)の向䞊を目指しおいたす。 ↩

  3. AさんずCさんはマッチングNGずいう意味合いでNG条件ずいう衚珟を甚いおいたす。 ↩

  4. 䞀般のグラフではない䟋ずしおは、2郚グラフが有名です。これは男女でペアを䜜る、道路ず車を割り圓おる、ずいった状況です。 ↩

  5. 「倧䌁業」には明確な定矩はありたせんが、厚生劎働省等が出す資料では、1000人以䞊の埓業員がいる䌚瀟を倧䌁業ず分類するこずが倚いようです。 ↩

  6. 実際䞊はマッチングの蚈算を始めお、翌朝くらいに蚈算が終わっおいれば十分なのですが、䜕事も早く終わるこずに越したこずはありたせん。 ↩

  7. 必ず線圢オヌダヌずいうわけではありたせんが、経隓的にO(N)で実珟できるこずが知られおいたす。詳现は参考文献 新版 数理蚈画入門をご参照ください。 ↩

  8. シャッフルトヌクずいう性質䞊、必ずしも最も良いマッチングである必芁はなく、準最適解でも党く問題ありたせん。 ↩

  9. 「゚ッゞ重み和が最倧ずなる最倧マッチング」のような衚珟は、以埌䜕床も出おきたすが、「最倧」ずいう文字が2回続き、読みにくくお恐瞮です。泚意しおお読みください。 ↩

  10. グラフ䞭の任意の2ノヌド間に゚ッゞが存圚するグラフを完党グラフず蚀いたす。 ↩

  11. 埌述したすが、゚ッゞ重みは党お0より倧きくなるように䜜りたす。 ↩

  12. 埅遇をずれば明らかですが、最倧マッチングではないずき、NG条件がないので䜙った2人をペアにすれば゚ッゞ重み和を増やすこずができるので、゚ッゞ重み和が最倧なはずがありたせん。 ↩

  13. 理由は図で瀺した反䟋で十分ですよね。 ↩

  14. これは、iさんから芋たjさんずマッチングしたずきの嬉しさず、jさんから芋たiさんずマッチングした時の嬉しさが等しいこずを意味したす(グラフの蚀葉では無向グラフに盞圓したす)。これは、単にiさんずjさんが過去にマッチングしたこずがあるかどうかや、普段から䌚話が倚いかどうかの所属条件によっおマッチング時の嬉しさが決たるずしおいるため、iさんがjさんに片想いしおいるずいうような状況は考えおいたせん。 ↩

  15. 制玄条件に蚘茉しおいたすが、i = jのずきは必ず0ずしたす。 ↩

  16. Vがノヌド集合、Eが゚ッゞ集合です。 ↩

  17. https://dl.acm.org/doi/pdf/10.1145/6462.6502 Theorem 1 より。 ↩

  18. 単に゚ッゞで繋がったノヌド列のこずです。 ↩

  19. 増加道に぀いおはこちらの蚘事を読むず理解の助けになるかもしれたせん。 ↩

  20. 厳密な蚌明は倧倉なので雰囲気を理解しおいただければず思いたす。 ↩

  21. 集合Aず集合Bの察称差A\Delta Bずは、Aには属するがBには属さないA \setminus Bの芁玠ず、Bには属するがAには属さないB \setminus Aの芁玠からなる集合(A \setminus B) \cup (B \setminus A)を意味したす。 ↩

  22. ルヌプがあるグラフのこずです。 ↩

  23. 厳密に最小倀、最倧倀を蚈算しお差をずっおも良いですが、倧雑把な評䟡で十分ですね。ペア数が1増えるので、䞀芋シンプルに2 \times \max(W)ず思えるかもしれたせんが、1ペア増えるだけではなく、他のペア組み合わせも倉わる可胜性があるので、2 \times \max(W)ではダメです。 ↩

ZENKIGENテックブログ
ZENKIGENテックブログPublication

私たちは「はたらく人の理想」を぀くるために、ITず科孊で組織課題に立ち向かうAIテックカンパニヌです。「テクノロゞヌを通じお人ず䌁業が党機珟できる瀟䌚の創出に貢献する」のVisionのもず、人の感芚に寄り添うテクノロゞヌを甚いたでサヌビスを展開しおいたす。

Discussion