南山大学　シラバス検索用

指定	選	期間	秋学期
単位	２	年次	新：3 旧：3
担当者	梅谷　俊治

他の科目との関連	OR概論I・II、線形計画法、非線形・整数計画法
他学科履修	可
副題	組合せ最適化　—巡回セールスマン問題を中心として—
講義内容	現実社会に現れる多くの問題は、組合せ最適化問題に定式化できるが、これらほとんどの問題に対して、現実的な計算時間で厳密解を求めることが非常に困難であることが、計算の複雑さの理論により知られている。組合せ最適化の分野では、これらの計算困難な問題に対する研究が盛んに行われ、これまで非常に多くの解法が提案されてきた。この講義では、代表的な組合せ最適化問題である巡回セールスマン問題（Traveling Salesman Problem）を通じて、計算困難な組合せ最適化問題に対する様々なアプローチを解説する。
講義計画	主にテキストに従い。印の項目については配布プリントに従い説明する。・計算困難な組合せ最適化問題・巡回セールスマン問題・計算量の理論とNP完全問題・精度保証のある近似算法・動的計算法* ・メタヒューリスティクス（Metaheuristics）・分枝限定法（Branch and Cut）
評価方法	授業内で出す課題と期末レポートの成績を総合的に評価する。
テキスト	山本芳嗣、久保幹雄著「巡回セールスマン問題への招待」朝倉書店テキスト以外の内容についてはプリントを配布する。
その他