機械フローショップの一歩目！Johnson法について解説してみた！

皆様こんにちは！ばるとーくです！
今回はJohnson法について解説していこうと思います！

先に断りを入れておくと，今回紹介するJohnson法は，「スケジューリング問題」に関するものであって，「グラフ理論」に関するものではございませんのでご注意ください！

スケジューリング問題におけるJohnson法は，2機械と（一部）3機械フローショップで使える高速なアルゴリズムですので，ぜひ覚えていってもらえると嬉しいですっ！

フローショップとは

まずそもそも，「フローショップ」って何なのでしょうか？

その答えとして，ASPROVA株式会社のページを見るとこのような説明があります¹

設備の編成形式の1つで、ライン配置とも呼ばれ、すべての仕事（ジョブ）の加工経路が同じ場合、この流れに合わせて編成した工程もしくはショップをいう。
これは、ジョブの流れが決まっており、繰返し生産が行われ、かつ生産量も比較的多い場合に有効である。ジョブとしての流れの管理はしやすくなるが、製品の多様化への対応は難しくなる。
また、各機械設備での作業時間が異なることがある。この場合各作業のピッチタイムをとり、ラインバランシングを行い、流れ作業化を実現することが必要となる。

つまり，車の生産などで使われる「組み立てライン」のような工場形態の時に使われる設備編成というわけです．
そして，「ジョブとしての流れの管理はしやすくなるが、製品の多様化への対応は難しくなる。」とある通り，フローショップの最適化というのは非常に難しいものです．

というのも，基本的に，フローショップなどのスケジューリング問題の計算量はNP困難と言われ，最適解を求める計算は膨大になりがちです．
多項式時間で解けるようなスケジューリング問題は，かなり特殊な条件下だったり，単純な場合に限られることが分かります．²

Johnson法とは

Johnson法とは，先の章で述べたうちの「かなり特殊な条件下だったり，単純な場合」に相当する，と言ってもいいでしょう．
これは，「2機械，または条件付きの3機械から構成される作業について，全体の作業時間が最適になるようなスケジュールを作成することができる」という手法です．^{3 4}
ここでいう「機械」というのは「工程」であって，いわば「その製品を作るためにいくつの工程を経る必要があるのか」ということです．
それでは，実際の計算方法を見ていきましょうか．

2機械フローショップ

例えば，以下のような2機械の仕事を考えます．
製品は7つです．これらの生産には最短で何日かかるでしょうか？
Johnson法を使って解いてみましょう．
(解いてみたい人は一度ここでストップ！)

Johnson法による作業順序決定は，以下の流れで進みます．
ただし，ここでは上の例題に合わせ，機械 $A$ を先に，機械 $B$ を後に行う工程とします．

1. 現時点で選ばれていない製品のうち，機械 $A$，あるいは機械 $B$ のうちどちらかの作業時間が最も少ない製品を選ぶ．
2. (機械 $A$ の作業時間) $\le$ (機械 $B$ の作業時間)，つまり，先に行う工程の作業時間が，あとに行う工程の作業時間以下なら，その製品を最初に処理する．
3. 2.のようにならないなら，その製品は最後に処理する．
4. 同数が出たときは，以下のように対処する．
   1. 機械Aの場合は，機械Bの工程時間がより短いものを先に選ぶ．
   2. 機械Bの場合は，機械Aの工程時間がより長いものを先に選ぶ．
5. 選ばれていない製品がなくなるまで，この工程を繰り返す．

ここで，「処理」とは，機械へ投入することを意味しています．
つまり，「最初に処理する」とは，先に機械へ投入すること，「最後に処理する」とは，機械への投入を後回しにすることを表します．

それでは，これに則り，この問題を解いてみましょう．
なお，これ以降，機械 $A$, 機械 $B$ を単に $A, B$ と呼ぶことにします（そろそろ煩わしいだけ...ですっ）

まず，製品2の $A$ が作業時間1で最短です．これを最初に選びます．
$A < B$ より，最初に処理します．
分かりやすく配列 $Q$ を定義しておくと，現在は $Q = {2}$ となっています．

次に短いのは製品4の $A$ ですね．
$A < B$ より，最初に処理します．
$Q = {2, 4}$ となりました，先頭から連結するイメージです．

次に短いのは製品3の $B$，製品1の $A$ が3で並んでいます．
製品1は $A < B$ より，最初に処理し，製品3は $A > B$ より，最後に処理します．
$Q = {2, 4, 1, 3}$ となります．製品3のように $A > B$ の時は，末端から連結するイメージです．

