情報工学総合演習 課題 B1
組み合わせ最適化 2007

担当:
重原 孝臣 (大学院 理工学研究科 研究部 数理電子情報部門 教授)
池口 徹 (大学院 理工学研究科 研究部 数理電子情報部門 教授)
桑島 豊 (大学院 理工学研究科 研究部 数理電子情報部門 助教)

TA:
松浦 隆文 (大学院 理工学研究科 理工学専攻 数理電子情報コース D1)
星野 聖 (大学院 理工学研究科 数理電子情報系専攻 情報システム工学コース M2)

時間: 後期，金曜日，1〜10限＠情報システム工学科端末演習室

概要:

本課題では， 工学において頻繁に出現する組み合わせ最適化問題 (combinatorial optimization problem) の中でも， 特に有名な巡回セールスマン問題を対象として，

• 列挙法のプログラムを作成し， 計算量の組み合わせ爆発を体験する．
• 基本的な近似解法の一つである 2opt 法のプログラムを作成し， 2opt 法の性能を統計的に解析する．

尚，本実験課題のサポートページ (http://www.nls.ics.saitama-u.ac.jp/~tohru/Lectures/ からアクセス) も用意しています． 適宜参考にして下さい．

1. テキスト は， 演習ガイダンス時 (2007年10月05日) に配布されました． (2007年9月30日版)．
2. 列挙法解析用のデータ
3. 構築法・改善法用のデータの割当
4. 説明用PDF
5. ヒント，その他．
6. YaTeX の使い方
7. a0,a1サイズでのポスタの作り方