組合せ最適化とアルゴリズム サポートページ

久保幹雄 著
共立出版 2000年

パワーポイントスライド集

授業の概要 PowerPoint

Part 1 グラフ・アルゴリズム・計算量
Part 1では,グラフ,アルゴリズム,計算量の理論の基礎について書かれています.

  1. グラフ理論-オイラー閉路と最小木-
    PowerPoint (新バージョン:練習問題を含む)
  2. グラフ理論-有向グラフと巡回セールスマン問題 –
    PowerPoint (新バージョン:練習問題を含む)  追加資料(2008年AO入試模擬講義)
  3. 計算量とアルゴリズム
    PowerPoint

Part 2 線形計画
Part 2では,線形計画を例題を通して解説しています.特に,双対問題の意味と(絶対に失敗しない)導出方法に力点を置いています.

  1. 線形計画
    PowerPoint練習問題 –PowerPoint
  2. 双対問題
    PowerPoint練習問題 –PowerPoint

Part 3 ネットワーク理論
Part 3では,最短路,最大流,最小費用流の3つの代表的なネットワーク問題に対するアルゴリズムを解説しています.特に,双対性によるアルゴリズムの自然な解釈に力点を置いています.

  1. 最短路
    PowerPoint
    補助資料 最短路問題をGurobiで解こう!
    PowerPoint
  2. 最大流
    PowerPoint
  3. 最小費用流
    PowerPoint 宿題

Part 4 組合せ最適化
Part 4では,組合せ最適化に関するトピックスを扱っています.授業では,適当なトピックスを選択すると良いでしょう.

  1. 分枝限定法
    PowerPoint
  2. 多面体的アプローチ
    PowerPoint
  3. Lagrange緩和
    PowerPoint
  4. 動的計画
    PowerPoint
  5. 主・双対法
    PowerPoint
  6. 実験的解析
    PowerPoint

誤植ならびに修正候補

  1. p.4  4行目:日本首相->日本の首相
  2. p.6 下から7行目:Euler閉路をもつ.->Euler閉路をもつ (図1.3).
  3. p.29 図2.1 の牛肉の使用可能量 20 -> 30
  4. p.38 4行目:基底変数から->基底変数を
  5. p. 52 2行目:数式内  +7s2 -> -7s2
  6. p.73 表3.3のk=5の点3の値:4 → 6,同様に同ページの下から4行目:y3(5)=4 → y3(5)=6
  7. p.85 図3.12の修正:
    枝(s,2)の容量:6 → 8,同図の枝(1,t)の容量:7 → 8
  8. p.92 図3.16が例題と違う問題になっているので,以下のように修正:
    p.92 図3.16(a)~(f)の枝(s,2)の容量:6 → 8,同図(a)~(f)の枝(1,t)の容量:7 → 8
    p.92 図3.16(a)のカット容量:5+6=11 → 5+8=13
    p.92 図3.16(c)のカット容量:7+6=13 → 8+2+7=17(これも間違いです.8+8=16が正しい.)
    p.92 図3.16(d)のカット容量:7+5=12 → 8+7=15(これ間違いです.8+5=13が正しい.)
    p.92 図3.16(f)のカット容量:7+6=13 → 8+6=14
  9. p.131 下から3行目:仕様計算機->使用計算機
  10. p.151 5行目:GA Lib -> GA Lib. (省略形なのでピリオドを入れる.)
  11. p.157 5行目から:「1つの問題例ごとに一度だけ事前処理を行えば良い場合があるが,...」の部分: ちょっと分かりにくいのですが,たとえば巡回セールスマン問題の場合には,距離行列を事前に作成しておいて,それから構築法や改善法を行うことを意味します.
    ————————-以下第2刷の修正
  12.  p.7 下から2行目:盤がn回のときの->盤がn枚のときの
  13. p.33 下から5行目:直線上の両端は端点である -> 線分の両端は端点である
  14. p.69 Bellman-Ford法の3行目から7行目を以下のように変更(改訂後も5行目が直っていない)3    yw(k+1):=yw(k) ,∀w ∈V
    4    for all vw ∈E  do
    5        if  yv(k)+cvw < yw(k+1)  then 
    6                yw(k+1) :=yv(k)+cvw
  15. p.73 Bellman-Ford法(完全版) の4行目から9行目を以下のように変更(改訂後も6行目が直っていない)4    yw(k+1):=yw(k) ,∀w ∈V
    5    for all vw ∈E  do
    6        if  yv(k)+cvw < yw(k+1)  then 
    7                yw(k+1) :=yv(k)+cvw
      8               prev(w) := v
  16. (第1版の訂正が違っていました.)
    p.92 図 3.16(c)のカット容量:8+8=16
    p.92 図 3.16(d)のカット容量:8+5=13
  17. p.129 図 4.12 で、上から6行目 4 0 0 16 19 32 35 42 47 -> 4 0 0 16 19 32 35 39 44 (最後の2箇所が間違い)
  18.  p.130 下から2行目:の中の最小のものである.-> の中の最大のものである.
  19.  p.131 2行目の式: =min …k=2,…,n -> =max … k=1,….,n
    ————————-以下第3刷の修正
  20. p.37 7行目:(0,0,60,0,-30) という座標->(0,0,60,0,0,-30) という座標
  21. p.57 下から7行目:-4,-7,-9の符号を反転-> -4,-7,-19の符号を反転
  22. p.89 図 3.14の右下の図:sから2への枝の残余容量が1,2からsへの枝の残余容量が7
  23. p.90 図 3.15:すべての図の点1の下の点の番号を点2にする.
  24. p.101 下から2行目:枝vw の費用c’wvは ->枝vw の費用c’vw
  25. p.102 2行目:枝wv の費用c’vwは ->枝wv の費用c’wv
  26. p.103 下から2行目:O(n^2 m^2 log n) -> O(n^2 m^3 log n)
  27. p.159 下から3行目:33: -> 36:
    ————————-以下第6刷の修正
  28. p. 39 14行目: x1+x2+x3=30 -> x3=30
  29. p. 41, 最終行:すべての基底変数,どの基底変数 ->すべての非基底変数,どの非基底変数
  30. p. 70 3行目:最適パスは s→2→1→r ->最適パスは s→2→1→t
  31. (8刷り)p. 69 3行目:Bellman-Ford法内 5行目:y_w(k) -> y_w(k+1)