システム制御情報学会 マルチメディアライブラリー(DVD教材)
組合せ最適化問題に対する実践的解法を中心に解説した講演を収録したDVD教材です. とくに,3部構成のうち第1部は予備知識が無くても分かるように 数式を用いない平易な説明を心がけました.
【タイトル】 組合せ最適化: 実践的解法を中心として

【講師】 柳浦 睦憲 (名古屋大学大学院情報科学研究科)

【概要】
 組合せ最適化問題は,生産・流通等におけるコスト削減や問題解決など,重要な局面に
おいて様々な形で現れ,その重要性は広く認知されています.本講義では,組合せ最適化
問題に対する実践的解法を中心に解説します.
 講義は3部構成で,第1部は組合せ最適化に関する種々の話題を,身近な題材を用いつ
つ,数式を用いずに分かりやすく紹介する入門編です.
 第2部では,組合せ最適化問題に対する実践的解法を紹介します.まず,厳密解法の中
から動的計画法と分枝限定法を解説した後,近似解法の基本戦略として欲張り法,局所探
索法をとりあげ,さらに,アニーリング法,タブー探索法,遺伝アルゴリズムなどに代表
されるメタ戦略の話題にも言及します.
 第3部では,メタ戦略による汎用解法構築の試みを説明したのち,その中からとくに集
合被覆問題に焦点を当て,解法のアイデアと集合被覆問題を介して解くことのできる種々
の応用問題を紹介します.

【章立て】
・第1部  組合せ最適化入門: 身近な話題を中心に
 - 組合せ最適化問題と列挙の難しさ
 - 近似解を求める方法
 - 最適解を求める方法
 - 効率的に最適解を計算できる問題

・第2部  組合せ最適化問題に対する実践的解法
 - 組合せ最適化問題---一般的定義,代表的な問題
 - アルゴリズムの計算量とクラスNP
 - 厳密解法---動的計画法,分枝限定法
 - 近似解法
  -- 基本戦略---欲張り法,局所探索法
  -- メタ戦略---アニーリング法,タブー探索法,遺伝アルゴリズムなど
  -- ハイブリッドメタ戦略

・第3部  メタ戦略による汎用解法: 標準問題によるアプローチ
 - メタ戦略と標準問題によるアプローチ
 - 集合被覆問題に対するアルゴリズム
 - 集合被覆問題の応用例
  -- 集配計画問題
  -- 正方形カバー問題
  -- ドビー織機の綜絖枠枚数最小化

【講義時間】 合計約5時間

【価格】   30,000円+税

【メディア】 DVD(1枚) 表紙裏表紙中身

【販売について】
システム制御情報学会より発売中です.詳しくは学会のウェブページをご覧ください.

・システム制御情報学会のページシステム制御情報学会のマルチメディアライブラリーのページ
 (あるいはシステム制御情報学会のページの左のメニューより「刊行物」→「マルチメディアライブラリー」とたどる)

【練習問題】
DVDの内容の理解度を確認するための練習問題を用意しました.ご利用下さい.

Mutsunori YAGIURA