【しっかり学ぶ数理最適化】4.3.2

2025年後期輪読会 #9 (12/18) しっかり学ぶ数理最適化 4.3.2 動的計画法 京都大学 理学部 数理科学系 B3 千葉 一世 0

アジェンダ ◼ ナップザック問題 ◼ 資源分配問題 ◼ 最小費用弾性マッチング問題 ◼ 最短路問題 • ダイクストラ法 • ベルマン・フォード法 • フロイド・ウォーシャル法 1

アジェンダ ◼ ナップザック問題 ◼ 資源分配問題 ◼ 最小費用弾性マッチング問題 ◼ 最短路問題 • ダイクストラ法 • ベルマン・フォード法 • フロイド・ウォーシャル法 2

動的計画法 動的計画法：問題をより小さな部分問題に分割し、部分問題の最適解を保存・参照しながら、 大きな部分問題を順に求めていく手法 メモリ(領域量)を犠牲に効率化している。 イメージとしては、漸化式と帰納法で下から順に全ての値を求めていく 例：フィボナッチ数列 漸化式 𝐹𝑛+2 = 𝐹𝑛+1 + 𝐹𝑛 を用いてフィボナッチ数列を求めていく際に、値の保存を 行わなければ、同じ数列を毎回毎回計算し直すが、保存すればスムーズに計算できる。 動的計画法が有効となる問題は、「部分問題の重複性」と「部分構造最適性」がある物である。 部分問題の重複性 再帰的に計算する際に全く同じ部分問題が繰り返し現れるという性質。 部分問題の最適解を保存することで、同じ問題を繰り返し解く必要がなくなる。 (分割統治法では、分割した部分問題が完全に独立した状態になる。) 部分構造最適性 元の問題の最適解が、その部分問題の最適解から構成できる性質。 既に解かれた部分問題の最適解を参照して楽に最適解が求められる。 3

ナップサック問題 荷物 𝑗 の価格𝑝𝑗 , 重さ𝑤𝑗 、最大容量 𝐶 としたナップザック問題を解く。(値は全て整数とする) 部分問題として、荷物を1~𝑘まで・容量を 𝑢 に制限した場合を考え、 (部分問題もまたナップザック問題になっている) 元の問題 部分問題 𝑘: 1~𝑛, 𝑢: 1~𝐶に対する、𝑛𝐶個の部分問題の最適値𝑓(𝑘, 𝑢)を帰納的に求めていく。 ナップザック問題の動的計画法１ Step1: 𝑓 1, 𝑢 , 𝑢 = 1, … , 𝐶 を計算する。𝑘 = 1とする。 Step2: 𝑘 = 𝑛なら終了。そうでなければ𝑘 = 𝑘 + 1とする。 Step3: 漸化式から、 𝑓 𝑘, 𝑢 , ( 𝑢 = 1, … , 𝐶) を計算し、Step2に戻る。 4

ナップサック問題 𝑘の場合：𝑢 < 𝑤𝑘 の時、荷物𝑘は追加できないため、f 𝑘 − 1, 𝑣 が最大となる。 u < 𝑤𝑘 の時、荷物𝑘を追加することができ、追加する場合としない場合を比較する。 追加する場合：𝑘 − 1までで重さがu − 𝑤𝑘 以下となる必要があり、価値𝑝𝑘 がある。 追加しない場合： 𝑘 − 1までで重さが u となる必要がある。 各𝑓(𝑘, 𝑢)は漸化式より定数時間で計算できるので、この方法の時間量 O(𝑛𝐶)となる 例 右図のように部分問題の最適値が順に求まり、 𝑓(4,7)の値と、求める際の追加したkの推移から 最適解は、 1,0,0,1 𝑇 5

ナップサック問題 別の部分問題として、荷物を1~𝑘まで・価値合計がぴったり 𝑣 になる場合の重み最小化を考える。 (ナップザック問題とは、条件と目的関数が逆になっている。) 元の問題 部分問題 𝑛 𝑘, 𝑣での最適値を 𝑔 𝑘, 𝑣 、条件を満たす組が無い場合は + ∞ を取る物とし、 𝑃 = Σ𝑗=1 𝑝𝑗 として、 ナップザック問題の動的計画法2 Step1: Step2: Step3: g 1, 𝑣 , ( 𝑣 = 1, … , 𝑃) を計算し、𝑘 = 1とする。 𝑘 = 𝑛なら終了。そうでなければ𝑘 = 𝑘 + 1とする。 漸化式から、 g 𝑘, 𝑣 , ( 𝑣 = 1, … , 𝑃) を計算し、Step2に戻る。 6

