---

整数計画法について

• 離散的な最適化
• 積分表現より、Σで表されることが多い
• 組合せ最適化とも呼ばれる

\[\max \sum_{i} c_i x_i \\ s.t. \sum_{i} a_{ji} x_i \leq b_{j}, x_i \geq 0\]

応用

• 雑誌購読計画問題
• ナップサック問題
• 文章要約問題
• 商品推薦問題

グラフ

• 線形順序付け問題
  • 2D状に表現されたグラフを1Dのリスト(ポインタ付き)で表現する

グラフの解き方

• 最短路問題
  • 動的計画法のようにその時最もコストが安いところを選択してたどる解き方
• 最小全域木問題
  • 木構造をブロックに分割して表現する
• 集合被覆問題
  • ある集合UのサブセットSがあったとき、SでどのようにUを表現するか
  • NP困難である
  • 参考

貪欲法
各段階で最も評価が良いものを選ぶ手法を貪欲法

• 最小全域木問題
  • 木を分割する際にクラスカル法, プリム法で分割すること

動的計画法

• 二次元かそれ以上のtableを作ってメモのように必要な箇所を書き込みながら解く方法
• ナップサック問題等がこの問題を解くときの例である
• コードで解いたときの記録
• spreadsheetで作成したDPの例