アルゴリズム特論Ⅰ --- 近似アルゴリズム ---
近似アルゴリズムの基礎を学習する.
離散最適化問題の多くがNP困難と呼ばれる問題であり,
それらは,
現実的な時間で最適解を求めることが不可能であると思われている問題である.
そのような計算困難性に対処する一つの方法として,
最適解に近い解,「近似解」を求めるアルゴリズムが考案されてきた.
本講義では,
そのようなアルゴリズム論の一分野である近似アルゴリズムの基礎を学習する.
講義スケジュール
- 導入(近似アルゴリズムとは)
- カット問題
- 集合被覆問題
- 頂点被覆問題
- 独立頂点集合問題
- 巡回セールスマン問題
- ナップサック問題
- 近似スキーム1(PTAS:ナップサック問題)
- 近似スキーム2(FPTAS:ナップサック問題)
- 充足可能性問題1(貪欲法)
- 充足可能性問題2(乱択アルゴリズム)
- 充足可能性問題3(線形計画法の適用)
- 頂点彩色問題1(貪欲法)
- 頂点彩色問題2(半正定値計画法の適用)
Last Update: 02/April/2021