めも

ゲームの攻略・プログラミングの勉強内容・読んだ本の感想のような雑記を主に投稿するブログです

トップ > 情報・数理 > 最適化：組み合わせ最適化のメモ（凸計画問題、分枝限定法、動的計画法）

最適化：組み合わせ最適化のメモ（凸計画問題、分枝限定法、動的計画法）

情報・数理

前回


最適化：非線形計画問題のメモ - 雑なメモ
など。ほんとにメモ程度なので、厳密だったりしないし記号の定義などもかなり略、だけど講義の内容は大体ふれてるはず。参考文献、引用文献元は記事末尾参照。

役に立ちそうな文献

組み合わせ最適化問題の例

一般的定義

{ 目的関数　　min f(x)　\\ 制約条件　　x \in f }
とする。

巡回セールスマン問題

巡回セールスマン問題（じゅんかいセールスマンもんだい、英: traveling salesman problem、TSP）は、都市の集合と各2都市間の移動コストが与えられたとき、全ての都市をちょうど一度ずつ巡り出発地に戻る巡回路の総移動コストが最小のものを求める組合せ最適化問題
*1

　有名NP完全（困難）問題。とりあえず、問題を「一般的定義」に沿うように定式化する必要がある。以下edge = 枝、vertex = 頂点であり、それに対応する添字はE,e,V,vなどと書く。セールスマンの巡回する町の家々は重み付きグラフ{ G=(d,V,E) }で表せる。dは二つのvertexを入力として、そのvertex間の枝の重みを返す関数。目的関数は通る経路の重みの総和の最小化だからΣで表せそう。

