組合せ最適化問題と厳密解法 • 最小木、ナップサック問題、ビンパッキング、巡回セールスマン問題 • LPによる上界・下界 • 分枝限定法 • 帰着とNP完全性組合せ最適化 • 決定すべき変数が、組合せ的（集合の部分集合）であるような数理計画問題を組合せ最適化という E: 集合、 X : 実行可能な E の部分集合 F: 変数、E の部分集合、 f: 部分集合上で定義された目的関数最小化 f(F) 制約条件 F ∈ X （ただし、 X ⊆ 2E ）応用：広い • NP-hard。100変数ぐらいから解けなくなる • 誤差が多少あってよいなら、それなりに速く解ける組合せ最適化：たとえば • マッチング問題、割当て問題、配送計画、ビンパッキング、巡回セールスマン問題、施設配置問題、スケジューリング、時間割作成問題、勤務表作成問題、ナップサック問題、安定集合問題、分割問題、ネットワークデザイン問題、集合被覆問題、など • だいたい、NP-hard 問題 • 個々の問題に、個別の解法が研究されている 10000変数くらいのものが解ける問題から、 50くらいでアップアップのものまで様々 01整数計画として定式化 • 部分集合を決定する、という定式化では、一般の数理計画の上に乗せずらい • そこで、通常の数理計画のテイストで定式化してみる + E = {1,…,n } + F  (x1, x2,…,xn) で表す。つまり、 F に i が入っているとき、xi = 1 最小化 f(x1, x2,…,xn) 制約条件 g(x1, x2,…,xn) ≦ b x1, x2,…,xn ∈ { 0,1 } • 多くの場合、f, g は線形の式で記述できる基礎的な問題 • 数学的にきれいな構造がある  基本的な解法がある • 直接的な応用はあまりない  単純化した場面を想定して用いられる • 他の問題を解くとき、子問題として現れる  他の問題の特殊ケースになっている最小全張木問題 • グラフ G=(V,E) と枝のコスト w が与えられる • 家と家を電話線で結び、ネットワークを作る • どういう結び方にすると、コスト最小になるだろうか 5 6 3 8 4 7 2 01整数計画で定式化 • グラフ G=(V,E) 枝のコスト w が与えられる • 選ぶものは枝なので、枝に変数を割り当てる • サイクルを作ってはいけないので、各サイクル(長さk) に対して、その中の k-1 本以上は使ってはいけない、という制約を入れる最小化 Σwixi 制約 Σi∈C xi ≦ |C|-1 (全てのサイクル C について) 3 Σ xi = |V|-1 xi ∈ { 0,1 } • 制約式が指数本ある 5 6 8 4 7 2 クラスカル法 • クラスカル法という方法を使うと、簡単に解ける • コストの小さい枝から採用していく • 無駄な枝（サイクルができる枝）は採用しない 5 6 3 8 4 7 2 クラスカル法の正当性 • クラスカル法で最小木でないもの（偽者）が求まった！ • 「最小木に含まれない偽者の枝」の中で、最も早く加えられたものを e とする  e より先に加えられた枝は最小木と偽者で等しい • 最小木に e を加えるとサイクル C ができる • C には e より重い枝がある  入替ればもっと軽くなる e クラスカル法の計算時間 • コストの小さい枝から採用していく  枝をコストでソート O( |E| log |E| ) • サイクルができるかどうかのチェック－２分木を使って O( log |V| ) －最大 |E| 回 5 • 合計 O( |E| log |E| ) 時間 6 3 8 4 7 2 プリム法 • ある頂点を選ぶ • 頂点（集合）から出て行く枝で、コスト最小枝を採用 • 新たにつながった頂点を集合に入れる 5 6 3 8 4 7 2 プリム法の正当性 • プリム法で最小木でないもの（偽者）が求まった！ • 「最小木に含まれない偽者の枝」の中で、最も早く加えられたものを e とする  e より先に加えられた枝は最小木と偽者で等しい • 最小木に e を加えて、出来るサイクルに、e より重い枝がある  入替ればもっと軽くなる e プリム法の計算時間 • ある頂点を選ぶ定数時間 • 頂点（集合）から出て行く枝で、コスト最小枝を採用－出て行く枝をヒープに入れる。１本あたり O( log |E| ) －内部同士を結ぶようになった枝は消す１本あたり O( log |E| ) －消された枝は、２度とヒープに入らない 5  合計 O( |E| log |E| ) 時間 6 3 8 4 7 2 難しい問題 • 最小全張木問題は、組合せ最適化の中でも比較的簡単に（多項式時間で）解ける問題 • 他にも、最大マッチング、最小費用流、最短路などが、楽に解ける（多項式時間で）問題 • しかし、こういった簡単な問題はごくわずか • ほとんどは、NP完全(NP-complete)、あるいは NP困難(NPcomplete)とよばれる難しい問題のクラスに属する • （多項式時間のアルゴリズムが存在しないだろうと言われている）問題の帰着 • 問題 A と問題 B があり、問題 B を変換すると、問題 A になる、あるいは、問題 A を解くと、＋αの時間で問題 B が解けるとする • n 個の数の中から、k 番目に大きな要素を見つける問題  ソートすると、O(n) 時間で見つかる  この問題は、ソートをつかって解ける • こういった、問題 B を問題 A に変換すること、あるいは問題 A を解くことで解く方法を、「問題 B を問題 A に帰着する」という • このとき、問題 B のほうが、＋α以上の時間がかかる限り、問題 A より易しい • 入出力に必ず O(n) 時間かかるので、上の例だと、ソートのほうが難しい充足可能性問題がNP困難 • 多項式時間、指数時間かかりそうな問題の中で、他の問題が多項式時間で帰着できる、最も難しい問題がNP困難問題 • 充足可能性問題は、変数 x1,…,xn からなる論理式を満たす解があるかどうかを判定する問題  変形して、連言標準形にしてあると思ってよい • コンピュータの回路を論理式で記述できるので、ということ • 非決定性チューリングマシンといって、指数個の可能性を平行して調べられるコンピュータの動作を論理式でシミュレートできる • 組合せ的な難しい問題が、このマシンなら多項式時間で解ける • その問題たちの中で、充足可能性問題は一番難しいことになる（通常のコンピュータなら、指数時間かかりそう）難しさの証拠 • 充足可能性問題は、難しい問題のランドマーク  この問題より難しければ、難しそう • 充足可能性問題より難しい問題を、NP困難問題とよぶ • 非決定性チューリングマシンで、多項式時間で解ける問題をNP 問題とよぶ • NPの問題で、 NP困難問題であるものをNP完全問題とよぶ • NP問題の中で、最も難しい問題の部分がNP完全問題近似解法 • NP完全問題は、ある意味、総当たりの解法を使わないと最適解が求められない • そこで、時間をかけて最適解を求めるのではなく、短時間でそれなりに良い解を見つける、という解法が近似解法 • 精度保障があるもの：近似解法（得られる解が、必ず、最適解の2倍以内、など） • 精度保証がないもの：発見的解法（メタ･ヒューリスティック）（精度保証はないが、実験的に良い解が得られることがわかっているもの、あるいはそう思われるもの） • 問題固有の性質を使うので、解法が細分化されている（スケジューリング用、配送計画用、など）組合せ最適化の近似解法 • 様々な手法がある最もよく使われる方法： 1. 整数条件を線形緩和する xi ∈ { 0,1 }  0 ≦ xi ≦ 1 （解集合が広くなるので、最適解は悪くはならない） 2. 得られた問題の最適解を見つける（一般に小数解。整数解なら元問題の最適解） 3. 得られた最適解を、何かしらのルールで整数に丸める（実行不能にならないように丸める）最大独立集合問題 • グラフ G=(V,E) の独立集合（または安定集合）： G の頂点集合で、全ての頂点の組が枝で結ばれていないもの • G の最大独立集合： G の独立集合で、頂点数が最大のもの • 最大独立集合を求める問題は NP-hard • 各頂点に変数を割り当て、独立集合に含まれるとき１になる、として整数計画で定式化すると、枝の両端点が独立集合に含まれない、という制約から、以下の問題が得られる max. ∑ xi s.t. xi + xj ≦ 1 xi ∈ {0,1} for ∀(i,j) ∈ E 最大独立集合のLPによる近似 • 最大独立集合問題の整数計画の、整数条件を緩和する max. ∑ xi s.t. xi + xj ≦ 1 0 ≦ xi ≦ 1 for ∀(i,j) ∈ E • 全ての変数に1/2 を割当てたものが実行可能解  それほど精度は良くないが、一応、上限は得られる • 各枝の片方だけが１になるように最適解を丸めると、独立集合が得られる • ２部グラフの場合は最適解になる工夫の仕方そのままではうまく精度保証ができないことが多い各問題の構造に大きく影響されるので、個別に上手に解法を設計する必要がある 1. 緩和問題を作る緩和の仕方を工夫して（余計な制約を入れて）なるべく元問題に近い（または性質の良い）緩和問題を作る 2. 得られた問題の最適解を見つける整数条件を残し、線形計画以外の方法を使うこともある 3. 得られた最適解を、何かしらのルールで整数に丸める精度を保証するため、いろいろなテクニックを使う最大独立集合のLP近似の改良 • G の部分グラフで、任意の頂点の組が枝で結ばれているものをクリークとよぶ  独立集合の補グラフ • クリークの中からは、独立集合の頂点は１つしか選べない  制約式が作れる max. ∑ xi s.t. ∑xi∈S xi ≦ 1 0 ≦ xi ≦ 1 for ∀クリーク S • 全てのクリークを求めると指数個あるので、適当なところだけを選んで、制約式にする最大独立集合のLP近似の改良 (2) • LPの解を丸めるときに、次数の小さい頂点から優先的に選ぶようにすると、効率が良くなる  星型のグラフが最悪（最良）のケース • 解の精度がもう少し良くなる分枝限定法 • 列挙問題を（変数を1つずつ固定して）いくつかに分割し、それぞれの最適解を求め、元の問題の最適解を求めるアルゴリズム • 基本的にどんな組合せ最適化問題にも使える • 通常、指数時間かかるが、厳密に最適解を求めることができる v1 v1, v2 v1 v1, v2 v1, v2 v1, v2 上界と下界による限定操作 • 分子限定法は、計算を速くするために枝刈りを行う（これ以上進んでも最適解がある見込みのないところは省略する） • 最小化問題を考える • これから解こうとしている部分問題の解の下界が、今までに見つけた v1, v2 解（暫定解）よりも大きかったら、見込みなし v1 v1 v1, v2 v1, v2 v1, v2 巡回セールスマン問題 • セールスマンがお客のいる都市を回って帰ってくる • どういうルートで回ると、移動距離が最短になるだろうか問題の難度と解法 • NP-hard 問題である • 厳密解法：分枝限定法、分枝切除法など • 近似解法はNP-Hard • 発見的解法： 2-opt、挿入距離が三角不等式を満たすと、いろいろなことが言える • 近似解法： 3/2近似アルゴリズム、ε近似アルゴリズム（FPTAS） • 発見的解法：リン・カーニハン近傍探索 01整数計画として定式化 • 決めるのは、都市の順番  順番を決めるように定式化するのは困難 • ルートに入る枝を選ぶ問題、として定式化  都市 i の次に都市 j に行くとき、xij = 1 とする最小化 Σwijxij 制約 Σi xij = 1 、 Σj xij = 1 (入る枝＆出る枝＝１） Σi∈X, j∈V＼X xij ≧ 2 ( X が島にならない) xij ∈ { 0,1 } • またまた制約式が指数本あるハミルトンサイクルが解ける • 近似解法はNP-Hard：巡回セールスマン問題の近似解法でハミルトンサイクル問題が解けるハミルトンサイクル問題：与えられたグラフに、全ての頂点を通る（単純な）サイクルは存在するか？問題の変換移動時間をこのように設定しましょう • 頂点の間に辺がある 1 • 頂点の間に辺がない＋∞ ハミルトンサイクル‥ ‥ ‥ ‥ ‥ ‥ ハミルトンサイクルではない‥ ‥ ‥ 有限の長さ長さ無限大問題の変換 (2) • 頂点の間に枝がある • 頂点の間に枝がない 1 ＋∞ 経路がハミルトンサイクル  枝だけ通る  有限の長さ経路がハミルトンサイクルではない  枝ではない所を通る  長さ無限大近似解から元問題の解を得る • 近似アルゴリズムがあるとする近似解の長さは有限だよ  有限の長さのサイクルがある  ハミルトンサイクルがある近似解の長さは無限だよ  最適解の長さは + ∞/n 以上  ハミルトンサイクルはない NP-hard問題が解ける  NP-hard問題より同じか難しい難しさの比較 • 巡回セールスマン問題の近似アルゴリズムがあれば、ハミルトンサイクル問題が解ける  巡回セールスマン問題のほうが難しい • ハミルトンサイクル問題はNP-complete  巡回セールスマン問題もNP-complete まとめ • 基本的な組合せ最適化問題の紹介 • NP完全問題と帰着の解説 • 最小木問題のクラスカル法とプリム法の解説 • 巡回セールスマン問題が、近似ですら NP-complete 問題である証明 • 巡回セールスマン問題の2近似アルゴリズム • 巡回セールスマン問題のセービング法