【しっかり学ぶ数理最適化】4.2~4.3.1

2025年後期輪読会 #9 しっかり学ぶ数理最適化 4.2~4.3.1 京都大学 総合人間学部 B1 本川玄人 0

アジェンダ ◼ 4.2 アルゴリズムの性能と問題の難しさの評価 ◼ 4.3 効率的に解ける組み合わせ最適化問題 1

アジェンダ ◼ 4.2 アルゴリズムの評価と問題の難しさの評価 ◼ 4.3 効率的に解ける組み合わせ最適化問題 2

4.2.1 アルゴリズムの計算量とその評価 時間量(計算手間) : 計算終了までに実行される基本演算の回数 領域量 : 計算の途中経過を一時的に保存するために必要な記憶領域 計算量 : 時間量と領域量の総称 アルゴリズムの性能は時間量によって評価されることが多い 領域量 計算量 時間量 3

4.2.1 アルゴリズムの計算量とその評価 性能を評価する:オーダー記法 入力データの長さを𝑁、計算量を𝑇(𝑁)とする。ある正の定数𝑐と ഥ ഥ 𝑁が存在して、𝑁 ≥ 𝑁に対して常に 𝑇(𝑁) ≤ 𝑐𝑓(𝑁) が成り立つとき、𝑇 𝑁 = Ο(𝑓(𝑁)) と表す。これをオーダー記法という。 𝑁と独立な定数𝑘を用いてΟ 𝑁 𝑘 で表すことが出来るとき、多項式オーダーという 多項式オーダーで表せるかどうかでアルゴリズムの実用性を評価することが多い また、このアルゴリズムを多項式アルゴリズムという 4

4.2.2 問題の難しさとNP困難問題 問題自身の難しさを評価する 入力データの長さ𝑁の問題例からなる問題𝑄を考える。問題例𝐼∈𝑄に対するアルゴリズム𝐴の計算量を 𝑇𝐴 (𝐼)としたとき、 𝑇𝐴 𝑄 = max 𝑇𝐴 (𝐼) 𝐼∈𝑄 を問題Qに対するアルゴリズムAの計算量と定義する。 これを最小にするアルゴリズムを選んだときを問題の難しさとする。すなわち、 問題𝑄を解くアルゴリズムの集合を𝐴(𝑄)としたとき、問題を𝑄の難しさ𝑇(𝑄)を 𝑇 𝑄 = min 𝑇𝐴 𝑄 と定義する。 𝐴∈𝐴(𝑄) 長さNに対する多項式時間アルゴリズムが知られている問題のクラスをPと記す。 5

4.2.2 問題の難しさとNP困難問題 決定問題:個々の問題例に対してある性質を満たすかどう かを判定し、yesかnoの回答を求める問題 答えがyesとなる解を多項式オーダーの時間量で確認出 来るとき、その決定問題のクラスをNPと記す P⊆NPであるが、P=NPが成り立つか？ →「P=NP問題」 P≠NPと予想されているが、未解決 帰着可能性という概念を使ってこの問題を考察する 6

4.2.2 問題の難しさとNP困難問題 帰着可能性の概念を用いて考える 2つの決定問題QとQ’を考える。問題Q’の任意の問題例I’がその問題例の入力データの 長さNに対する多項式時間アルゴリズムにより問題Qのある問題列Qのある問題列Iに 変換でき、問題Q’における問題例I’の答えと問題Qにおける問題例Iの答えが常に一致 するとき、問題Q‘は問題Qに帰着可能であるという。 この変換によって、問題Qが多項式時間で解けるなら問題Q’も多項式時間で解けることが分かる ただし、 (問題Q’の難しさ)≤(問題Qの難しさ) である。 この変換を繰り返し、クラスNPの中で最も難しい問題を考える。このとき、次を満たす: (1)問題QはクラスNPに含まれる (2)クラスNPに含まれる任意の問題Q’が問題Qに帰着可能 このような決定問題QをNP完全という。 巡回セールスマン問題、ナップサック問題などはNP完全であると知られている 7

4.2.2 問題の難しさとNP困難問題 ここまで決定問題を考えたが、ある最適化問題はクラスNPには含まれない クラスNPに含まれる任意の決定問題Q’が最適化問題Qに帰着可能 であるとき、最適化問題QをNP困難という。巡回セールスマン問 題はNP困難である。 以上から、あるNP完全問題の多項式時間アルゴリズムを見つければ全て のクラスNPの問題に多項式時間アルゴリズムを作れるが、まだ見つかっ ていない 8