次に短いのは製品6の $B$ です．
$A > B$より，最後に処理します．
$Q = {2, 4, 1, 6, 3}$ となります．末尾からつなぐので，結果的に製品3より先に処理されることになる点に注意です．

次に短いのは製品7の $A, B$ ですね．どちらも7です．
$A = B$ の場合も，最初に処理します．
$Q = {2, 4, 1, 7, 6, 3}$ となりました，いよいよ次でラストです．

最後に残ったのは製品5です．
$A < B$ より，最初に処理します．
$Q = {2, 4, 1, 7, 5, 6, 3}$ となりました．

こうして，結果的に，$2 \to 4 \to 1 \to 7 \to 5 \to 6 \to 3$ という順で処理するといいことが分かりました．
これをガントチャートに表してみましょう．すると，以下のようになります．

これより，43日ですべての作業を終えることができると求まりました．

3機械フローショップ

3機械フローショップでも，以下の条件付きでJohnson法を適用することができます．

条件：3つの機械をそれぞれ $A, B, C$，製品数を $n$ とする．
この時，$min(A_i) \le max(B_i)$ または $min(C_i) \le max(B_i)$ を満たす．
ただし，$1 < i < n$であり，$min(), max()$ はそれぞれ「最小値」「最大値」を示す．

では，こちらも以下のような例題を考えてみましょう．

以下に示される5つの製品を生産するには3工程必要である．
これらすべての生産には最短で何日必要でしょうか？
（こちらも「自力で解きたい！」って人はここでストップです！）

まず，Johnson法の適用条件を満たしているかの確認を行います．
ここで，$A$ と $B$ について，$min(A_i) = 5, max(B_i) = 5$ より，適用条件を満たしていることが分かります．
というわけで，今回もJohnson法を用いて解いていきましょう．

3機械のJohnson法もやることはほとんど変わりませんが，少しだけ手順が変わります．

1. $(A_i + B_i)$ を仮想機械 $X_i$, $(B_i + C_i)$ を仮想機械 $Y_i$ として考える． <-ここが新しいところ！
2. 現時点で選ばれていない製品のうち，機械 $X$，あるいは機械 $Y$ のうちどちらかの作業時間が最も少ない製品を選ぶ．
3. (機械 $X$ の作業時間) $\le$ (機械 $Y$ の作業時間)，つまり，先に行う工程の作業時間が，あとに行う工程の作業時間以下なら，その製品を最初に処理する．
4. 3.のようにならないなら，その製品は最後に処理する．
5. 同数が出たときは，以下のように対処する．
   1. 機械 $X$ の場合は，機械Yの工程時間がより短いものを先に選ぶ．
   2. 機械 $Y$ の場合は，機械Xの工程時間がより長いものを先に選ぶ．
6. 選ばれていない製品がなくなるまで，工程2. ~ 6.を繰り返す．

ではまず，仮想機械 $X, Y$ について考えていきます．
すると，以下の表のようになると思います．

それでは，ここからは2機械の時と同様に処理していきます．

まず，製品4のYが作業時間5と最短です．
$X > Y$ より，最後に処理します．
こちらもわかりやすく待期列 $R$ を定義しておくと，$R = {4}$ です．
1つしかないのでわかりにくいですが，最後尾なので間違えないようにしましょう．

次に短いのは製品1の $Y$ と製品5の $X, Y$ です．どちらも作業時間6と並んでいます．
製品1は $X > Y$ より最後に処理し，製品5は $X = Y$ より最初に処理します．
$R = {5, 1, 4}$ となりました．何度も言いますが間違えないように！

次に短いのは製品2の $Y$ です．
$X > Y$ より，最後に処理します．
$R = {5, 1, 2, 4}$ となりました．早くも次がラストです．

最後に残ったのは製品3です．
$X < Y$ より，最初に処理します．
$R = {5, 1, 3, 2, 4}$ となりました．

結果として，$5 \to 1 \to 3 \to 2 \to 4$ という順で処理を行うのが最適とわかりました．
ガントチャートを書くとこのようになります．

よって，39日ですべての作業を終えることができると求まりました．

証明

それでは，これよりJohnson法がフローショップ問題の最適解を求めることができることの議論・証明をしていきます．
証明は大きく分けて3つです

1. 2機械フローショップ問題の場合
2. 3機械フローショップ問題の場合(条件を満たさないとき)
3. 3機械フローショップ問題の場合(条件を満たすとき)

