2024年度学院等開講科目情報理工学院数理・計算科学系

組合せアルゴリズム

開講元: 数理・計算科学系
担当教員: 澄田範奈 / 横井優 / 山下真
授業形態: 講義 (対面型)
メディア利用科目: -
曜日・時限 (講義室): 月5-6 (S4-201(S421)) / 木5-6 (S4-201(S421))
クラス: -
科目コード: MCS.T322
単位数: 200
開講時期: 2024年度
開講クォーター: 4Q
シラバス更新日: 2025年3月14日
使用言語: 日本語

シラバス

授業の目的（ねらい）、概要

本講義では代表的な組合せ最適化問題とその解法を解説する．現実問題は本質的な目的や制約を抽出することで最適化問題としてモデル化される．抽象化された最適化問題を効率良く解くことは現実に重要な課題であり，そのために問題のもつ特有の性質や構造の利用が必要になる．本講義では「組合せ最適化問題」にフォーカスし，代表的な問題とその性質を利用したアルゴリズムを解説する．さらに，組合せ構造とアルゴリズムに関する理論を説明する．

本講義のねらいは，様々な例を通して組合せ最適化問題の代表的な問題とそのアルゴリズムに関する知識と，アルゴリズムの性能を数学的に説明するための基礎的な概念を与えることである．

到達目標

本講義の目標は以下である．
1) 組合せ最適化問題の基礎的な問題を認識できる．
2) 基礎的な問題をアルゴリズムを用いて解くことができる．
3) アルゴリズムの性能を理論的に解析できる．

キーワード

組合せ最適化, アルゴリズム, モデル化, オンライン最適化, 動的計画法,

学生が身につける力

専門力
教養力
コミュニケーション力
展開力 (探究力又は設定力)
展開力 (実践力又は解決力)

授業の進め方

毎回ひとつの組合せ最適化問題に焦点を絞り，基本的なアルゴリズムを解説する．

授業計画・課題

	授業計画	課題
第1回	イントロダクション	評価基準などの説明
第2回	グラフ探索
第3回	最短路問題
第4回	最大流問題
第5回	最小費用流問題
第6回	二部グラフの最大マッチング問題
第7回	非二部グラフの最大マッチング問題
第8回	マトロイド
第9回	安定結婚問題
第10回	ナップサック問題と近似解法
第11回	ナップサック問題と動的計画法
第12回	巡回セールスマン問題
第13回	劣モジュラ関数最大化問題	期末レポート
第14回	オンライン問題

準備学修(事前学修・復習)等についての指示

学修効果を上げるため，教科書や配布資料等の該当箇所を参照し，「毎授業」授業内容に関する予習と復習（課題含む）をそれぞれ概ね100分を目安に行うこと。

教科書

教科書は指定しないが，以下の参考書を基に作成した講義資料を用いる．

参考書、講義資料等

B. Korte and J. Vygen, "Combinatorial Optimization: Theory and Algorithms", Springer, 2018.
A. Schrijver, "Combinatorial Optimization: Polyhedra and Efficiency", Springer, 2003.
繁野麻衣子，「ネットワーク最適化とアルゴリズム」，朝倉書店，2010．
河原吉伸，永野清仁，「劣モジュラ最適化と機械学習」，講談社，2015．

講義資料はT2SCHOLAにアップロードする．

成績評価の方法及び基準

主に期末レポートにより評価する．

履修の条件・注意事項

「数理最適化」を履修していることが望ましい．