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

担当 :
勝部昭明 (大学院 理工学研究科 研究部 数理電子情報部門 教授)
重原孝臣 (大学院 理工学研究科 研究部 数理電子情報部門 教授)
池口徹 (大学院 理工学研究科 研究部 数理電子情報部門 教授)
長谷川有貴 (大学院 理工学研究科 研究部 数理電子情報部門 助手)

TA :
星野 聖 (大学院 理工学研究科 数理電子情報系専攻 M1)

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

概要:

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

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

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

1. テキストは演習ガイダンス時 (2006年10月6日) に配布されますした． こちら (2006年9月30日版)．

2. 列挙法解析用のデータは こちら
3. 構築法・改善法用，データの割当は こちら
4. 説明用PDFは こちら
5. ヒント，その他．
6. YaTeX の使い方

7. a0,a1サイズでのポスタの作り方