2機械フローショップ問題の場合

設定

2つの機械 $M_1, M_2$ と $n$ 個のジョブ ${1, 2, \ldots, n}$ からなるフローショップを考える．各ジョブ $i$ は $M_1$ で処理時間 $A_i$，続いて $M_2$ で処理時間 $B_i$ を要する ($A_i, B_i > 0$)．

順序 $S = (S_1, S_2, \ldots, S_n)$ に従ってジョブを処理するとき，総所要時間 (メイクスパン) $F(S)$ を最小化する順序 $S^*$ を求めたい．

補題1: 置換スケジュールの最適性

主張: 最適解の中には，$M_1$ と $M_2$ で同じジョブ順を用いる置換スケジュールが存在する．

証明: $M_1$ 上での順序を固定したとき，$M_2$ 上での順序を $M_1$ と同じにしても総所要時間は悪化しない．実際，$M_2$ 上で $M_1$ と異なる順序を用いているとすると，隣接する不整合ペアを交換していくことで $M_1$ と同じ順序に変形できる．各交換で $M_2$ の完了時刻は増加しないため，置換スケジュールに帰着してよい．

以下では置換スケジュールのみを考える．

記法と定式化

順序 $S$ の下で，$X_i$ を「$i$ 番目のジョブが $M_2$ に到着する直前の $M_2$ の遊休時間」と定義する．$M_1$ には遊休時間を入れず，ジョブを連続して処理するとしてよい (これは総所要時間を悪化させない)．

このとき $M_2$ の総所要時間は次のように書ける: $F(S) = \sum_{i=1}^{n} X_i + \sum_{i=1}^{n} B_i$．

第2項は順序に依存しないため，$F(S)$ の最小化は $\sum X_i$ の最小化と等価である．

$X_i$ の漸化的な定義は $X_1 = A_1$ および $i \geq 2$ に対して $X_i = \max\left(A_1 + \cdots + A_i - B_1 - \cdots - B_{i-1} - \sum_{k=1}^{i-1} X_k,\ 0\right)$ で与えられる．

これを整理すると，次の閉じた形が得られる: $\sum_{i=1}^{n} X_i = \max_{1 \leq u \leq n} K_u$，ただし $K_u = \sum_{i=1}^{u} A_i - \sum_{i=1}^{u-1} B_i$．

したがって目的関数は $F(S) = \max_{1 \leq u \leq n} K_u + \sum_{i=1}^{n} B_i$ となり，$\max_u K_u$ を最小化する順序を求めればよい．
⁵

隣接交換の効果

順序 $S$ における $j$ 番目と $j+1$ 番目のジョブを交換した順序を $S'$ とする．$S'$ における $K$ 値を $K'_u$ と書く．

$K_u$ の定義から，$u \neq j, j+1$ については $K'u = K_u$ である ($u$ 番目までの総和が変わらないため)．したがって $F(S) \leq F(S') \iff \max(K_j, K{j+1}) \leq \max(K'j, K'{j+1})$．

$j$ 番目までのジョブに関する共通項 $\sum_{i=1}^{j-1} A_i - \sum_{i=1}^{j-1} B_i$ を $\alpha$ と置くと，交換前の $j, j+1$ 番目のジョブを $p, q$，交換後を $q, p$ として:

• $K_j = \alpha + A_p$，$K_{j+1} = \alpha + A_p + A_q - B_p$
• $K'j = \alpha + A_q$，$K'{j+1} = \alpha + A_q + A_p - B_q$

$\max(K_j, K_{j+1}) < \max(K'j, K'{j+1})$ となる条件を求める．両辺から $\alpha + A_p + A_q$ を引くと $\max(-A_q, -B_p) < \max(-A_p, -B_q)$，すなわち $-\min(A_q, B_p) < -\min(A_p, B_q)$．

したがって $\min(A_p, B_q) < \min(A_q, B_p)$ ならば $p$ を $q$ より先に置くほうがよい．これが Johnson法 である．

補題2: Johnson法の推移性

主張: 関係 $p \prec q \iff \min(A_p, B_q) \leq \min(A_q, B_p)$ は推移的である．

証明: $\min(A_1, B_2) \leq \min(A_2, B_1)$ かつ $\min(A_2, B_3) \leq \min(A_3, B_2)$ を仮定し，$\min(A_1, B_3) \leq \min(A_3, B_1)$ を示す．