ナップサック問題 𝑘の場合：𝑣 < 𝑝𝑘 の時、荷物𝑘は追加できないため、𝑔 𝑘 − 1, 𝑣 が最小となる。 𝑣 < 𝑝𝑘 の時、荷物𝑘を追加することができ、追加する場合としない場合を比較する。 追加する場合：𝑘 − 1までで価値が𝑣 − 𝑝𝑘 となる必要があり、重み𝑤𝑘 がかかる。 追加しない場合： 𝑘 − 1までで価値が𝑣となる必要がある。 この方法では一つ目の方法と異なり、求めるべき(𝑘, 𝑣)の組が分からないので、 𝑛 𝑣を価値合計の最大値である 𝑃 = Σ𝑗=1 𝑝𝑗 まで求めておく必要がある。 各g(𝑘, 𝑢)は漸化式より定数時間で計算できるので、この方法の時間量 O(𝑛𝑃)となる 例 右図のように部分問題の最適値が求まり、 元の問題の、重さの最大が4より、4以下で価値が 最大となる物を探して、最適解 0,1,1,0 𝑇 7

ナップサック問題 全て列挙する場合は、2𝑛 通りの組合せに、重さ・価値の和の計算でnかかるので、時間量𝑂 𝑛2𝑛 動的計画法により、𝑂 𝑛𝐶 , 𝑂(𝑛𝑃)と、指数を多項式に改善できた。 (入力数字が入るため擬多項式ではある。) 8

アジェンダ ◼ ナップザック問題 ◼ 資源分配問題 ◼ 最小費用弾性マッチング問題 ◼ 最短路問題 • ダイクストラ法 • ベルマン・フォード法 • フロイド・ウォーシャル法 9

資源配分問題 事業 𝑗 の資源に対する利益を一般の関数𝑓𝑗 (𝑥)、資源総量 𝐵 としたナップザック問題を解く。 部分問題として、事業を1~𝑘まで・資源総量を 𝑢 に制限した場合を考え、 (部分問題もまた資源配分問題になっている) 元の問題 部分問題 𝑘: 1~𝑛, 𝑢: 1~𝐵に対する、𝑛𝐵個の部分問題の最適値𝑓(𝑘, 𝑢)を帰納的に求めていく。 資源配分問題の動的計画法 Step1: 𝑓 1, 𝑢 = 𝑓1 (𝑢), 𝑢 = 1, … , B を計算する。𝑘 = 1とする。 Step2: 𝑘 = 𝑛なら終了。そうでなければ𝑘 = 𝑘 + 1とする。 Step3: 漸化式から、 𝑓 𝑘, 𝑢 , ( 𝑢 = 1, … , 𝐵) を計算し、Step2に戻る。 10

資源配分問題 𝑓(1, 𝑢)は、事業1に資源uを入れるので、𝑓1 (𝑢) 𝑓(𝑘, 𝑢)は、事業kにどれだけの資源を入れるかで比較して、𝑥𝑘 = 0, … , 𝑢の場合に、 最適値は、𝑓𝑘 𝑥𝑘 と事業k-1までに、資源𝑢 − 𝑥𝑘 の場合の最適値となる。 各f 𝑘, 𝑢 は𝑢個比較する漸化式より𝑂(𝐵)で計算できるので、この方法の時間量 𝑜(𝑛𝐵2 )となる 例 右図のように部分問題の最適値が順に求まり、 𝑓(4,6)の値と、求める際の追加した𝑘, 𝑥𝑘 の推移から 最適解は、 0,2,0,4 𝑇 11

アジェンダ ◼ ナップザック問題 ◼ 資源分配問題 ◼ 最小費用弾性マッチング問題 ◼ 最短路問題 • ダイクストラ法 • ベルマン・フォード法 • フロイド・ウォーシャル法 12

