情報工学総合演習 D-I 近似アルゴリズム 埼玉大学 理工学研究科 山田 敏規、 橋口 博樹、 堀山 貴史 埼玉大学 理工学研究科 山田 敏規、 橋口 博樹、 　堀山 貴史 2008/01/23

この課題で学ぶこと 問題のモデル化 重み付き集合被覆問題 (最適解を求めるのは、NP困難な問題) 集合被覆問題の近似解法 グリーディ法による近似 LP 緩和による近似 近似解法の評価

情報工学総合演習 D-I 近似アルゴリズム 2009/10/7 問題のモデル化

軌道探査の問題例 探査対象は、 13個の 惑星/小惑星 探査軌道は 軌道 1 ～ 軌道 47 各軌道には、 探査費用が かかる 探査対象 すべてを、 費用最小で 探査したい 惑星の写真: Courtesy NASA/JPL-Caltech http://photojournal.jpl.nasa.gov/jpegMod/PIA06890_modest.jpg より

重み付き集合被覆問題 軌道 1 : S1 = { e3, e4, e5, e6 } 探査コスト : c(S1) = 90 S1 90 e1 入力 : 探査対象の集合 U = { e1, e2, …, e9 } 探査軌道の集合 S = { S1, S2, …, S8 } コスト関数 c: S → Q+ (正の有理数)

重み付き集合被覆問題 軌道 1 : S1 = { e3, e4, e5, e6 } 探査コスト : c(S1) = 90 S7 S1 90 100 S1 90 S3 23 S4 30 e1 e2 e3 e4 e5 e7 S2 34 S5 e9 e8 e6 20 S8 S6 2 98 入力 : 探査対象の集合 U = { e1, e2, …, e9 } 探査軌道の集合 S = { S1, S2, …, S8 } コスト関数 c: S → Q+ (正の有理数)

重み付き集合被覆問題 S7 S1 90 S3 23 S4 30 e1 e2 e3 e4 e5 e7 S2 34 S5 e9 e8 e6 20 100 S1 90 S3 23 S4 30 e1 e2 e3 e4 e5 e7 S2 34 S5 e9 e8 e6 20 S8 S6 2 98 出力 : カバー C で、総コスト Σ c(Si) が最小となるもの Si ∊ C ∪ Si = U となるもの Si ∊ C

課題 課題 1 遊園地の問題例を、重み付き集合被覆問題として モデル化する。重み付き集合被覆問題の U や S, S1, S2, … および c がそれぞれ 何に対応するか説明しなさい。 課題 2 食玩集めの問題例を、辺被覆問題としてモデル化する。 辺被覆問題の頂点 v (∊ V) および e (∊ E) がそれぞれ 何に対応するか説明しなさい。 例 1 にならって、辺被覆問題の問題例を 1 つ作りなさい。

情報工学総合演習 D-I 近似アルゴリズム 2009/10/7 グリーディー法による近似

グリーディー法による近似 S7 S1 90 S3 23 S4 30 e1 e2 e3 e4 e5 e7 S2 34 S5 e9 e8 e6 100 S1 90 S3 23 S4 30 e1 e2 e3 e4 e5 e7 S2 34 S5 e9 e8 e6 20 S8 S6 2 98 アイデア: 探査対象 1 つあたりのコストが 最小の軌道から、 C に加えていく

作業 作業 1 作業 2 グリーディー法による近似アルゴリズムを実装しなさい。 問題例のフォーマットは自分で考え、その仕様を レポートに記載すること。 プログラムは、出力として、 解 (カバー C として選択したすべての Si の添字 i ) と その時のコストを表示すること。 作業 2 資料 p. 117, 118 の問題例を、作業 1 で実装した プログラムの入力フォーマットに従って ファイルに記述しなさい。 また、作業 1 で実装したプログラムでのそれぞれの 実行結果を示しなさい。

実装のヒント 実装に用いるプログラミング言語は、問わない C 言語で文字列を数値に変換するには… # include <stdlib.h> 関数 atoi ( ) や strtol ( ) が使える

情報工学総合演習 D-I 近似アルゴリズム 2009/10/7 L P 緩和による近似