Case 1: $A_1 \leq B_2$ かつ $A_2 \leq B_3$ のとき

このとき $A_1 \leq \min(A_2, B_1)$ より $A_1 \leq A_2$．同様に $A_2 \leq A_3$．よって $A_1 \leq A_3$．また $A_1 \leq B_1$ であるから $A_1 \leq \min(A_3, B_1)$．

Case 2: $B_2 \leq A_1$ かつ $B_3 \leq A_2$ のとき

$B_3 \leq A_2$ から $B_3 \leq \min(A_3, B_2)$ より $B_3 \leq B_2$．$B_2 \leq A_1$ とあわせて対称的に議論すると $B_3 \leq A_3$ かつ $B_3 \leq B_1$ が導け，$B_3 \leq \min(A_3, B_1)$．

Case 3: $A_1 \leq B_2$ かつ $B_3 \leq A_2$ のとき

$A_1 \leq B_1$ (前提より) かつ $B_3 \leq A_3$ (第2前提より) が得られ，$\min(A_1, B_3) \leq \min(A_3, B_1)$．

Case 4: $B_2 \leq A_1$ かつ $A_2 \leq B_3$ のとき

このケースでは $A_2 = B_2$ となり，ジョブ 2 はジョブ 1, 3 のいずれとも「同順位 (indifferent)」となる．定順序に矛盾は生じない

定理: Johnson法による順序の最適性

定理: Johnson法にしたがって並べた順序 $S^*$ は，$F(S)$ を最小化する．

証明: 任意の順序 $S_0$ から出発し，Johnson法に反する隣接ペア (すなわち $\min(A_p, B_q) < \min(A_q, B_p)$ でありながら $q$ が $p$ より先に置かれているペア) を見つけるたびに交換する．⁶

隣接交換の効果より，この交換は $F$ を悪化させない．推移性 (補題2) により，この操作は有限回で停止し，最終的に得られる順序は Johnson法にしたがう順序 $S^$ である．したがって $F(S^) \leq F(S_0)$ が任意の $S_0$ について成り立つ．

(おまけ)実装のための Working Rule

$(A_i, B_i)$ の $2n$ 個の値の中から最小値を選び:

• 最小値が $A_i$ ならジョブ $i$ を「前から順に」配置
• 最小値が $B_i$ ならジョブ $i$ を「後ろから順に」配置

そのジョブに関する両方の値を除外し，残った $2n-2$ 個の値に対して同じ操作を繰り返す．これにより $O(n \log n)$ で最適順序が構成できる．

3機械フローショップ問題の場合

3機械フローショップ問題では，Johnson法は無条件では最適解を与えない．最適性が保証されるのは以下の条件を満たすときである．

条件: 3つの機械をそれぞれ $A, B, C$，製品数を $n$ とする．このとき

$\min_{1 \le i \le n} A_i \ge \max_{1 \le i \le n} B_i \quad \text{または} \quad \min_{1 \le i \le n} C_i \ge \max_{1 \le i \le n} B_i$

を満たす．

以下では，(i) この条件を満たさないときにJohnson法が最適解を与えない例が存在すること，(ii) 条件を満たすときにJohnson法が必ず最適解を与えることを示す．
なお本節では前者を示すが，これは「条件を満たさないなら必ず非最適」を意味するのではなく，あくまで「最適性が保証されない」ことを意味する．

条件を満たさないときに最適性が保証されないこと

反例として，以下の3製品を考える．

条件の確認: $\min A = 1$，$\max B = 10$ より $\min A \ge \max B$ は不成立．$\min C = 1$，$\max B = 10$ より $\min C \ge \max B$ も不成立．
したがって条件を満たさない．

仮想機械 $P_1 = A + B$，$P_2 = B + C$ を考えると:

Johnson法を適用すると，$P_1 \le P_2$ の集合 $= {1, 2}$ を $P_1$ 昇順で $2 \to 1$，$P_1 > P_2$ の集合 $= {3}$ を後ろに配置し，順序 $2 \to 1 \to 3$ を得る．このときの3機械メイクスパンは $27$ となる．

一方，全探索により真の最適順序を確認すると $2 \to 3 \to 1$ でメイクスパン $25$ が達成される．よってJohnson法は最適解を与えていない．したがって，条件を満たさない場合にJohnson法の最適性は一般には保証されないことが示された．

条件を満たすときにJohnson法が最適解を与えること

以降，条件 $\min_i A_i \ge \max_i B_i$ を満たす場合について証明する ($\min_i C_i \ge \max_i B_i$ の場合は対称的な議論で示せる)．