最小費用弾性マッチング問題 弾性マッチング：2つの列𝐴, 𝐵のマッチング(要素のペア集合) 𝑀 で、以下の2つを満たす物 𝐴 = 𝑎1 , 𝑎2 , … , 𝑎𝑚 , 𝐵 = (𝑏1 , 𝑏2 , … , 𝑏𝑛 )で、𝑀 ⊂ 𝐴 × 𝐵 (1) (2) 𝐴, 𝐵の任意の要素は𝑀内のペアに含まれる。 ∀ 𝑎𝑖 , 𝑏𝑗 , 𝑎𝑘 , 𝑏𝑙 ∈ 𝑀に対し、𝑖 < 𝑘なら𝑗 ≤ 𝑙となる。 マッチングは、𝐴, 𝐵 を順番に並べた頂点集合とした二部グラフの辺集合として考えられる。 このとき、図で考えると、(1)は孤立点が無いこと・(2) は辺が交わらないことを意味する。 最小費用弾性マッチング問題：与えられた列𝐴, 𝐵と、ペア 𝑎𝑖 , 𝑏𝑗 に対するコスト𝑐𝑖𝑗 から、 総コストが最小となる弾性マッチングを求める問題 13

最小費用弾性マッチング問題 部分問題として、列𝐴, 𝐵を𝐴𝑖 = 𝑎1 , 𝑎2 , … , 𝑎𝑖 , 𝐵𝑗 = (𝑏1 , 𝑏2 , … , 𝑏𝑗 )に制限した問題を考える。 この部分問題の最適値を𝑓(𝑖, 𝑗)で表して、帰納的に求める。 最小費用弾性マッチング問題の動的計画法 Step1: Step2: Step3: 𝑓 1,1 = 𝑐11 , 𝑓 𝑖, 1 = 𝑓 𝑖 − 1, 1 + 𝑐𝑖1 (𝑖 = 2, … , 𝑚)を計算する。𝑗 = 1とする。 𝑗 = 𝑛なら終了。そうでなければ𝑗 = 𝑗 + 1とする。 漸化式から、 𝑓 1, 𝑗 , 𝑓(𝑖, 𝑗) (𝑖 = 2, … , 𝑚)を計算し、Step2に戻る。 𝑓 1, 𝑗 ： 弾性マッチングは、𝑎1 と全ての𝑏を結ぶ物のみ 𝑓 𝑖, 𝑗 , 𝑖 ≥ 2：弾性マッチングとなるために、 𝑎𝑖 , 𝑏𝑗 ∈ 𝑀が必要であり、次の3通りのみ考えられる。 (1) 𝑎𝑖 のペアは𝑏𝑗 のみ・𝑏𝑗 のペアは𝑎𝑖 のみ (2) 𝑎𝑖 と𝑏𝑗−1 のペアを含む (3) 𝑎𝑖−1 と𝑏𝑗 のペアを含む (1),(2),(3)のいずれの場合も、弾性マッチングになることの必要十分条件は、 𝑎𝑖 , 𝑏𝑗 を除いても弾性マッチングとなることであるので、それぞれの部分最適値から求まる。 各𝑓(𝑖, 𝑗)は漸化式より定数時間で計算できるので、この方法の時間量 𝑜(𝑛𝑚)となる 14

アジェンダ ◼ ナップザック問題 ◼ 資源分配問題 ◼ 最小費用弾性マッチング問題 ◼ 最短路問題 • ダイクストラ法 • ベルマン・フォード法 • フロイド・ウォーシャル法 15

最短路問題 グラフの最短路を求める問題は、有向グラフの接続行列が完全単模行列となり、単体法で解ける。 これを、動的計画法を用いてより効率良く求めるアルゴリズムを考える。 単一点対最短路問題：固定した始点と終点間の最短路を求める問題 単一始点最短路問題：固定した始点から全ての点との最短路を求める問題 全点対最短路問題：全ての頂点間の最短路を求める問題 重みの合計が負になる閉路を負閉路という。負閉路が存在する場合は、 その負閉路を繰り返し通ることでいくらでも小さくなってしまう。 負閉路が存在しない場合、閉路が存在しても重み非負なので、 その閉路を除いて閉路を含まない最短路(単純路)が得られる。 (負閉路を含む場合に最短単純路を求める問題はNP困難) 以下、グラフは任意の二点間の両方向の有効路が存在する強連結な有向グラフを仮定して考える。 16

