南山大学　シラバス検索用

指定	選	期間	春学期
単位	２	年次	3〜4
担当者	梅谷　俊治

他の科目との関連	OR概論I・II、線形計画法、非線形・整数計画法
他学科履修	可
副題	組合せ最適化　—巡回セールスマン問題を中心として—
講義内容	現実社会に現れる多くの問題は、組合せ最適化問題に定式化できるが、これらほとんどの問題に対して、現実的な計算時間で厳密解を求めることが非常に困難であることが、計算の複雑さの理論により知られている。組合せ最適化の分野では、これらの計算困難な問題に対する研究が盛んに行われ、これまで非常に多くの解法が提案されてきた。この講義では、代表的な組合せ最適化問題である巡回セールスマン問題（Traveling Salesman Problem）を通じて、計算困難な組合せ最適化問題に対する様々なアプローチを解説する。
講義計画	テキストおよび配布資料に従い説明する。・巡回セールスマン問題の紹介・計算の複雑さとNP困難問題・巡回セールスマン問題に対する近似解法・巡回セールスマン問題に対する発見的解法・メタヒューリスティクス・動的計画法・分枝限定法・配送計画問題
評価方法	期末レポートの成績を基に評価する。
テキスト	山本芳嗣、久保幹雄著「巡回セールスマン問題への招待」朝倉書店【その他】参考書　柳浦睦憲、茨木俊秀「組合せ最適化（メタ戦略を中心として）」朝倉書店
その他