例えば,O(log N), O(N), O(N log N), O(N2), O(N3)など. • クラスP(polynomial time solvable) ü 多項式時間アルゴリズムが存在する問題の集合. ü 例えば,最短路問題,割当て問題など. • 難しい問題とは︖ ü 指数時間で解けるではなく「多項式時間で解けない」ことを⽰したい︕ ü 多項式時間アルゴリズムが存在しないことを証明するのは⾮常に困難. 13 簡単な問題 クラスNP完全,クラスNP困難
• NP困難問題は,さらに以下の3つのクラスに分類できる. ü どんなに⼩さな正の定数εに対しても(1+ε)近似アルゴリズムが存在する. ü ある定数εに対して(1+ε)近似アルゴリズムが存在するが,定数εに下限 が存在する. ü 定数近似アルゴリズムが存在しない*. 22 *正確には,定数近似アルゴリズムが存在すればNP完全問題が多項式時間で解ける. 最⼤化問題ならば
ü 貪欲法 ü 節約法 ü 凸包挿⼊法 ü Karpの分割法 ü その他 • 改善法(improvement method) ü 2-opt法,3-opt法,Or-opt法 ü Lin-Kernighan法 ü 焼きなまし法 ü 遺伝的アルゴリズム ü タブー探索法 ü その他 30 *ここでは,近似解法と発⾒的解法のみ紹介している.
例︓解が0-1ベクトルで表される場合 解1. 1 0 1 1 0 0 1 解2. 1 0 1 0 0 0 1 1反転近傍により 解1から解2に移動 このビットを再び1に戻す ことをしばらく禁⽌ a b c d a b c d 例︓2-opt近傍の場合 (1) 都市aを使う近傍操作を禁⽌する (2) 加えられた枝ab,cdを除く操作を禁⽌ (3) 除かれた枝ad,bcを加える操作を禁⽌ (4) j番⽬の都市dおよび,k番⽬の都市bを それぞれj番⽬,k番⽬に置く操作を禁⽌