アジェンダ ◼ 4.2 アルゴリズムの評価と問題の難しさの評価 ◼ 4.3 効率的に解ける組み合わせ最適化問題 9

4.3 効率的に解ける組み合わせ最適化問題 資源配分問題の問題設定 資源配分問題 事業数:n 総資源量:B 事業jに資源𝑥𝑗 単位配分すると利益𝑓𝑗 (𝑥𝑗 )が生じるとする 目的関数: σ𝑛𝑗=1 𝑓𝑗 (𝑥𝑗 )（最大化） 制約条件: σ𝑛𝑗=1 𝑥𝑗 = 𝐵, 𝑥𝑗 ∈ ℤ+ 𝑓𝑗 (𝑥𝑗 )は凹関数であると仮定する。このとき、利益の変化量 𝑑𝑗 𝑥𝑗 = 𝑓𝑗 𝑥𝑗 + 1 − 𝑓𝑗 (𝑥𝑗 )は単調減少 貪欲法を使って最適解を求めることが出来る 10

4.3 効率的に解ける組み合わせ最適化問題 アルゴリズムと例 資源配分問題の貪欲法 Step1: 初期解を𝕩 = (0,0, … , 0)𝑇 とする Step2: σ𝑛𝑗=1 𝑥𝑗 = 𝐵ならば終了 Step3:𝑑𝑗 𝑥𝑗 = max 𝑑𝑘 (𝑥𝑘 )を満たす事業jを求め、 𝑘=1,2,…,𝑛 𝑥𝑗 = 𝑥𝑗 + 1としてStep2に戻る 例:１票の重みのばらつきの最小化(ウェブスター法) 目的関数: σ𝑛𝑗=1 𝑝𝑗 ( 𝑥𝑗 𝑝𝑗 − 𝑏)2 （最小化） 制約条件: σ𝑛𝑗=1 𝑥𝑗 = 𝐵, 𝑥𝑗 ∈ ℤ+ 𝑥𝑗 2𝑥𝑗 +1 𝑝𝑗 𝑝𝑗 𝑝𝑗 ( − 𝑏)2 は凸関数なので貪欲法が適用できる。変化量は min 𝑗=1,2,…,𝑛 2𝑥𝑗 +1 𝑝𝑗 − 2b より、 を求めると良い。 11

4.3 効率的に解ける組み合わせ最適化問題 最小全域木問題を解く クラスカル法とプリム法を扱うが、その前にこれらの方法の基礎となる 定理を確認する 定理4.2 任意のカット𝛿 𝑆 𝑆 ⊂ 𝑉 について、𝛿(𝑆)の中で長さが最小となる辺は 最小全域木𝑇 ∗ に含まれる グラフ𝐺 = (𝑉, 𝐸)は連結、𝑒 ∈ 𝐸の長さ𝑑𝑒 はすべて異なると仮定する 12

4.3 効率的に解ける組み合わせ最適化問題 クラスカル法の説明 クラスカル法 step1: すべての辺を長さの昇順に整列し、𝑑𝑒1 ≤ 𝑑𝑒2 ≤ ⋯ ≤ 𝑑𝑒|𝐸| とする k=1,𝑇 = 𝜙とする step2: 𝑇 = 𝑉 − 1ならば終了 Step3: 𝑇 ∪ {𝑒𝑘 }が閉路を含まないとき𝑇 = 𝑇 ∪ {𝑒𝑘 }とする。K=k+1として step2に戻る 全体を眺めて長さが短いところからつなげる 操作を続けることで得られる 13

4.3 効率的に解ける組み合わせ最適化問題 プリム法の説明 プリム法 Step1: 任意の頂点を１つ選び𝑣0 とする。𝑆 = 𝑣0 , 𝑇 = 𝜙とする。 Step2: 𝑆 = 𝑉なら終了 Step3: min{𝑑𝑒 |𝑒 ∈ 𝛿(𝑆)}を達成する辺𝑒 ∗ = {𝑢∗ , 𝑣 ∗ }(𝑢∗ ∈ 𝑆, 𝑣 ∗ ∈ 𝑉 ∖ 𝑆)を求め、 𝑇 = 𝑇 ∪ 𝑒 ∗ , 𝑆 = 𝑆 ∪ {𝑣 ∗ }としてstep2に戻る 任意の頂点からスタートして全体をつなげる 14