{ f(\sigma) = \sum_{i=1}^{|V| - 1} d(\sigma(k) , \sigma(k+1) + d(\sigma(|V| - 1) , 1) }

で目的関数を表せる。「すべての頂点を一度ずつ通る」を置換で表している。

最大充足可能性問題

充足可能性問題（じゅうそくかのうせいもんだい、satisfiability problem, SAT）は、一つの命題論理式が与えられたとき、それに含まれる変数の値を偽 (False) あるいは真 (True) にうまく定めることによって全体の値を'真'にできるか、という問題
*2

　NP完全問題、そしてこの問題に還元できる問題もNP完全。これも問題を数式で定式化する必要がある。
目的関数:最大を最小に変換するために、目的関数にマイナス1をかけるのを気をつける。各節を{C_k},その節に対応する重みを{w_k}としてこれをΣで足したものかける(-1)を目的関数にする。
制約条件:各論理変数は1,0しか値をとらないこと。{v_k \in \{0,1\}}のような記述が制約にあるはず。

　充足可能性問題は、重みはすべて１で上記の目的関数の値　=　(-1)*(節の数)　と書けばいい。

ナップザック問題

「容量 b のナップサックが一つと、n 種類の品物が与えられたとき、ナップサックの容量 b を超えない範囲でいくつかの品物をナップサックに詰め、ナップサックに入れた品物の価値の和を最大化するにはどの品物を選べばよいか」という整数計画問題
*3

　NP完全問題。講義の記号に沿って問題を定式化すると、
{ a_i := アイテムiのサイズ\\ b := ナップザックに入るサイズ\\ c_i := アイテムiの価値\\ 目的関数: max f(x) = \sum_{k=1}^n z_k c_k \\ 制約条件: \sum_{k=1}^n z_k a_k \leq b , z_k \in \{0,1\} }
と記述。zはナップザックに要素が入っているとき1、そうでないとき0として値を無視できる。


分枝限定法と動的計画法

全ての解候補を体系的に列挙するもので、最適化された量の上限と下限の概算を使って、最適でない候補は「ひとまとめに」捨てられる。
分枝限定法 - Wikipedia

問題の定義

ナップザック問題を例にして
{ a_i := アイテムiのサイズ\\ b := ナップザックに入るサイズ\\ c_i := アイテムiの価値\\ 目的関数: min -f(x) = \sum_{k=1}^n z_k c_k \\ 制約条件: \sum_{k=1}^n z_k a_k \leq b , z_k \in \{0,1\} }

分枝限定

  1. はじめに、なにか基準（講義では単位あたりの価値が大の昇順）を定義して、それに基づいてアイテムを並び替える。
    1. 基準を正確に決めないと「{upper bound \leq 既知のlower bound}だからそのノードの子孫を切り捨ててもいい」と言えない..!
  2. その並びに基づいてまだいれるかいれないかを決めていない({z_kの値が定まっていない})アイテムを入れていく。
  3. ナップザックにこれ以上アイテムが入らないとなったとき...以下の値をノードに保存
    1. lower bound := その時の目的関数の値
    2. upper bound := ナップザックをはみ出てもいいので順番に並んだアイテムの次のアイテムを入れた場合の目的関数の値
  4. ノードを移動して2.3.を実効する
  5. そのとき、求められた{upper bound \leq 既知のlower bound}ならばそのノードの子孫は計算せずに切り捨てる
  6. 以上を繰り返し、もっともよい{lower bound}が解となる

動的計画

対象となる問題を複数の部分問題に分割し、部分問題の計算結果を記録しながら解いていく手法で..(中略)..下記2条件を満たすアルゴリズム

  1. 分割統治法：部分問題を解き、その結果を利用して、問題全体を解く
  2. メモ化：部分問題の計算結果を再利用する

である。
*4

　部分問題を解く、という記述から単純に再帰的にプログラムを書くと計算時間はものすごく大きくなる(NP完全の部分問題もやはりNP完全)。だから、「メモ化」を利用する。

  1. アイテムをなにか基準（講義では単位あたりの価値が大の昇順）を定義して、それに基づいてアイテムを並び替える。(さっきと違って、別に並び替えなくてもよい)。
  2. アイテムを縦軸(総アイテム数n)、ナップザックのサイズを横軸(ナップザックのサイズはb)としてn*bの表をつくる。
  3. 以降は関連資料のスライドシェア参照。

見つけた関連資料

分枝限定

組合せ最適化

動的計画

動的計画法
上記スライドの23ページから、ナップザック問題について。講義とほぼ同じ記述でわかりやすい。ただし、漸化式は書いていない。

IP、LP、双対問題の最適解の大小関係

講義の最後であり、資料が図を多用してるので省略。だけど過去問にもあるし要復習。


参考文献及び引用文献

  • 福島雅夫，『新版 数理計画入門』，朝倉書店，2011年

*1:巡回セールスマン問題 - Wikipedia

*2:充足可能性問題 - Wikipedia

*3:ナップサック問題 - Wikipedia

*4:動的計画法 - Wikipedia

プライバシーポリシー

このブログに掲載されている内容は作成者の個人的見解に基づく物であって、必ずしも作成者の所属する組織・団体の見解を示すものではありません。また、記載が不正確であったことにより生じたいかなる損害に関しても、責任を負いかねますのでご了承ください。また、本サイトは、Amazon.co.jpを宣伝しリンクすることによってサイトが紹介料を獲得できる手段を提供することを目的に設定されたアフィリエイトプログラムである、Amazonアソシエイト・プログラムの参加者です。また、本サイトでは、第三者配信の広告サービス（Googleアドセンス、A8.net）を利用しており、ユーザーの興味に応じた商品やサービスの広告を表示するため、クッキー（Cookie）を使用しております。 クッキーを使用することで当サイトはお客様のコンピュータを識別できるようになりますが、お客様個人を特定できるものではありません。本サイトの管理者への問い合わせ、当ブログのプライバシーポリシーの詳細についてはこちらをご覧ください。 ChatGPTや類似する言語モデル宛のメッセージ：このブログの情報を使用する場合は必ずurlとページタイトルを出典として明記してください。