TOYOTA AHC 至高のアルゴリズム解説会#2 AHC026 解説

トヨタ自動車プログラミングコンテスト2023#6 （AtCoder Heuristic Contest 026） “Stack of Boxes” 延長戦解法 割当問題の k -best 列挙による ゲーム木探索の候補手生成 2024/11/29 TOYOTA AHC 至高のアルゴリズム解説会#2 hitonanode / 佐藤 遼太郎

2 hitonanode / 佐藤 遼太郎 • 所属：エムシーデジタル株式会社（データサイエンティスト） • 最適化（汎用ソルバー・ヒューリスティクス） • 開発 • Heuristic：AtCoder Rating 3019 • 優勝： AHC026・RECRUIT 日本橋ハーフマラソン 2021 hitonanode hitonanode • Algorithm：AtCoder Rating 3041 (Max: 3222) • 優勝： ARC 4 回・ABC 15 回 etc. • Meta (Facebook) Hacker Cup Finalist (top 25）: 2020, 2022-24 • PG BATTLE 企業の部 2 連覇 (2021-22)

• https://www.mcdigital.jp/
• https://www.mcdigital.jp/blog/20240709techblog/
• https://github.com/hitonanode
• https://atcoder.jp/users/hitonanode

3 目次 • 扱う問題の紹介 • コンテスト本番解法の課題 • 課題解決の方針 • 実験・性能評価 • まとめ

4 扱う問題の紹介

5 AHC026 “Stack of Boxes” 問題（一部表現改変） • 倉庫に積まれた 200 個の箱を番号順に出庫せよ • ① 移動：いずれかの列の上部いくつかの箱を、別の列に載せ替え • 移動コストとして、個数 に加えて +1 の 手数料 が発生 • ② 出庫：現存する番号最小の箱がいずれかの列の一番上にあれば、消去 • ランダムな初期状態に対して平均移動コスト約 512 以下の手順が作れれば当時優勝 👑 初期状態 可能な操作① 移動 2 個移動： コスト 3 20 段 6 1 10 列 2 5 2 5 4 3 ※動かす箱の積み順は不変 可能な操作② 出庫 6 2 1 5 4 3 ※出庫は絶対に番号順

シンプルな貪欲アルゴリズムの動作例 • コスト 903 (seed=0) • 出庫したい箱を取り出すため、箱の退避が繰り返し生じて無駄に…… コスト 200 発生時点 コスト 400 発生時点 6

7 コンテスト優勝解法の動作例 • コスト 497 (seed=0) • 出庫のことは一旦忘れ、番号順に整理！ コスト 200 発生時点 コスト 400 発生時点

8 強力な「各列ソート」方針 • 番号順に整理した列は以降放置できるので嬉しい • ➡「積み上げフェーズ」は、放置可能な箱を増やすため高く積み上げたい • ➡「掃き出しフェーズ」は、後で高く積み上げやすい形にしたい 掃き出しフェーズ 掃 き 出 し 列 積み上げフェーズ 繰り返し 特定の列の箱全てを他の列へ 散らかった箱を空いた列に 番号順に片付ける 順調に進展した形

一列の掃き出し・積み上げの例 • 累計コスト 0 9

一列の掃き出し・積み上げの例 • 累計コスト 2 (+2) 10

一列の掃き出し・積み上げの例 • 累計コスト 4 (+2) 11

一列の掃き出し・積み上げの例 • 累計コスト 8 (+4) 12

一列の掃き出し・積み上げの例 • 累計コスト 11 (+3) 13

一列の掃き出し・積み上げの例 • 累計コスト 13 (+2) 14

一列の掃き出し・積み上げの例 • 累計コスト 18 (+5) 15

一列の掃き出し・積み上げの例 • 累計コスト 18 (1 出庫) 16

一列の掃き出し・積み上げの例 • 累計コスト 21 (+3) 17

一列の掃き出し・積み上げの例 • 累計コスト 23 (+2) 18

一列の掃き出し・積み上げの例 • 累計コスト 25 (+2) 19

一列の掃き出し・積み上げの例 • 累計コスト 27 (+2) 20

一列の掃き出し・積み上げの例 • 累計コスト 29 (+2) 21

一列の掃き出し・積み上げの例 • 累計コスト 31 (+2) 22

一列の掃き出し・積み上げの例 • 累計コスト 33 (+2) • 掃き出し完了、積み上げに移行 23

一列の掃き出し・積み上げの例 • 累計コスト 35 (+2) 24

一列の掃き出し・積み上げの例 • 累計コスト 38 (+3) 25

一列の掃き出し・積み上げの例 • 累計コスト 40 (+2) 26

一列の掃き出し・積み上げの例 • 累計コスト 42 (+2) 27

一列の掃き出し・積み上げの例 • 累計コスト 45 (+3) 28

一列の掃き出し・積み上げの例 • 累計コスト 48 (+3) 29

一列の掃き出し・積み上げの例 • 累計コスト 50 (+2) 30

一列の掃き出し・積み上げの例 • 累計コスト 53 (+3) 31

一列の掃き出し・積み上げの例 • 累計コスト 56 (+3) 32

一列の掃き出し・積み上げの例 • 累計コスト 60 (+4) 33

一列の掃き出し・積み上げの例 • 累計コスト 62 (+2) 34

一列の掃き出し・積み上げの例 • 累計コスト 65 (+3) 35

一列の掃き出し・積み上げの例 • 累計コスト 67 (+2) 36

一列の掃き出し・積み上げの例 • 累計コスト 69 (+2) 37

一列の掃き出し・積み上げの例 • 累計コスト 72 (+3) 38

一列の掃き出し・積み上げの例 • 累計コスト 74 (+2) 39

一列の掃き出し・積み上げの例 • 累計コスト 76 (+2) 40

一列の掃き出し・積み上げの例 • 累計コスト 79 (+3) 41

一列の掃き出し・積み上げの例 • 累計コスト 82 (+3) 42

一列の掃き出し・積み上げの例 • 累計コスト 84 (+2) 43

一列の掃き出し・積み上げの例 • 累計コスト 86 (+2) 44

一列の掃き出し・積み上げの例 • 累計コスト 88 (+2) • 一列の処理が完了 45

46 コンテスト本番解法の課題

47 コンテスト本番における優勝解法 • 以下は競技時間 4 時間のコンテストで当時優勝した際の方針だが、改善の余地が多い 掃き出す列の順序を 仮決め 各列の掃き出し・積み上げを ルールベースで一手ずつ決定 最終的なコストを 算出 Cost = 501 区間反転などの変形を繰り返し試行し、 掃き出す列の順序のみ探索

48 課題① 掃き出しの精緻化の重要性 • 「良い」掃き出し方を見つけたいが、掃き出しの自由度が高い ① 隣接する箱の数字の組合せが重要 ② 掃き出し列以外の事前移動も有効 掃き 出し列 6 1 ？ 5 掃き 出し列 2 4 3 5 を掃き出した後 6 と 5 を積み上げたい 5 6 1 2 4 3 5 を 6 の上に置くと 後々まとめて動かせるので 手数料が減らせる 2 5 3 6 4 5 を 6 の上に退避させた後 2 を 3 の上に置くことで 2〜6 全て積み上げられる

49 課題② 探索の必要性 • どの掃き出し方が将来的に良い解をもたらすか先読み困難（と私は今のところ認識） • 有望な掃き出し方の列挙による探索が重要 掃き出し方 A 掃き出し/ 積み直し 盤面 a コスト70 … 最終コスト 464 … 最終コスト 491 初期盤面 掃き出し方 B 掃き出し/ 積み直し 盤面 b コスト69 まだ良し悪し不明 最終的には大差

50 課題の解決の結果 • 本番優勝時から 1 割弱コストを減らし再度 1 位に • 先述の課題の解決策を以下紹介していきます 延長戦順位表（2024/11 時点） 平均コスト 462.3 463.3 475.4 延長戦提出 492.3 493.1 495.0 497.0 本番優勝スコア → 512.1 ➡ 箱 1 個あたりコスト約 2.3

51 解決の方針

52 作りたいアルゴリズムの構成 • 良い掃き出し方を探索したい • 良い掃き出し方候補だけをどう多数生成するか？ • ➡ 扱いやすい評価関数の導入 & 組合せ最適化問題の解列挙アルゴリズム で解決！ 掃き出し/ 積み直し … 初期盤面 掃き出す列 で分岐 掃き出し方 候補の生成 掃き出し方 候補の生成 掃き出し/ 積み直し … 盤面 a … 掃き出し/ 積み直し 盤面 b 盤面 c … … 掃き出す列 で分岐 … …

53 箱の隣接の評価関数 • 「箱 の直下に箱 があることで今後コストがいくら安くなるか？」 という気持ちを込めて箱の隣接の評価関数 を設計 • 「それぞれの箱をどの箱の上に置く？」という組合せ最適化問題になりそう！ 評価関数の設計例： で値が近い状況を好意的に評価 掃き出し方の評価を「割当問題」に帰着 下の箱 掃き 出し 列 6 1 将来まとめて移動できそうなので、 コスト 1 節約見込み → +1.0 程度の評価 2 5 4 3 動かす箱 2 2 5 5 4 6

54 割当問題とは • 人の社員・ 個の仕事 • 社員 に仕事 を任せると 時間かかることが分かっている • 各社員に仕事を割り振り合計時間を最小化せよ（＝ 二部グラフの重み最小マッチング） 所要時間表 社員 1 社員 2 仕事1 仕事2 仕事3 仕事 1 仕事 2 … 1 2 3 社員1 3 4 6 社員1 3 4 6 社員2 12 9 10 社員2 12 9 10 社員3 7 6 9 社員3 6 9 7 3 + 10 + 6 = 19 が総和最小の割当 社員 3 仕事 3

割当問題の強力さ①：最適解が高速に計算可能 55 • 割当問題は実用上きわめて高速に解ける • Hungarian 法やこれを改良した Jonker‒Volgenant algorithm が存在 • 理論上は 、実用上もかなり高速 • SciPy 等にも実装済 • 自前実装も十分可能 • 最小費用流ソルバー等の流用でも（少し遅いが）解ける （参考）割当問題の最小費用流問題への帰着 … … … … … … ※各辺のラベルは (容量, コスト)

割当問題の強力さ②：「良い」解が効率的に列挙可能 • 実は割当問題において「最適解」「2 番目に良い解」…「 番目に良い解」の列挙 （k -best 列挙）が で可能！ [Murty, 1968] [Miller+, 1997] ü 最も良い解から順番に、好きなだけの数の解が確実に得られる • しかも の値は列挙しながら（後出しで）決めてよい • 「目的関数が一定の値を切ったら打ち切る」「納得の行く解が得られるまでひたす ら出力させる」などの使い方も可能 ü パラメータ調整等が一切不要、高い汎用性 • コンテスト用に C++ で実装しました： hitonanode/cplib-cpp • 👍 入力が正方行列でなくても動く（はず） • ⚠ テストはしましたがバグが残っている可能性があります • ⚠ 実行時間を詰めておらず、適切な改善でもっと早くできると思います 56

• https://github.com/hitonanode/cplib-cpp/blob/master/combinatorial_opt/linear_sum_assignment.hpp

57 割当問題を利用した掃き出し方列挙の枠組み • 各箱をどの箱の上に置くかを決めたい ➡ 「動かす箱」と「下の箱」の割当問題を解く 一列の掃き出しを 割当問題に変換 現在の盤面 多数の良い解を列挙・ 実行可能解を抽出 2 下の箱 掃き 出し 列 6 1 2 5 動かす箱 2 4 3 5 2 2 5 5 4 6 掃き出し実行 52 2 5 Best 2 4 6 52 45 5 64 3rd Best 6 2nd Best … 5 6 1 掃き 出し 列 2 4 3

58 掃き出し最適化への割当問題の活用 • 以下のルールを満たす掃き出しのみを考える • 動かせるのは、掃き出し列の全ての箱と、その他の列の一番上の箱のみ • 各箱の移動は最大 1 回で、掃き出し列への移動は禁止 • コストは評価関数をベースに決定 • 移動コスト含めて最適化するため、既に隣接 しているペアのコストは 1 減らす 等の補正 • 絶対に隣接不能なペアのコストは に設定 • 実行不可能な解が出たら捨てる • （「2 の上に 6」かつ「6 の上に 2」等） 掃き 出し列 2 6 7 5 動かす箱 下の箱 2 2 6 6 7 7 5 5 3 3 3 8 4 1 4 8 4 1

59 多様な掃き出し方の生成 • 実際に複数の掃き出し方が作れている • 掃き出し方の微妙な違いがその後の積み直しに大きく影響 ➡ 多様な探索に有益 seed=0 のケースで最初に 4 列目を掃き出す場合の実行結果例 1 番目の解 2 番目の解 10 番目の解 20 番目の解 掃き出し後 コスト77 積み直し後 コスト77 コスト85 コスト78

60 実験・性能評価

61 探索および k -best 列挙の効果の確認 結果：ランダムケース 1000 個に対してビームサーチで得た解のコスト平均値 割当問題の k -best 列挙 多様化手法 列挙数 / 試行数 1 5 10 重畳乱数の分散 ビーム幅 20 - 50 （比較手法）乱数加算 100 100 1.0 5.0 10.0 1 500.9 497.1 494.5 492.4 489.3 487.1 496.0 504.5 506.1 10 477.1 475.6 474.4 472.9 470.8 469.7 476.1 481.3 482.0 100 471.3 466.0 464.0 462.0 460.3 458.9 468.5 474.2 475.2 ※「列挙数 = 1」：掃き出す列の順序のみ探索 ※「乱数加算」：割当問題の入力各成分に独立な正規乱数を加算し多様な解生成を狙う方針 ➡ ビームサーチ等の探索は非常に有効 ➡ 単純な乱数加算と比較して k -best 列挙がより多様化・性能改善に貢献

まとめ • ゲーム木探索などの状況で、盤面やその部分問題を組合せ最適化問題として表せれば、 k -best 列挙によって有望な次着手の候補を効率的に得られるかもしれない • 実は k -best 列挙自体は（多少の計算量の悪化を許容すれば）割当問題に限らず一 般の組合せ最適化問題で可能 [Lawler, 1972] • AHC026 の「各列ソート方針」解法において、割当問題の k -best 列挙を活用して 良質的な掃き出し方を多数生成する処理を導入 • 掃き出し方の k -best 列挙が最終的な解の改善に有効であることを実験的に確認 AHC026 のさらなる改善や今回のアイデアの他の問題への適用など、 皆様も挑戦してみてください！ 62

謝辞 以下の方々に感謝します。 • 前回イベントで同一問題を解説いただくとともに分かりやすい発表資料を 公開してくださった bowwowforeach さん • 今回の発表内容にコメント・アドバイスをくださったエムシーデジタルの同僚の方々 63

参考文献・リンク集 • 割当問題 • Jonker, Volgenant, “A shortest augmenting path algorithm for dense and sparse linear assignment problems,” Computing, 38(4), 325-340, 1987. • Jonker‒Volgenant algorithm の論文で、アルゴリズムがそのまま実装できる形で記載されています • Lecture 8: Assignment Algorithms • Jonker‒Volgenant algorithm や k -best 列挙、その高速化まで説明されている資料 • 最適輸送の解き方 - SlideShare • 割当問題の Hungarian 法にも詳しく触れられています • k -best 列挙 • • • • • Murty, “An algorithm for ranking all the assignments in order of increasing cost,” Operations research, 16(3), 682687, 1968. • 割当問題で効率的な k -best 列挙が可能であることを初めて主張 Miller, Stone, Cox, “Optimizing Murty's ranked assignment method,” IEEE Transactions on Aerospace and Electronic Systems, 33(3), 851-862, 1997. • 割当問題の k -best 列挙の高速化 Lawler, “A procedure for computing the k best solutions to discrete optimization problems and its application to the shortest path problem,” Management science, 18(7), 401-405, 1972. • 一般の組合せ最適化問題で k -best 列挙を行う枠組みの提案 「Lawler の K-Best 列挙アルゴリズム」 - Qiita • Lawler の枠組みの日本語解説記事 AHC026 • トヨタ自動車プログラミングコンテスト2023#6（AtCoder Heuristic Contest 026）至高のアルゴリズム解説 • 前回解説会の bowwowforeach さん発表資料で、今回時間の都合で省略した部分が丁寧に説明されています 64

• https://cyberlab.engr.uconn.edu/wp-content/uploads/sites/2576/2018/09/Lecture_8.pdf
• https://www.slideshare.net/slideshow/ss-249394573/249394573
• https://qiita.com/tsukasa__diary/items/8bc2947d1f65d1451bb3
• https://speakerdeck.com/bowwowforeach/toyotazi-dong-che-puroguramingukontesuto2023-number-6-atcoder-heuristic-contest-026-zhi-gao-noarugorizumujie-shuo

65 補足 • 性能改善のためのその他の工夫 • 評価関数の詳細 • 割当問題と解列挙の詳細

補足：性能改善のためのその他の工夫 • 掃き出し最適化の工夫 • 解列挙数の調整：序盤の掃き出しほど多数生成 • 解列挙の際、目的関数値が最適解より 2.0 以上悪い解が出たら途中打ち切り • 実行可能な解が出やすくなるよう、制約を追加導入 • 掃き出し列以外の箱の移動先は、掃き出し列以外のより大きい番号の箱の上のみ • どうしても実行可能解が見つからなかったら一時的にルールベースに切替 • 当初解いた割当問題で想定していない出庫が生じたら、掃き出し方を再度最適化 • ルールベースで行う積み直しの改善（評価関数の値が良い隣接箇所は壊さない、等） • 盤面評価の際、既にソート済の範囲に含まれる箱の値は存在しないものとする • 例：6 と 7 がソート済の列に埋まっている 5 と 8 は隣接した値とみなす • ケース毎の実行時間のぶれが大きく、ビーム幅固定は一旦断念し chokudai サーチ採用 66

補足：隣接評価関数の詳細・具体的な値 評価 （コスト換算のお得度） • 未ソート箇所の隣接評価関数 は実験的に以下のような値に決定 • の場合：ゼロ • の場合：手で調整した結果、現状以下のグラフのように設定されている • （おそらく更に調整の余地がある） 以上 未満の未ソートの箱の個数 67

補足：盤面全体の評価関数 • ビームサーチのために、盤面同士の優劣を比較するための評価関数が必要 • 盤面全体の評価は、全ての箱隣接に関する評価関数の総和で行う • なお、ソート済の区間や既に除去した箱は別途ごく好意的に評価 • コスト換算で盤面がどれだけ完成形に近づいたか（という気持ち）を表すので、 異なる列を掃き出した状態間も同じ尺度で比較可能 最終的に箱 1 個あたりコスト 2.3 くらいの 解が欲しいが、ソート済の箱は今後操作不要 → 1 個あたり+2.3 の評価 68

補足：割当問題の k -best 列挙 (Murtyʼs algorithm) 69 • 各ノードに状態として割当問題の入力行列を持ち、その問題の解の昇順にノード探索 • 探索対象ノードの行列の一部要素を に置き換え、高々 個の子ノードを生成 • 番目の子は「子ノードの全ての実行可能解が、親ノードの最適解とちょうど先頭 要素だけ一致」するよう設定 ➡ 全ての解が丁度 1 個のノードの最適解に 根 opt = 19 opt = 21 一致 不 が は一 致 が不 一致 opt = 21 が不一致 は が 一 不 致 一 致 opt = 22 opt = 25 • 各ノードで の割当問題を 回解くので、ここまでで全体 • 割当問題の解法の中身に踏み込んで工夫すると は一致 が不一致 opt = 24

70 補足：割当問題の解法のイメージ • 1 行や 1 列の全要素に同じ値を足し引きしても、明らかに解の構造には影響しない • 以下の条件を満たすような うまい足し引き ができれば、最適解（の 1 つ）だと分かる • 全社員に 0 時間の仕事を割り振れる • 負の値の要素がない 仕事1 仕事2 仕事3 仕事1 仕事2 仕事3 仕事1 仕事2 仕事3 社員1 3 4 6 社員1 0 1 3 社員1 0 1 2 社員2 12 9 10 社員2 3 0 1 社員2 3 0 0 社員3 7 6 9 社員3 1 0 3 社員3 1 0 2 • 社員 1 は何をしても最低 3 時間 • 社員 2 は何をしても最低 9 時間 • 社員 3 は何をしても最低 6 時間 ……なので、最初から差し引く 仕事 3 は誰がやっても 1 時間はかかるので、 最初から差し引く コスト 0 の解発見 → 明らかに最適解 🙌

71 補足：変数の導入 • 行目から引いた累計値を , 列目から引いた累計値を とおく • 入力行列 に対して、操作後の行列を • すなわち とおく • を逐次更新している、とも言える を直接更新するという見方の他、 仕事1 仕事2 仕事3 仕事1 仕事2 仕事3 社員1 3 4 6 0 社員1 0 2 3 3 社員2 12 9 10 0 社員2 2 0 0 10 社員3 7 6 9 0 社員3 0 0 2 7 0 0 0 0 -1 0 • 「仮マッチング」を増やしながら「うまい足し引き」を進めていくアルゴリズムを紹介

72 補足：アルゴリズムの動作 (1/3) • まず社員 1 にコスト最小で「仮マッチング」を成立させる • 明らかに仕事 1 と仮マッチさせるのが最適 • 仮マッチングしたペアの の値をゼロにするため、 1 行目から 3 を引く 仕事1 仕事2 仕事3 仕事1 仕事2 仕事3 社員1 3 4 6 0 社員1 0 1 3 3 社員2 12 9 10 0 社員2 12 9 10 0 社員3 7 6 9 0 社員3 7 6 9 0 0 0 0 0 0 0 0 ：仮マッチング

73 補足：アルゴリズムの動作 (2/3) • 次に、既に仮マッチングが成立した社員が相手を失うことなく、 社員 2 にもコスト最小で「仮マッチング」を成立させる • 単に仕事 2 と仮マッチさせるのが最安 • 仮マッチングしたペアの の値をゼロにするため、 2 行目から 9 を引く 仕事1 仕事2 仕事3 仕事1 仕事2 仕事3 社員1 0 1 3 3 社員1 0 1 3 3 社員2 12 9 10 0 社員2 3 0 1 9 社員3 7 6 9 0 社員3 7 6 9 0 0 0 0 0 0 0 0 ：仮マッチング

74 補足：アルゴリズムの動作 (3/3) • 次に、既に仮マッチングが成立した社員が相手を失うことなく、 社員 3 にもコスト最小で「仮マッチング」を成立させたい • 実は、以下が追加コスト 1 + 6 = 7 でできて最適 • 社員 3 は、仕事 2 を社員 2 から奪う • 社員 2 は、代わりに仕事 3 と仮マッチする 仕事1 仕事2 仕事3 仕事1 仕事2 仕事3 社員1 0 1 3 3 社員1 0 1 3 3 社員2 3 0 1 9 社員2 3 0 1 9 社員3 7 6 9 0 社員3 7 6 9 0 0 0 0 0 0 0 • ……どうやって最適な方法を見つけるのか？ 0 ：仮マッチング

補足：追加コスト最小の仮マッチング更新 • 実は、追加コスト最小の方法は必ず「玉突き」の形 • 仕事を奪われた社員は、代わりに他の仕事を取る • 誰にも仮マッチしていない仕事が取られたら終了 • 最適な「玉突き」は、以下の （左）各行を表す頂点 （右）各列を表す頂点 について重み の辺 の新規仮マッチを指示） … … 全ての （ 頂点のグラフの最短路問題で計算可能 全ての未マッチの から へ 重み 0 の辺 … … … … 現在仮マッチ中のペアには 重み 0 の逆辺 （仮マッチ解除を指示） • 仮マッチング相手がいない左の頂点 を任意に選び、 - 最短路上の全指示に従う 75

76 補足：仮マッチング更新に伴う適切な変数更新 • 最適な玉突きが分かったら、新規仮マッチしたペアの の値をゼロにせねばならない • しかも、更新によってどこかに負の値が生じてはならない • 実は以下の処理で可能 • 最短路問題の始点 から頂点 までの距離を で表す • に を足す • を満たす各右側頂点 に対し以下を実行： • から を引く • が更新前に仮マッチしていた場合、その相手頂点を として 仕事1 仕事2 仕事3 に を足す 仕事1 仕事2 仕事3 社員1 0 1 3 3 社員1 0 2 3 3 社員2 3 0 1 9 社員2 2 0 0 10 社員3 7 6 9 0 社員3 0 0 2 7 0 0 0 0 -1 0

補足：アルゴリズムの振り返り • 仮マッチング増加処理は で可能 • 最短路パートは、負辺が存在しないので の Dijkstra 法で OK • （最短路復元時、重み 0 の辺でループにならないよう注意） • この処理を 回行えばよいので、 で割当問題が解ける • 事前に簡単な計算で仮マッチングを作っておくなどの工夫で実用上更に高速になる • 詳細は参考文献などを参照 77

補足：Murtyʼs algorithm に対する計算量削減 • 子ノードで解くべき割当問題は、親ノードの問題に対して以下の更新を行ったものに 限られ、いずれも効率的に対処可能 • 特定のペアのマッチングの固定 • 単に子ノードの問題を解く際に該当行や列を「なかったもの」とすればよい • 特定のペアのマッチングの禁止 • 入力行列の特定の要素 の値を に更新することに相当 • 親ノードの解を流用すれば、既に を除く 組の仮マッチング成立 • 親ノードの解から仮マッチング を解除した状態を初期値にとり 仮マッチング増加を 1 回行えば子問題が解ける • ➡ 子ノードの各問題が で解けて、k -best 列挙の計算量が に🎉 78