最短路問題 定理4.3 𝑣 ∈ 𝑉に対し、𝑓𝑣 を始点𝑠から𝑣へのある路の長さとする。このとき、 ∀ 𝑣 ∈ 𝑉, 𝑓𝑣 が始点𝑠から𝑣への最短路の長さ ⟺ 𝑓𝑣 ≤ 𝑓𝑢 + de , ∀ e = u, v ∈ 𝐸 Proof (⟹) ∀ (⟸) ∀ e = u, v ∈ 𝐸に対し、𝑓𝑢 を実現する路に𝑒を加えると𝑠から𝑣への路となる。 𝑓𝑣 の最短路性より、 𝑓𝑣 ≤ 𝑓𝑢 + de 𝑣 ∈ 𝑉に対し、𝑠から𝑣への路を任意に取り、𝑠 = 𝑣1 → 𝑣2 → ⋯ → 𝑣𝑘 = 𝑣とする。 𝑒𝑖 = (𝑣𝑖 , 𝑣𝑖+1 )として、 𝑓𝑣𝑖+1 ≤ 𝑓𝑣𝑖 + de𝑖 より、総和を取って 𝑘−1 𝑘−1 ෍ 𝑑𝑒𝑖 ≥ ෍ 𝑓𝑣𝑖+1 − 𝑓𝑣𝑖 = 𝑓𝑣 − 𝑓𝑠 = 𝑓𝑣 𝑖=1 𝑖=1 従って、 𝑓𝑣 は始点𝑠から𝑣への最短路の長さを表す。 この𝑓𝑣 ≤ 𝑓𝑢 + de の関係を三角不等式という。 17

最短路問題 始点𝑠から頂点𝑣への最短路の長さを、𝑓𝑣∗ とする。 系4.1 始点𝑠から頂点𝑣への路𝑃𝑣 = (𝑠 = 𝑣1 → 𝑣2 → ⋯ → 𝑣𝑘 = 𝑣)が最短路 ⟺ 𝑓𝑣∗𝑖+1 = 𝑓𝑣∗𝑖 + de𝑖 , Proof (⟹) (⟸) ∀ 𝑒𝑖 = 𝑣𝑖 , 𝑣𝑖+1 ∈ 𝐸, i = 1, … , k − 1 𝑘−1 ∗ 定理4.3より、最短性と総和より、 σ𝑘−1 𝑖=1 𝑑𝑒𝑖 = 𝑓𝑣 ≤ σ𝑖=1 𝑑𝑒𝑖 よって、総和を取る前の全ての不等式で等号が成立する。 𝑓𝑣∗𝑖+1 − 𝑓𝑣∗𝑖 = de𝑖 を総和取って、 𝑓𝑣∗ = σ𝑘−1 𝑖=1 𝑑𝑒𝑖 より、最短 系4.2 始点𝑠から頂点𝑣への最短路を𝑃𝑣 = (𝑠 = 𝑣1 → 𝑣2 → ⋯ → 𝑣𝑘 = 𝑣)として、 ∀ i = 1, … , kに対して、𝑃𝑣 の途中までの路𝑃𝑣𝑖 = (𝑠 = 𝑣1 → 𝑣2 → ⋯ → 𝑣𝑖 )は最短路 Proof 𝑃𝑣 で系4.1より、𝑃𝑣𝑖 で系4.1の等号が成り立つは明らか 18

最短路問題(ラベリング法) ラベリング法：各点𝑣 ∈ 𝑉の路の長さの上界ラベル𝑓𝑣 をより小さく更新していく手法 ラベリング法 Step1: 𝑓𝑠 = 0, 𝑓𝑣 = +∞, (∀ 𝑣 ∈ 𝑉 ∖ {𝑠})とする。 Step2: 頂点𝑣 ∈ 𝑉を一つ選ぶ Step3: 頂点vから出る辺𝑒 = 𝑣, 𝑢 ∈ 𝐸に対して、𝑓𝑢 > 𝑓𝑣 + 𝑑𝑒 の時に、 𝑓𝑢 ← 𝑓𝑣 + 𝑑𝑒 と更新 Step4: 負閉路が見つかる or ∀ e ∈ Eが三角不等式𝑓𝑢 ≤ 𝑓𝑣 + 𝑑𝑒 を満たす場合に終了 そうでなければStep2に戻る ラベリング法は様々な最短路問題のアルゴリズムのベースとなっており、 Step2の次の頂点の選択の方法によって種類がある。主な種類として以下の二つがある。 • ダイクストラ法(ラベル確定法) 始点に近い方から順に確定させていく方法 • ベルマン・フォード法(ラベル修正法) 全ての点を一周更新させることを繰り返す。 19

20