方針: 条件下で，任意の順序 $S$ について 3機械メイクスパン $F^{(3)}(S)$ と仮想2機械メイクスパン $F^{(2v)}(S)$ が定数差の関係にあることを示し，最適順序集合が一致することを結論する．

記法と定式化

順序 $S$ の下で，$X_i$ を「$i$ 番目のジョブが $M_2$ に到着する直前の $M_2$ の遊休時間」，$Y_i$ を「$i$ 番目のジョブが $M_3$ に到着する直前の $M_3$ の遊休時間」と定義する．

2機械のときと同様に，$M_3$ の総所要時間は次のように書ける:

$F^{(3)}(S) = \sum_{i=1}^{n} Y_i + \sum_{i=1}^{n} C_i$

第2項は順序に依存しないので，$F^{(3)}(S)$ の最小化は $\sum Y_i$ の最小化と等価である．

2機械の議論を機械2と機械3の間に適用すると，一般に次が成り立つ:

$\sum_{i=1}^{n} Y_i = \max_{1 \le u \le v \le n} (H_v + K_u)$

ただし $H_v = \sum_{i=1}^{v} B_i - \sum_{i=1}^{v-1} C_i$，$K_u = \sum_{i=1}^{u} A_i - \sum_{i=1}^{u-1} B_i$ である．

条件による簡約

条件 $\min_i A_i \ge \max_i B_i$ の下で，$\sum Y_i$ の表現を簡約する．まず次の補題を示す．

補題3: 条件 $\min_i A_i \ge \max_i B_i$ の下で，$K_u = \sum_{i=1}^{u} A_i - \sum_{i=1}^{u-1} B_i$ は $u$ について単調非減少である．

証明: $u \ge 2$ に対して

$K_u - K_{u-1} = \left(\sum_{i=1}^{u} A_i - \sum_{i=1}^{u-1} B_i\right) - \left(\sum_{i=1}^{u-1} A_i - \sum_{i=1}^{u-2} B_i\right) = A_u - B_{u-1}$

ここで条件より $A_u \ge \min_i A_i \ge \max_i B_i \ge B_{u-1}$．したがって $K_u - K_{u-1} \ge 0$．$\blacksquare$

系: 任意の $v$ について $\max_{1 \le u \le v} K_u = K_v$．

証明: 補題3より $K_1 \le K_2 \le \cdots \le K_v$ であるから，最大値は $u = v$ で達成される．$\blacksquare$

系を用いて $\sum Y_i$ の表現を書き換える:

$\sum_{i=1}^{n} Y_i = \max_{1 \le u \le v \le n} (H_v + K_u) = \max_{1 \le v \le n} \left(H_v + \max_{1 \le u \le v} K_u\right) = \max_{1 \le v \le n} (H_v + K_v)$

ここで $L_v := H_v + K_v$ と置くと

$L_v = \sum_{i=1}^{v} B_i - \sum_{i=1}^{v-1} C_i + \sum_{i=1}^{v} A_i - \sum_{i=1}^{v-1} B_i = \sum_{i=1}^{v}(A_i + B_i) - \sum_{i=1}^{v-1}(B_i + C_i)$

これは $P_1(i) = A_i + B_i$，$P_2(i) = B_i + C_i$ を処理時間とする仮想2機械フローショップの $K$ 値そのもの である．

帰着の完成 (最適順序集合の一致)

以上の議論をまとめると，条件下では任意の順序 $S$ について

$F^{(3)}(S) = \max_{1 \le v \le n} L_v + \sum_{i=1}^{n} C_i$

が成り立つ．一方，$P_1, P_2$ を処理時間とする仮想2機械フローショップのメイクスパンは，2機械の場合の議論より

$F^{(2v)}(S) = \max_{1 \le v \le n} L_v + \sum_{i=1}^{n} P_2(i) = \max_{1 \le v \le n} L_v + \sum_{i=1}^{n} (B_i + C_i)$

と書ける．両者の差をとると

$F^{(2v)}(S) - F^{(3)}(S) = \sum_{i=1}^{n} B_i$

この差は $S$ に依存しない定数である．したがって

$\arg\min_S F^{(3)}(S) = \arg\min_S F^{(2v)}(S)$

すなわち，元3機械問題の最適順序集合と仮想2機械問題の最適順序集合は一致する．

