情報工学総合演習 D-I : 近似アルゴリズム埼玉大学理工学研究科山田敏規、橋口博樹、堀山貴史 1 この課題で学ぶこと  問題のモデル化  重み付き集合被覆問題 (最適解を求めるのは、NP困難な問題)  集合被覆問題の近似解法  グリーディ法による近似  LP 緩和による近似  近似解法の評価 2 問題のモデル化 3 軌道探査の問題例     探査対象は、 13個の惑星/小惑星探査軌道は軌道 1 ～軌道 47 各軌道には、探査費用がかかる探査対象すべてを、費用最小で探査したい惑星の写真: Courtesy NASA/JPL-Caltech http://photojournal.jpl.nasa.gov/jpegMod/PIA06890_modest.jpg より 4 重み付き集合被覆問題軌道 1 : S1 = { e3, e4, e5, e6 } 探査コスト : c(S1) = 90 S1 90 e1 e2 e9 e8 e3 e4 e5 e7 e6 入力 : 探査対象の集合 U = { e1, e2, …, e9 } 探査軌道の集合 S = { S1, S2, …, S8 } コスト関数 c: S → Q+ (正の有理数) 5 重み付き集合被覆問題 S7 100 S1 90 23 S3 e1 軌道 1 : S1 = { e3, e4, e5, e6 } 探査コスト : c(S1) = 90 e2 S4 30 e3 e4 e5 e7 S2 34 e9 S8 e8 2 S5 20 e6 S6 98 入力 : 探査対象の集合 U = { e1, e2, …, e9 } 探査軌道の集合 S = { S1, S2, …, S8 } コスト関数 c: S → Q+ (正の有理数) 6 重み付き集合被覆問題 S7 100 S3 e1 S1 90 23 e2 S4 30 e3 e4 e5 e7 S2 34 e9 S8 e8 2 S5 20 e6 S6 98 出力 : カバー C で、総コスト ΣS ∊ C c(Si) が最小となるもの i ∪S ∊ C Si = U となるもの i 7 課題  課題 1   遊園地の問題例を、重み付き集合被覆問題としてモデル化する。重み付き集合被覆問題の U や S, S1, S2, … および c がそれぞれ何に対応するか説明しなさい。課題 2   食玩集めの問題例を、辺被覆問題としてモデル化する。辺被覆問題の頂点 v (∊ V) および e (∊ E) がそれぞれ何に対応するか説明しなさい。例 1 にならって、辺被覆問題の問題例を 1 つ作りなさい。 8 グリーディー法による近似 9 グリーディー法による近似 S7 100 S3 e1 S1 90 23 e2 S4 30 e3 e4 e5 e7 S2 34 e9 S8 e8 2 S5 20 e6 S6 98 アイデア: 探査対象 1 つあたりのコストが最小の軌道から、 C に加えていく 10 作業  作業 1     グリーディー法による近似アルゴリズムを実装しなさい。問題例のフォーマットは自分で考え、その仕様をレポートに記載すること。プログラムは、出力として、解 (カバー C として選択したすべての Si の添字 i ) とその時のコストを表示すること。作業 2   資料 p. 117, 118 の問題例を、作業 1 で実装したプログラムの入力フォーマットに従ってファイルに記述しなさい。また、作業 1 で実装したプログラムでのそれぞれの実行結果を示しなさい。 11 実装のヒント   実装に用いるプログラミング言語は、問わない C 言語で文字列を数値に変換するには…  # include <stdlib.h>  関数 atoi ( ) や strtol ( ) が使える 12 L P 緩和による近似 13  0-1 整数計画問題 1 … 採用する目的関数 0 … 採用しない   m minimize Σ i = 1 c(Si) ・ xi 採用した軌道のコストの総和制約条件   Σe を要素に持つS xi ≧ 1 (j = 1, 2, …, n) j i xi ∊ { 0, 1 } ( i = 1, 2, …, m) ej を通る軌道を少なくとも 1 つ採用 14 LP : Linear Programming  線形計画問題への緩和 1 … 採用する目的関数 0 … 採用しない   m minimize Σ i = 1 c(Si) ・ xi 採用した軌道のコストの総和制約条件  Σe を要素に持つS xi ≧ 1 ( j = 1, 2, …, n) j i  xi ∊ { 0, 1 }  0 ≦ xi ≦ 1 ( i = 1, 2, …, m) ej を通る軌道を少なくとも 1 つ採用 LP ソルバーで、この問題を解く * は実数解 → 最適解 x*1, x*2, …, xm 15 LP 緩和による近似    LP 緩和した線形計画問題を解き、 * , …, x * を得る実数最適解 x*1, x2 m fj … ej を要素に持つ集合 Si の個数 f … その最大値 x *i ≧ 1/f なら 1 に丸め、そうでないなら 0 に丸める ( i = 1, 2, …, m) 16 作業・課題  作業 3    作業 4   LP 緩和による近似アルゴリズムを実装しなさい。また、作業 2 の問題例について、それぞれの実行結果を示しなさい。作業 2 の問題例それぞれに対して、グリーディー法および LP 緩和による近似アルゴリズムの近似率と計算時間を比較し、考察を述べなさい。発展課題 1  重み付き集合被覆問題の問題例を、ランダムに生成したり、自分で設計するなどして作成し、 n や m の増加にしたがって近似率や計算時間がどのように変化するか考察しなさい。 17 実装のヒント 1. LP 緩和による近似アルゴリズムの動作を把握する。 2. 資料 p. 121 ～ 123 をもとに、GLPK パッケージのサンプルプログラムをコンパイルして動作させる。 3. 問題例 1 つを対象に、LP 緩和した問題を手で書く。 4. 2 をもとに、3 の問題を解くプログラムを作る。 (実数最適解を得たら、f を計算し、1, 0 に丸める。) 5. 問題例をファイルから読んで、 LP 緩和した問題を作るようにプログラムを改良する。 18 19 この教材のご利用について     この文面は、TOKYO TECH OCW の利用条件を参考にしましたこの教材は、以下に示す利用条件の下で、著作権者にわざわざ許諾を求めることなく、無償で自由にご利用いただけます。講義、自主学習はもちろん、翻訳、改変、再配布等を含めて自由にご利用ください。非商業利用に限定  この教材は、翻訳や改変等を加えたものも含めて、著作権者の許諾を受けずに商業目的で利用することは、許可されていません。著作権の帰属  この教材および教材中の図の著作権は、次ページ以降に示す著作者に帰属します。この教材、または翻訳や改変等を加えたものを公開される場合には、「本教材 (or 本資料) は http://www.al.ics. saitama-u.ac.jp/horiyama/OCW/ の教材です (or 教材を改変したものです」との旨の著作権表示を明確に実施してください。なお、この教材に改変等を加えたものの著作権は、次ページ以降に示す著作者および改変等を加えた方に帰属します。同一条件での頒布・再頒布  この教材、または翻訳や改変等を加えたものを頒布・再頒布する場合には、頒布・再頒布の形態を問わず、このページの利用条件20 この教材のご利用について  配布場所  http://www.al.ics.saitama-u.ac.jp/horiyama/OCW/  このファイルの著作者  堀山貴史 2009-2011 [email protected]  改変等を加えられた場合は、お名前等を追加してください図の著作者  p. 4 惑星の写真  NASA Jet Propulsion Laboratory California Institute of Technology  その他  堀山貴史  21