組み合わせ計画
言葉の意味と定義
組み合わせ計画
有限個の元からなる実行可能領域の中から目的関数を最小化する最適解を求める問題。
貪欲法
解を求める途中のステップで、その時点で最も最適だと思われる解を常に選択。
最小全域木
以下参照。
全域木 - Wikipedia
貪欲法を用いた、最小全域木の解法がクラスカル法。
クラスカル法 - Wikipedia
だいたいの流れは以下の通り。
- グラフのすべての頂点一個だけからなる木の集合Fをつくる。（FはforestのF、木の集合を森と言うからだろうと思う）
- グラフの全ての辺を含む集合Eを生成する．
- Eから重みが最小の辺eを取り出し，Eから除外する．★
- その辺eと繋がっている二つの頂点x, yについて考える、x,yが集合Fのなかで別々の木に属しているならば，集合Fの中のx,yの属する木をeで連結してひとつの木にまとめる。x,yが集合Fのなかで別々の木に属しているのではないのなら放置。
- Eが空集合なら終了、そうじゃないときは★へもどる。
最終的に森Fが一つの木となりそれが最小全域木となる．常に重みが最小のものを選ぶ点が”貪欲”である。
分枝限定法
分枝限定法 - Wikipedia
wikiをみるよりも、実際に計算した方が分かりやすい。NP困難問題に対して、すべての場合を計算せずに最適解を求めるために利用されることが多い。
例:ナップザック問題
ナップサック問題 - Wikipedia
問題を定式化すると、
と書くことにする。つまり、a_i は要素iのサイズ、bはナップザックのサイズ、c_i は要素iの価値であり、ナップザックに詰め込めるもののすべての価値の和を最大化するのが問題。
