凸関数じゃないですか (最大値/最小値を求める問題) 目的関数を固定する (最大値/最小値を最小/最大化する問題)

Presentation on theme: "凸関数じゃないですか (最大値/最小値を求める問題) 目的関数を固定する (最大値/最小値を最小/最大化する問題)"— Presentation transcript:

1 凸関数じゃないですか (最大値/最小値を求める問題) 目的関数を固定する (最大値/最小値を最小/最大化する問題)
全探索を忘れるな まずは何をさておき「全通り試す」計算の計算量を確認 凸関数じゃないですか (最大値/最小値を求める問題) 最大値/最小値は凸関数なら賢さ不要で数値的に三分探索できる 目的関数を固定する (最大値/最小値を最小/最大化する問題) 「最小値 x にできる？」という問題なら簡単に yes/no 答えられる？ ならば x を全探索。単調ならば二分探索。 前から順に固定する (辞書順最小を求める問題) 「1文字目をaにしたら解がある？ない？」を繰返し１文字ずつ決める 黙ってグラフにしてみよう 探索→状態空間がグラフ。グループ分け→最小カット。整数→mod N で N 点グラフ 二部グラフではないですか 特に二部グラフにならないか注意深く観察しよう。チェス盤白黒など 条件反転してみよう 「○○を満たす物は何個？」 → 「○○を満たさないものは何個？」 期待値ならば線形性 問題を分解 E(aX+bY) = aE(X) + bE(Y) 小さいところで規則を探す (数学ゲー) 小さい入力を全探索して眺める 巨大なメモ化はmapにしない! 配列にすると20倍は速い 無根拠決めつけ全探索 実はこのケースだけ考えれば十分なのでは？と決めつけ突撃 するときは、計算時間の許す限り他のケースも調べるコードを書く n4 604 ≒ 1300万 1304/4!≒1000万 n5 255 ≒ 1000万 705/5!≒1400万 Σ nk Σ<404≒2000万 ≒ nk+1 / k+1 3n 315 ≒ 1500万 2nC n 26C13 ≒ 1000万 ≒ 2n / √n

2 二部グラフ ツリー n次元グリッドの縦横隣接関係 2次元グリッドのセル

3 最小辺カバー 最大マッチング 任意 二部グラフ DAG 最小独立Pathカバー 二部グラフ 推移律 最小点カバー 任意 最大独立点集合

4 最大マッチ （最大独立辺集合） P 二部グラフ：P max E’ ⊂ E where
∀e1, e2 ∈ E’. e1 disjoint e2 一般：O(V4) 等 らしい Proof: 交代路の一般化とか 二部グラフ ： O(VE) Proof: 左から右に最大フローを流す。

5 最小点カバー NP-Hard 二部グラフ：P min V’ ⊂ V where ∀e ∈ E. e intersect V’
最大マッチ ≦ 最小点カバー Proof: 最大マッチに含まれる辺集合を覆うには 最低でも、それだけの点が必要 V2 V1 【二部グラフ】 [König1931] 最大マッチ ＝ 最小点カバー V0 = マッチング E’ に含まれない左点集合から 交代路によるBFSをする（奇数ステップではE’以外の辺、偶数ではE’の辺で進む）。E’ のうち交代路に含まれた辺では右点、else左点を取ると点カバー。 Proof: ・ E’の辺は明らかにカバーされる。 ・ 奇数長交代路があると反転して最大マッチを伸ばせるので交代路は偶数長。カバーされる。 ・ 入らない辺は、V0 の構成より左点がマッチングに含まれている。そのマッチング辺が交代路に含まれない→左点がカバーされる。含まれる→今の辺の行き先は交代路の右点。カバーされる。 V0 V0

6 最大独立点集合 NP-Hard 二部グラフ：P max V’ ⊂ V where ∀e ∈ E. e ⊈ V’ |V| - 最小点カバー
＝ 最大独立点集合 Proof: 点カバー＝全ての辺で、どっちかの端は押さえる 独立点集合＝全ての辺で、両方押える事はない よって最小点カバーの補集合をとれば、 最大独立点集合。

7 最小辺カバー P 二部グラフ：P min E’ ⊂ E where ∀v ∈ V. v intersect E’ 最小辺カバー
(or, in short, min E’ where V=∪E’ ) Meaningful only when no isolated vertex 最小辺カバー ＝ 最大マッチ＋残り頂点数 ＝ |V| - 最大マッチ Proof: つまり最大マッチを計算して、あぶれた頂点それぞれについて一つずつ辺を足す。 ≦ は自明。 ≧。極小辺カバー E’ をとり、E’ に限定した最大マッチを M とする。点を覆う貢献を数えると |M|*2 + |E’-M| ＝ |V| 。よって |E’|=|V|-|M|。 よって |E’| が全体の最大マッチを含む時最適。

8 最小独立Pathカバー (有向グラフ ; 無向でも二重化するだけ)
NP-Hard 最小独立Pathカバー (有向グラフ ; 無向でも二重化するだけ) DAG：P min P ⊂ P(V) where V = disjoint union of P and ∀p∈P. p is a path [Gallai & Migram 1960] 最小Pathカバー 　≦ 最小独立Pathカバー ≦ 最大独立点集合 Proof: Pathの最後の頂点の集合を ter(P) と書く。 「ter(P) が極小なら |ter(P)| 個のMISを取れる」 を |V| に関する帰納法で示す。 - ter(P) が独立なら証明完。 - ter(P) が独立でない、 v2-> v1 だったとする。 v1を削ったグラフでのP’=P–v1も極小な事を示す 　（そうすれば帰納法より|P’|のMISが取れる） v1の直前以外が減ったもっと小さいPathカバーが あったとするとPの極小性に反する。v1が減ったとするとv2にv1を繋げられるのでやはり反する 【推移律のあるグラフ】 最小Pathカバー＝MIS Proof: ≧がすぐ言える。 独立なの全部別でカバーするしか内。

9 最小独立Pathカバー NP-Hard DAG：P min P ⊂ P(V) where 強制二部グラフ化（src/dst 分離）
V = disjoint union of P and ∀p∈P. p is a path 強制二部グラフ化（src/dst 分離） G = (V, E)  G’ = (V∪V’, {(v,u’) | (v,u)∈E}) |V| - 最小独立Pathカバー ≦ 強制二部の最大マッチ Proof: 独立Pathカバーの辺を全部突っ込むとマッチングである。（独立Pathなので枝分かれや合流なし。） k本の独立PathカバーPの頂点数は k+|P| =|V| なので、|V| - k のマッチングがこれで得られる。 【DAG】 |V| - 最小独立Pathカバー ＝ 強制二部の最大マッチ Proof: 最大マッチを求めて属す辺をすべてとる。 マッチに関われなかった頂点を単独でパスと して入れる。すると独立Pathカバーである。 ・ マッチングなので枝分かれ合流はできない ・ DAGなので、サイクルもできない。∴独立Path ・ カバーなのは構成より。 サイズは → の議論より。