2機械フローショップ問題ではJohnson法が最適解を与えることが既に示されているので，仮想2機械問題にJohnson法を適用して得た順序 $S^*$ は，元の3機械問題においてもメイクスパンを最小化する．
具体的にはJohnson則は次の形で書ける:

$\min(A_p + B_p,\ B_q + C_q) < \min(A_q + B_q,\ B_p + C_p) \implies p \text{ を } q \text{ より先に置く}$

補足: 条件が本質的である理由

条件を用いなければ，$\sum Y_i$ の表現は $\max_{u \le v}(H_v + K_u)$ の形のままとどまり，補題3の単調性が成り立たないため $\max_{u \le v} K_u = K_v$ の簡約ができない．
この場合，隣接交換 $j \leftrightarrow j+1$ で影響を受ける項が添字 $j, j+1$ に閉じず，それ以前の順序に依存するため，局所的な決定則としてのJohnson則が導けない (P-402 §2末尾でJohnson自身が指摘している通り⁵)．条件 $\min A \ge \max B$ は，補題3を介して $\sum Y_i$ を $\max_v L_v$ という2機械問題の形に閉じ込める役割を果たしている．

以上より，2機械フローショップ問題ではJohnson法が必ず最適解を与えること，3機械フローショップでは無条件にはJohnson法の最適性が保証されないこと，並びに，$\min A \ge \max B$ (または $\min C \ge \max B$) の条件下では2機械問題への帰着を通じてJohnson法が最適解を与えることが示された．

余談～なぜJohnson法やフローショップ問題は競プロ典型になりえないのか

ここからは私の余談です．
実は私一度，yukicoderでフローショップ問題を題材にした問題を作ったことがあるんです...
※何ならその補足のためにこの記事を書いてるまである

で，私ふと思いました．「なんでこの類の問題ってあまり見ないんだろう？」と．
もしかしたら私の競プロ人生がまだ浅すぎて出会ってないだけの可能性も十分考えられますが，あんまり話題に聞かないなと思い...

というわけで今から，私がこの記事を書くためにいろいろ調べたり，大学の授業でかじったりした知識をもとにして，自身を論駁していこうと思います...というのがこの章の趣旨です///

まずそもそも，「拡張性が小さい」と思いましたね．
これを題材に使おうとすると，どうしてもストーリー性がワンパターンになるなーと感じます．
だって，「工場のライン生産」以外にこの題材が当てはまりそうなシチュエーションが思いつかないんですもん．
※思いついた方，ぜひこの下のコメ欄，Ｘなどなどでコメントください．または問題を作って送り付けてきてください．

次に，「Johnson法の条件が厳しすぎる」点が挙げられます．
2機械はともかく，3機械になると条件が厳しすぎて制約で手法がバレます．
これはあまり快しとしない人もいるのではないかな～と考えています．
例えば「$N$ が小さいからビット全探索でしょ」みたいな経験あると思います．こういう体験が追加されるのは...どうなんでしょうか？とも思ってしまいますね．
ただ，（論駁に論駁を重ねてしまいますが）2機械ならいい練習問題になるんではないでしょうか．こちらは制限がほぼないですからねっ
私の見立てでは(Novistep基準)4Qくらいの難易度になるんじゃないかなと...

また，「スケジューリング問題が基本的にNP困難」である点が致命的な気がします．
最初の章でも述べた通り，スケジューリング問題は基本的にNP困難です．
とすると，計算量での厳密な証明ができないので，上界をしっかり定めないと問題として破綻しうる，という面倒くささ付きです．
※主も実際その問題に立ちはだかりました．tester様には感謝してもしきれません...

これだけの論駁で，十分競プロ向きではないことが証明できてしまいましたね...
とはいえ，最適化問題を考える上では必ず出てくる問題であるため，認知自体はしておくことをお勧めします．

さいごに

ここまで，Johnson法について解説してきました！
ここまでぎゅっとした記事を書くのもなんだか久しぶりで，ちょっと楽しかったです．
現在は（コンテストの都合により）壊れた部屋のみでの公開ですが，コンテスト後にqiitaにも投稿いたしますので，併せて見ていってくださるととてもうれしいです！

というわけで，今回はここまでにしたいと思います！
この記事が皆様のためになることを願っております！
ご意見・ご感想あれば，コメ欄やXなどのSNSまでよろしくお願いいたします！
※上記「リンク集」からばるとーくのアカウントがあるサイト一覧が載っておりますので，ぜひ見てみてください！
また，お時間ございましたら，他の記事も見ていってください！

それではまた！