科目ナンバー

SG-IG5-8C21

履修条件・関連科目等

アルゴリズムとデータ構造、プログラミング、最適化法の基本知識があることが望ましい。

授業で使用する言語

日本語

授業で使用する言語（その他の言語）

授業の概要

巡回セールスマン問題を主な題材として、難しい最適化問題に対する様々なアルゴリズムの設計法を取り扱う。理論的な精度保証はないが、多くの問題に対して実用上有用である発見的解法，局所探索法およびメタ戦略を中心に学習する。

科目目的

難しい最適化問題に対する様々な対処法を、巡回セールスマン問題を通して学ぶ。

到達目標

発見的解法、局所探索法、メタ戦略を理解し、巡回セールスマン問題に対する具体的なアルゴリズムの設計とプログラムの実装ができるようになることを目標とする。

授業計画と内容

（１）巡回セールスマン問題とその周辺
（２）NP困難問題に対するアルゴリズム設計
（３）発見的解法の基礎
（４）発見的解法の効率化
（５）発見的解法の実装
（６）発見的解法についてのまとめ
（７）局所探索法の基礎
（８）局所探索法の効率化
（９）局所探索法の実装
（１０）局所探索法についてのまとめ
（１１）メタ戦略の基礎
（１２）様々なメタ戦略
（１３）メタ戦略の実装
（１４）メタ戦略についてのまとめ

授業時間外の学修の内容

授業終了後の課題提出／その他

授業時間外の学修の内容（その他の内容等）

学んだアルゴリズムのプログラムを組んで実行することで理解が深まる。

授業時間外の学修に必要な時間数／週

・毎週１回の授業が半期（前期または後期）または通年で完結するもの。１週間あたり４時間の学修を基本とします。
・毎週２回の授業が半期（前期または後期）で完結するもの。１週間あたり８時間の学修を基本とします。

成績評価の方法・基準

成績評価の方法・基準（備考）

課題や試験のフィードバック方法

授業時間内で講評・解説の時間を設ける／授業時間に限らず、manabaでフィードバックを行う

課題や試験のフィードバック方法（その他の内容等）

アクティブ・ラーニングの実施内容

ディスカッション、ディベート／プレゼンテーション／実習、フィールドワーク

アクティブ・ラーニングの実施内容（その他の内容等）

授業におけるICTの活用方法

その他

授業におけるICTの活用方法（その他の内容等）

必要に応じて、manaba、Webexミーティング、Google共有ドライブを用いて双方向型の学び及び自主学習支援を実施する。具体的にはその都度指示する。

実務経験のある教員による授業

いいえ

【実務経験有の場合】実務経験の内容

【実務経験有の場合】実務経験に関連する授業内容

テキスト・参考文献等

必要に応じて資料を配布する。参考書については授業中に紹介する。

その他特記事項

参考URL