0-1 整数計画問題 目的関数 制約条件 0 … 採用しない minimize Σ i = 1 c(Si) ・ xi m 1 … 採用する 0 … 採用しない 目的関数 minimize Σ i = 1 c(Si) ・ xi 制約条件 Σejを要素に持つSi xi ≧ 1 (j = 1, 2, …, n) xi ∊ { 0, 1 } ( i = 1, 2, …, m) m 採用した軌道の コストの総和 ej を通る軌道を 少なくとも 1 つ採用

線形計画問題への緩和 目的関数 制約条件 LP ソルバーで、この問題を解く → 最適解 x1, x2, …, xm は 実数解 LP : Linear Programming 線形計画問題への緩和 1 … 採用する 0 … 採用しない 目的関数 minimize Σ i = 1 c(Si) ・ xi 制約条件 Σejを要素に持つSi xi ≧ 1 ( j = 1, 2, …, n) xi ∊ { 0, 1 } ( i = 1, 2, …, m) 0 ≦ xi ≦ 1 m 採用した軌道の コストの総和 ej を通る軌道を 少なくとも 1 つ採用 LP ソルバーで、この問題を解く → 最適解 x1, x2, …, xm は 実数解 * * *

LP 緩和による近似 LP 緩和した線形計画問題を解き、 実数最適解 x1, x2, …, xm を得る fj … ej を要素に持つ集合 Si の個数 f … その最大値 x i ≧ 1/f なら 1 に丸め、 そうでないなら 0 に丸める ( i = 1, 2, …, m) * * * *

作業・課題 作業 3 作業 4 発展課題 1 LP 緩和による近似アルゴリズムを実装しなさい。 また、作業 2 の問題例について、それぞれの 実行結果を示しなさい。 作業 4 作業 2 の問題例それぞれに対して、グリーディー法 および LP 緩和による近似アルゴリズムの 近似率と計算時間を比較し、考察を述べなさい。 発展課題 1 重み付き集合被覆問題の問題例を、 ランダムに生成したり、自分で設計するなどして作成し、 n や m の増加にしたがって近似率や計算時間が どのように変化するか考察しなさい。

実装のヒント LP 緩和による近似アルゴリズムの動作を把握する。 資料 p. 121 ～ 123 をもとに、GLPK パッケージの サンプル プログラムをコンパイルして動作させる。 問題例 1 つを対象に、LP 緩和した問題を手で書く。 2 をもとに、3 の問題を解くプログラムを作る。 (実数最適解を得たら、f を計算し、1, 0 に丸める。) 問題例をファイルから読んで、 LP 緩和した問題を作るようにプログラムを改良する。

情報工学総合演習 D-I 近似アルゴリズム この文面は、TOKYO TECH OCW の利用 条件を参考にしました この教材のご利用について この教材は、以下に示す利用条件の下で、著作権者にわざわざ許諾を求めることなく、無償で自由にご利用いただけます。講義、自主学習はもちろん、翻訳、改変、再配布等を含めて自由にご利用ください。 非商業利用に限定 この教材は、翻訳や改変等を加えたものも含めて、著作権者の許諾を受けずに商業目的で利用することは、許可されていません。 著作権の帰属 この教材および教材中の図の著作権は、次ページ以降に示す著作者に帰属します。この教材、または翻訳や改変等を加えたものを公開される場合には、「本教材 (or 本資料) は http://www.al.ics. saitama-u.ac.jp/horiyama/OCW/ の教材です (or 教材を改変したものです」 との旨の著作権表示を明確に実施してください。なお、この教材に改変等を加えたものの著作権は、次ページ以降に示す著作者および改変等を加えた方に帰属します。 同一条件での頒布・再頒布 この教材、または翻訳や改変等を加えたものを頒布・再頒布する場合には、頒布・再頒布の形態を問わず、このページの利用条件に準拠して無償で自由に利用できるようにしてください。

この教材のご利用について 配布場所 http://www.al.ics.saitama-u.ac.jp/horiyama/OCW/ このファイルの著作者 堀山 貴史　2009-2011 horiyama@al.ics.saitama-u.ac.jp 改変等を加えられた場合は、お名前等を追加してください 図の著作者 p. 4 惑星の写真 NASA Jet Propulsion Laboratory California Institute of Technology その他 堀山 貴史