組合せ最適化

－３．組合せ最適化（ Combinatorial Optimization ）－

　　組合せ最適化問題 P₀ を，定式化すれば以下のようになります．

目的関数： f(x)
制約条件： x ∈ S，ただし，S ⊂ X: S，X：有限個，または，可算無限個の要素を持つ離散集合

　　組合せ最適化問題における困難さの一つの原因は，非線形計画法のように微分的な情報（解の位置を予測するための情報）を利用できない点にあります．そこで，各 x に対して，順にその目的関数の値を調べていかざるを得ないことになります．

　　S が有限個の集合であれば，理論的には，すべての組合せを調べることによって解を求めることが可能です．しかし，S の要素の数や x の次元が大きくなるにつれ，その組合せの数は膨大になり，実際にはほとんど不可能になってしまいます．

　　組合せ最適化に対する手法では，如何にしてより少ない点（x）だけを調べて，最適解または最適解に近い結果を求めることができるかということ，つまり，探索の範囲を如何にして狭めるかということに重点が置かれます．

３．１分枝限定法

３．１．１分枝操作と限定操作

　　分枝限定法は，以下の 2 つの操作を繰り返すことによって，最適解（以下の説明では，最小値）を求めようとする方法です．

分枝操作：与えられた問題 P₀ を，それらを解くことで等価的に P₀ が解かれるような，つまり，
```
f(P₀) = min f(P_i)	　　f(P₀)，f(P_i)： 問題 P₀ 及び P_i の最適値			
```
となるような部分問題 P_i（i = 1，2，･･･）に分解する操作です．ただし，最適化問題 P_i は，以下に示すような問題とします．
```
目的関数： f(x)
制約条件： x ∈ S_i，　S_i ⊂ X_i，　X_i ⊂ X，　S = S ∩ (∪ X_i)，　S_i = S ∩ X_i			
```
限定操作：部分問題 P_i を何らかの方法で終端させます．つまり，それ以上部分問題に分割させないようにします．そのために，部分問題 P_i よりも制約条件が緩く，解きやすい問題を考えて P’_i と置きます．このような問題を緩和問題と呼び，問題 P_i の緩和問題 P’_i は，以下のように定義されます．
```
目的関数： g(x)
制約条件： x ∈ S’_i，　S_i ⊂ S’_i ⊂ X_i			
```
制約条件を緩めてありますので，一般に，x ∈ S_i となる x に対しては，g(x) ≦ f(x) のような結果になるはずです．緩和問題の性質を一般的に述べれば以下のようになり，これらの性質を利用して終端させることになります．
1. g(P’_i) ≦ f(P_i)　　g(P’_i)： P’_iの最適値（下界値と呼びます）
2. P’_i が許容解を持たなければ，P_i も持たない．
3. P’_i の目的関数に g(x) = f(x) を用いるとき，P’_i の最適解が P_i の許容解であれば，それは P_i の最適解でもある．
4. それまでに他の部分問題によってもとの問題 P₀ の許容解が求められており（その中の最小値を z とする），g(P’_i) ≧ z なる関係があるとき，部分問題 P_i，及び，それから生成される部分問題に対する許容解は z 以上の値を持つ．

３．１．２アルゴリズム

　　以上より，分枝限定法のアルゴリズムは以下のようになります．

初期設定：　A = {P₀},　z = ∞
A = φ ならば終了．
- z = ∞：問題 P₀ は解を持たない
- z < ∞： f(P₀) = z
集合 A の中から，部分問題 P_i を選択（選択方法に関しては後述）
もし，緩和問題 P’_i が解を持たなければ，
1. A = A - {P_i} として，2 へ戻る
そうでなけでば，
1. もし，g(P’_i) = f(P_i) として，P_i の最適値が得られたら，
  1. z = min {z, f(P_i)}， A = A - {P_i} として，2 へ戻る．
  そうでなければ
  1. もし，g(P’_i) ≧ z ならば
    
    A = A - {P_i} として，2 へ戻る．
    
    そうでなければ
    
    問題 P_i を，部分問題 P_i1，･･･，P_ik に分解し， A = (A - {P_i}) ∪ {P_i1，･･･，P_ik} として，2 へ戻る．

　　上記のアルゴリズムにおいて，3 番目の部分，つまり，どの部分問題 P_i を選ぶべきかは，計算の挙動に大きな影響を与えます．選び方としては，以下のような方法が考えられます．

発見的探索：　各部分問題 P_i に対し，f(P_i) の推定値 h(P_i) を何らかの方法で求めておき，h(P_i) が最小の部分問題を選ぶ方法です．良い h が見つかれば，非常に優れた方法です．
最良下界探索：　発見的探索における h(P_i) として，下界値 g(P’_i) を利用する方法です．
深さ優先探索：　深さが最大のものから，h あるいは g を基準に選択します．ある部分問題が分解されると，その分解された部分問題から選ばれることになります．この操作が，部分問題が終端されるまで繰り返され，終端されるとバックトラック（たどってきた道筋を戻る）します．
幅優先探索：　深さが最小のものから，h あるいは g を基準に選択します．

３．１．３分枝限定法の適用例

　　ここで，組合わせ最適化の例として，「0-1 ナップザック問題」という簡単な問題を取り上げます．「0-1 ナップザック問題」とは，容量が決まったナップザックに，何を選択して入れるのが最も効用が高いのかを決める問題であり，以下に示すように定式化できます．

0-1 ナップザック問題

　　　目的関数： f(x) = -Σc_jx_j　j = 1, ･･･, n　　　（符号を変え，最小値問題に変換してある）
　　　制約条件： Σa_jx_j ≦ b　x_j = 0 or 1

たとえば，最大利益を上げる投資先を決定する問題の場合，各変数は以下のようなものに相当します（カッコ内は，本来のナップザック問題）．
- n：投資先の数（品物の数）
- a_j： j 番目の計画の必要経費（ j 番目の品物の重さ）
- c_j： j 番目の計画の期待利益（ j 番目の品物の効用）
- b：投資金額の上限（ナップサックの容量）
- x_j： =0：投資先 j に投資しない（品物 j を入れない）
  　　=1：投資先 j に投資する（品物 j を入れる）
0-1 ナップザック問題に対する緩和問題　　x_j の値として連続値を許す

　　　目的関数： f(x) = -Σc_jx_j　j = 1, ･･･, n
　　　制約条件： Σa_jx_j ≦ b　0 ≦ x_j ≦ 1
0-1 ナップザック問題に対する緩和問題の解法
1. x_j を，c_j / a_j が小さい（最大値を求める場合は，大きい）順に優先度が高いとみなします．
2. 優先度順に x_j = 1 とおいていきます．ただし，x_j = 1 とおくと条件式が満たされなくなる場合には，その x_j を x_j = k(1 / a_j) （k は定数）とおき，制約条件の等式が成立するように k を決定します．それ以降の x_j については x_j = 0 とおきます．

［例3.1］ 問題 P₀

目的関数： f = -2x₁ - 5x₂ - 4x₃ - 3x₄

制約条件： x₁ + 3x₂ + 3x₃ + 3x₄ ≦ 6

　　以下に，上記の問題に対し，分枝限定法を用いて解く過程について説明します．なお，部分問題 P_i の選択方法としては，以下の解法例に示すように，深さ優先探索を使用するものとします．

［節点 0 ］問題 P₀

目的関数： f = -2x₁ - 5x₂ - 4x₃ - 3x₄
制約条件： x₁ + 3x₂ + 3x₃ + 3x₄ ≦ 6

の緩和問題を，変数の優先度，

x₁ → x₂ → x₃ → x₄

を利用して解くと，以下のようになります．

(x₁, x₂, x₃, x₄) = (1, 1, 2/3, 0) のとき g(x) = -29/3

明らかにこの解は，元の問題 P₀ の解ではありません（制約条件を満たしていない）ので，z = ∞ とおき，変数 x₃ の値により，2 つの部分問題 P₁ と P₂ （接点 1 と接点 2 ）に分解します．
［節点 1 ］問題 P₁　（x₃ = 0）

目的関数： f = -2x₁ - 5x₂ - 3x₄
制約条件： x₁ + 3x₂ + 3x₄ ≦ 6

を解くと，以下のようになります．

(x₁, x₂, x₃, x₄) = (1, 1, 0, 2/3) のとき g(x) = -9

この解も，元の問題 P₀ の解ではありませんので，変数 x₄ の値により，2 つの部分問題 P₃ と P₄ （接点 3 と接点 4 ）に分解します．
［節点 3 ］問題 P₃　（x₃ = 0, x₄ = 0）

目的関数： f = -2x₁ - 5x₂
制約条件： x₁ + 3x₂ ≦ 6

を解くと，以下のようになります．

(x₁, x₂, x₃, x₄) = (1, 1, 0, 0) のとき g(x) = -7

この解は，元の問題 P₀ の解となりますので，z = -7 とおき，終端とします．
［節点 4 ］問題 P₄　（x₃ = 0, x₄ = 1）

目的関数： f = -2x₁ - 5x₂ - 3
制約条件： x₁ + 3x₂ + 3 ≦ 6

を解くと，以下のようになります．

(x₁, x₂, x₃, x₄) = (1, 2/3, 0, 1) のとき g(x) = -25/3

この解は，元の問題 P₀ の解ではなく，かつ，g(x) ＜ z ですので，変数 x₂ の値により，2 つの部分問題 P₅ と P₆ （接点 5 と接点 6 ）に分解します．
［節点 5 ］問題 P₅　（x₂ = 0, x₃ = 0, x₄ = 1）

目的関数： f = -2x₁ - 3
制約条件： x₁ + 3 ≦ 6

を解くと，以下のようになります．

(x₁, x₂, x₃, x₄) = (1, 0, 0, 1) のとき g(x) = -5

この解は，元の問題 P₀ の解ですが，g(x) ≧ z ですので，終端とします．
［節点 6 ］問題 P₆　（x₂ = 1, x₃ = 0, x₄ = 1）

目的関数： f = -2x₁ - 5 - 3
制約条件： x₁ + 3 + 3 ≦ 6

を解くと，以下のようになります．

(x₁, x₂, x₃, x₄) = (0, 1, 0, 1) のとき g(x) = -8

この解は，元の問題 P₀ の解となります．さらに，g(x) ＜ z ですので，z = -8 とおき，終端とします．
［節点 2 ］問題 P₂　（x₃ = 1）

目的関数： f = -2x₁ - 5x₂ - 4 - 3x₄
制約条件： x₁ + 3x₂ + 3 + 3x₄ ≦ 6

を解くと，以下のようになります．

(x₁, x₂, x₃, x₄) = (1, 2/3, 1, 0) のとき g(x) = -28/3

この解は，元の問題 P₀ の解ではなく，かつ，g(x) ＜ z ですので，変数 x₂ の値により，2 つの部分問題 P₇ と P₈ （接点 7 と接点 8 ）に分解します．
［節点 7 ］問題 P₇　（x₂ = 0, x₃ = 1）

目的関数： f = -2x₁ - 4 - 3x₄
制約条件： x₁ + 3 + 3x₄ ≦ 6

を解くと，以下のようになります．

(x₁, x₂, x₃, x₄) = (1, 0, 1, 2/3) のとき g(x) = -8

この解は，元の問題 P₀ の解ではなく，かつ，g(x) ≧ z ですので，終端とします．
［節点 8 ］問題 P₈　（x₂ = 1, x₃ = 1）

目的関数： f = -2x₁ - 5 - 4 - 3x₄
制約条件： x₁ + 3 + 3 + 3x₄ ≦ 6

を解くと，以下のようになります．

(x₁, x₂, x₃, x₄) = (0, 1, 1, 0) のとき g(x) = -9

この解は，元の問題 P₀ の解であり，かつ，g(x) ＜ z ですので，z = -9 とおき，終端とします．

　　以上の結果，この問題に対する最適解は -9 となります．上に述べた手続きにおいては，問題 P₀ を含め 9 つの問題を解きました．しかし，同じ深さ優先探索を用いたとしても，もし，

P₀ → P₂ → P₈ → P₇ → P₁

の順に問題を解けば，問題 P₈ を解いた段階で z = -9 という結果が得られるため，問題 P₁ を分解する必要がなくなります．つまり，問題 P₃ ～ P₆ を解く必要がないわけです．このように，どの部分問題 P_i を選ぶべきかは，計算の挙動に大きな影響を与え，大規模な問題の場合は，選び方によって解を得られなくなることも珍しくありません．

３．２近似解法

　　いずれの方法を採用するにしろ，組合せ最適化問題の真の最適解を求めることは非常に困難である場合が多く存在します．そこで，以下に示すように，多くの近似解法が提案されています．

欲張り法　　目的関数値の良さを示す局所的評価に基づいて，可能解を直接構成していく方法です．

　　たとえば，「 0-1 ナップザック問題」において，c_j / a_j （目的関数の係数／制約条件の係数）を評価基準として，この値が小さい順に x = 1 と固定していき，制約条件のために x_j = 1 とできなくなると，以後，x = 0 とする方法がこれにあたります．

　　また，「最小木問題」（無向グラフの各枝の長さ d_ij が与えられているとき，全節点を連結する木で，枝の長さの和が最小のものを見つける問題）において，長さ最小の枝から始め，選ばれた枝の集合が閉路を形成しないという条件の下で，長さの小さいものから順に N-1 本（N は節点数）選ぶ方法も良く知られた方法です．
ランダム法　　解をランダムに何個か選び，発見された可能解の中で目的関数値が最小のものを選ぶ方法です．
反復改善法（逐次改善法）　　何らかの方法で得られた近似最適解に対して，その近傍，つまり少し変更を加えることで得られる他の解を調べ，改善できればそれに置き換えていく方法です．

　　例えば，TSP: Traveling Salesman Problem（巡回セールスマン問題：与えられた n 個の都市に対して，各都市を一度だけ訪れ，すべての都市を訪れる経路の内，最小の経路を見つける問題）において，まず，一つの巡回路 t を見つけます．その中の k 本の枝を入れ替えて得られる巡回路が，もとの巡回路より短ければそれに置き換える，という操作を改善が得られなくなるまで繰り返す方法です．下に示す図は，k = 2 の場合であり，枝 AD と CB を入れ替えた例です．　→　（ C/C++によるプログラム例　→　，なお，他の言語（ PHP，Ruby，Python，C#，VB ）によるプログラム例に関しては，「プログラミング言語の落とし穴」第 9 章の「逐次改善法（ TSP ）」をご覧ください．）
緩和法　　制約条件を緩和することで一つの解を求め，それに修正を加えて可能解を構成する方法です．
分割法　　与えられた問題をいくつかの部分問題に分解し，それぞれの解から，もとの問題の可能解を合成する方法です．

　　たとえば，TSP において，与えられた都市を複数のグループに分け，各グループ内の最適経路を見つけた後，全体の最適経路を合成する方法が相当します．　→　（ C/C++によるプログラム例　→　，なお，他の言語（ PHP，Ruby，Python，C#，VB ）によるプログラム例に関しては，「プログラミング言語の落とし穴」第 9 章の「分割法（ TSP ）」をご覧ください．）

３．３人工知能的手法

　　人工知能分野の問題には，組合せ最適化問題として扱えるものが多く存在します．囲碁，将棋等，ゲームの問題はもちろんですが，有限個の単語の中から，翻訳文として最も適切な単語の組合せを見つける，といった意味から，機械翻訳のようなものも一種の組合せ最適化問題であるといえます．

　　そこで，この節では，人工知能における探索の分野に関して簡単に説明します．

３．３．１状態空間による問題の表現

　　まず，問題の表現方法について述べます．問題を解く各段階における対象の有様や条件を状態（ State ）と呼びます．問題を解くということは，与えられた初期状態に，何らかの作用素（ Operator ）を適用して，目標状態（問題が解かれた状態）に持っていくこと，つまり，作用素の系列を見つけることに相当します．

　　例えば，8 パズルについて考えてみます．8 パズルとは，下の図に示すように，与えられた初期状態（左図）を，できるだけ少ない回数のコマ（数字の書かれたものであり，1 カ所だけコマが置かれていない場所がある）移動によって，目標状態（右図）に持っていくゲームです．この問題における作用素は，コマを移動することに相当します．

　　問題を解くことは，コマを移動する順番（作用素系列）を決めることになります．例えば，上の例では，以下に示すものが解になります．

　　初期状態からすべての作用素を適用することにより到達可能な状態の集合を状態空間と呼びます．問題を解くためには，状態空間内を探索し，最適解を見つければよいわけですが，膨大な空間であるため全空間を探索することが不可能である場合がほとんどです．そこで，有効な探索方法が問題になってきます．

　　状態空間を表現するのに，下に示すようなグラフがしばしば使用されます．グラフの各節点（ノード）は状態を表し，また，枝は作用素を表します．節点には状態（ s1 等），また，枝には作用素の種類とその作用素を適用する際のコスト（op1,3 等）を明記します．ただし，すべての作用素に対するコストが同じ場合は，コストの表記を省略します．また，右図のように，閉路のない連結グラフを木と呼びます．

３．３．２探索方法

縦型（深さ優先）探索　　最も最近に生成された，すなわち，最も深い節点を最初に展開（その節点から一つの作用素で移動可能な状態を羅列する）します．発見される経路は必ずしも最短ではありません．無限ループに陥ることや解が存在しない部分を無意味に探索することを避けるため，一般には，深さ限界を設け，ある深さになると後戻り（ back tracking ）するように設定します．アルゴリズムは以下のようになります．
1. A = {S₀₀} とします　　　S₀₀：初期状態，
2. A の中から，深さ d が最も深い状態 S_di を選択し，
  - A = A - {S_di}
  - d = S_di の深さ
  とします．
3. 状態 S_di が目標状態であれば終了します．さもなければ，
  1. 深さ d が，深さ限界であれば，b へ戻ります（後戻り）．さもなければ，
    
    状態 S_di を展開
    d = d + 1
    展開された状態 S_dj, ･･･を A に追加，つまり，A = A + {S_dj, ･･･}
    
    とし，b へ戻ります．
　　深さ制限を 3 とした場合は，下図の左図に示した順番で探索されることになります（この例では，同じ深さの場合は，図の左の節点から探索するものとする）．
横型（幅優先）探索　　深さが最も浅い節点から順に展開します．もし，解があるならば，最短の解系列を見つけます．そのアルゴリズムは以下のようになります．
1. A = {S₀₀} とします　　　S₀₀：初期状態，
2. A の中から，深さ d が最も浅い状態 S_di を選択し，
  - A = A - {S_di}
  - d = S_di の深さ
  とします．
3. 状態 S_di が目標状態であれば終了します．さもなければ，
  - 状態 S_di を展開
  - d = d + 1
  - 展開された状態 S_dj, ･･･を A に追加，つまり，A = A + {S_dj, ･･･}
  とし，b へ戻ります．
　　例えば，上図の右図に示した順番で探索されることになります（この例では，同じ深さの場合は，図の左の節点から探索するものとする）．
［縦型探索及び横型探索に対するプログラム例］

　　右図に対する縦型探索では，S -> C -> (F, G) -> B -> A -> (D, E) の順で探索していきます（括弧内の順序は任意）．S の次に，A または B を選択しても構いません．縦型探索を実現する最も簡単な方法は，スタックを利用する方法です．スタックの先頭要素（グラフのノード）を取り出し，それが目的とするノードでなければ，そのノードから到達できるノードをスタックに追加する，といった操作を繰り返すだけです．横型探索と基本的な流れは同じですが，キューとは異なり，スタックでは最も最近追加したノードが先頭に来るため縦型探索になります．C/C++ に対するプログラム例は，STL の stack クラスを利用し（ Java の場合は，Stack クラスを利用し），この方法で書かれています．このプログラムを実行すると以下に示すような結果が得られます．
S の追加 stack の状態：先頭： S，　要素数： 1 先頭 S を削除し，A, B, C を追加 stack の状態：先頭： C，　要素数： 3 先頭 C を削除し，F, G を追加 stack の状態：先頭： G，　要素数： 4 先頭 G を削除 stack の状態：先頭： F，　要素数： 3 先頭 F を削除 stack の状態：先頭： B，　要素数： 2 先頭 B を削除 stack の状態：先頭： A，　要素数： 1 先頭 A を削除し，D, E を追加 stack の状態：先頭： E，　要素数： 2 先頭 E を削除 stack の状態：先頭： D，　要素数： 1 先頭 D を削除 stack の状態：空です
　　先の図に対する横型探索では，S -> (A, B, C) -> (D, E, F, G) の順で探索していきます（括弧内の順序は任意）．横型探索を実現する最も簡単な方法は，キューを利用する方法です．キューの先頭要素（グラフのノード）を取り出し，それが目的とするノードでなければ，そのノードから到達できるノードをキューに追加する，といった操作を繰り返すだけです．縦型探索と基本的な流れは同じですが，スタックとは異なり，キューでは最初に追加したノードが先頭に来るため横型探索になります．プログラム例は，STL の queue クラスを利用し（ Java の場合は，ArrayDeque クラスを利用し），この方法で書かれています．このプログラムを実行すると以下に示すような結果が得られます．
S の追加 queue の状態：先頭及び最後尾： S S，　要素数： 1 先頭 S を削除し，A, B, C を追加 queue の状態：先頭及び最後尾： A C，　要素数： 3 先頭 A を削除し，D, E を追加 queue の状態：先頭及び最後尾： B E，　要素数： 4 先頭 B を削除 queue の状態：先頭及び最後尾： C E，　要素数： 3 先頭 C を削除し，F, G を追加 queue の状態：先頭及び最後尾： D G，　要素数： 4 先頭 D を削除 queue の状態：先頭及び最後尾： E G，　要素数： 3 先頭 E を削除 queue の状態：先頭及び最後尾： F G，　要素数： 2 先頭 F を削除 queue の状態：先頭及び最後尾： G G，　要素数： 1 先頭 G を削除 queue の状態：空です
知識を用いた探索（評価関数を使用した探索）　　今まで述べてきた方法は，基本的に，すべての状態を虱潰しに調べようとするものです．したがって，非常に簡単な問題を除いて，解が得られることはほとんど無いと思われます．

　　人間の場合であれば，何らかの知識を使用し，調べる必要のない状態を積極的に除いた空間で探索を行っています．そこで，この知識に対応する部分を，評価関数という関数で表現し，より効率的に解を求めようとするのが知識を用いた探索方法です．知識を用いた探索方法では，1 や 2 で述べたアルゴリズムの b において，最も評価関数の値が小さなものを選択することになります．

　　評価関数としては，例えば，以下のようなものが使用されます．

f(n) = e(n) + h(n)

f(n)：節点 n を通る最適な経路のコストの推定値
e(n)：初期節点から節点 n までの最適な経路のコストの推定値
h(n)：節点 n から目標節点に至る最適な経路のコストの推定値

上記の評価関数を使用した探索において，

h(n) ≦ h^*(n)

h^*(n)：節点 n から目標節点に至る最適な経路のコストの真の値

という関係が成立するとき，そのアルゴリズムを，A^* アルゴリズムと呼びます．A^*アルゴリズムでは，解経路が存在する場合，必ず最小コスト経路解を発見します．A^*アルゴリズムにおいて，

h1(n) ＞ h2(n)

なる関係があるとき，「アルゴリズム A1 は A2 よりも，より知識がある」といいます．

　　また，すべての枝が均一のコストを持つとき，知識を用いた探索と，縦型探索及び横型探索とは，以下のような関係があります．
- h(n) = 0, e(n) = 深さ　→　横型探索
- h(n) = 0, e(n) = -深さ　→　縦型探索

［探索の例： 8 パズル］　　以下，上記で述べた探索方法を，下に示す 2 つの 8 パズルの問題に適用した例について述べていきます．以下，左側の問題を例１，また，右側の問題を例２と呼びます．
例えば，例１では，以下に示すのが最適解になります．

横型探索

　　プログラム例（）は，横型探索によって上記の問題を解いた例です．同じ状態か否かをチェックするため STL の map クラスを使用しています（ Java の場合は，TreeMap クラス）．以下に示すのが，このプログラムを実行した結果です．「展開とチェック」の後ろの数字の内，最初の数字が展開したノードの数（キューに入れられたノードの数），後ろの数字がそれらの内，解か否かをチェックしたノードの数です．例２に対しては，かなり多くのノードを展開していることが分かると思います．なお，以下のプログラムにおいても同様ですが，このプログラムは最適解を得るためのものではありません．解が得られた時点でプログラムを終了しています．ただし，この問題の場合は，横型探索によって最適解が得られますので，得られた結果は最適解になっています．
例１展開とチェック： 62 35，　最短距離： 6 1 2 3 8 0 4 7 6 5 1 2 3 0 8 4 7 6 5 0 2 3 1 8 4 7 6 5 2 0 3 1 8 4 7 6 5 2 8 3 1 0 4 7 6 5 2 8 3 1 6 4 7 0 5 例２展開とチェック： 34299 22912，　最短距離： 19 1 2 3 8 0 4 7 6 5 1 2 3 8 4 0 7 6 5 1 2 0 8 4 3 7 6 5 1 0 2 8 4 3 7 6 5 1 4 2 8 0 3 7 6 5 1 4 2 8 6 3 7 0 5 1 4 2 8 6 3 7 5 0 1 4 2 8 6 0 7 5 3 1 4 2 8 0 6 7 5 3 1 4 2 0 8 6 7 5 3 0 4 2 1 8 6 7 5 3 4 0 2 1 8 6 7 5 3 4 2 0 1 8 6 7 5 3 4 2 6 1 8 0 7 5 3 4 2 6 1 0 8 7 5 3 4 2 6 0 1 8 7 5 3 0 2 6 4 1 8 7 5 3 2 0 6 4 1 8 7 5 3 2 1 6 4 0 8 7 5 3

縦型探索

　　プログラム例（）は，縦型探索によって上記の問題を解いた例です．以下に示すのが，このプログラムを実行した結果です．縦型探索の場合は，深さ制限を入れないと，非常に時間がかかると共に最適解が得られる可能性が小さくなります．
例１展開とチェック： 61 60，　最短距離： 6 1 2 3 8 0 4 7 6 5 --- 省略 --- 2 8 3 1 6 4 7 0 5 例２展開とチェック： 11150 11139，　最短距離： 19 1 2 3 8 0 4 7 6 5 --- 省略 --- 2 1 6 4 0 8 7 5 3

知識を用いた探索（評価関数を使用した探索）　　ここでは，2 つの評価関数を使用して，探索を行ってみます．

評価関数は，以下の通りとします．

f(n) = g(n) + h(n)

g(n)：節点 n の深さ
h(n)：節点 n の状態で，誤って置かれているコマの数

明らかに，これは，A^* アルゴリズムとなっています．上で述べた横型探索や縦型探索よりはかなり高速に解を求めることができますが，次に述べる方法と比較すると劣った結果になります．

評価関数は，以下の通りとします．

f(n) = g(n) + h(n)

g(n)：節点 n の深さ
h(n) = p(n) + 3s(n)

p(n)：各コマの正しい位置からの距離を加えた値
s(n)：中心以外のコマに対し，その次のコマが正しい順序になっていなければ 2，そうでなければ 0，中心の駒には 1 を与える事によって得られる得点

これは，A^* アルゴリズムとはなっていません．しかし，8 パズルに対しては，非常に高速に解を求めることができます．A^* アルゴリズムではありませんので，得られた結果が最適である保証はありませんが，ここで扱った例においては最適解となります．プログラム例（）は，この方法によって上記の問題を解いた例です．以下に示すのが，このプログラムを実行した結果です．なお，評価値が小さいものをキューの先頭に置くため，STL の priority_queue クラスを使用しています（ Java の場合は，PriorityQueue クラス）．
例１展開とチェック： 12 6，　最短距離： 6 1 2 3 8 0 4 7 6 5 --- 省略 --- 2 8 3 1 6 4 7 0 5 例２展開とチェック： 201 111，　最短距離： 19 1 2 3 8 0 4 7 6 5 --- 省略 --- 2 1 6 4 0 8 7 5 3
　　プログラム例（）は，横型探索によって上記の問題を解いた例です．同じ状態か否かをチェックするため STL の map クラスを使用しています（ Java の場合は，TreeMap クラス）．以下に示すのが，このプログラムを実行した結果です．「展開とチェック」の後ろの数字の内，最初の数字が展開したノードの数（キューに入れられたノードの数），後ろの数字がそれらの内，解か否かをチェックしたノードの数です．例２に対しては，かなり多くのノードを展開していることが分かると思います．なお，以下のプログラムにおいても同様ですが，このプログラムは最適解を得るためのものではありません．解が得られた時点でプログラムを終了しています．ただし，この問題の場合は，横型探索によって最適解が得られますので，得られた結果は最適解になっています．: 例１展開とチェック： 62 35，　最短距離： 6 1 2 3 8 0 4 7 6 5 1 2 3 0 8 4 7 6 5 0 2 3 1 8 4 7 6 5 2 0 3 1 8 4 7 6 5 2 8 3 1 0 4 7 6 5 2 8 3 1 6 4 7 0 5 例２展開とチェック： 34299 22912，　最短距離： 19 1 2 3 8 0 4 7 6 5 1 2 3 8 4 0 7 6 5 1 2 0 8 4 3 7 6 5 1 0 2 8 4 3 7 6 5 1 4 2 8 0 3 7 6 5 1 4 2 8 6 3 7 0 5 1 4 2 8 6 3 7 5 0 1 4 2 8 6 0 7 5 3 1 4 2 8 0 6 7 5 3 1 4 2 0 8 6 7 5 3 0 4 2 1 8 6 7 5 3 4 0 2 1 8 6 7 5 3 4 2 0 1 8 6 7 5 3 4 2 6 1 8 0 7 5 3 4 2 6 1 0 8 7 5 3 4 2 6 0 1 8 7 5 3 0 2 6 4 1 8 7 5 3 2 0 6 4 1 8 7 5 3 2 1 6 4 0 8 7 5 3
　　プログラム例（）は，縦型探索によって上記の問題を解いた例です．以下に示すのが，このプログラムを実行した結果です．縦型探索の場合は，深さ制限を入れないと，非常に時間がかかると共に最適解が得られる可能性が小さくなります．: 例１展開とチェック： 61 60，　最短距離： 6 1 2 3 8 0 4 7 6 5 --- 省略 --- 2 8 3 1 6 4 7 0 5 例２展開とチェック： 11150 11139，　最短距離： 19 1 2 3 8 0 4 7 6 5 --- 省略 --- 2 1 6 4 0 8 7 5 3; f(n) = g(n) + h(n); g(n)：節点 n の深さ
h(n)：節点 n の状態で，誤って置かれているコマの数
明らかに，これは，A^* アルゴリズムとなっています．上で述べた横型探索や縦型探索よりはかなり高速に解を求めることができますが，次に述べる方法と比較すると劣った結果になります．: f(n) = g(n) + h(n); g(n)：節点 n の深さ
h(n) = p(n) + 3s(n)

p(n)：各コマの正しい位置からの距離を加えた値
s(n)：中心以外のコマに対し，その次のコマが正しい順序になっていなければ 2，そうでなければ 0，中心の駒には 1 を与える事によって得られる得点
これは，A^* アルゴリズムとはなっていません．しかし，8 パズルに対しては，非常に高速に解を求めることができます．A^* アルゴリズムではありませんので，得られた結果が最適である保証はありませんが，ここで扱った例においては最適解となります．プログラム例（）は，この方法によって上記の問題を解いた例です．以下に示すのが，このプログラムを実行した結果です．なお，評価値が小さいものをキューの先頭に置くため，STL の priority_queue クラスを使用しています（ Java の場合は，PriorityQueue クラス）．: 例１展開とチェック： 12 6，　最短距離： 6 1 2 3 8 0 4 7 6 5 --- 省略 --- 2 8 3 1 6 4 7 0 5 例２展開とチェック： 201 111，　最短距離： 19 1 2 3 8 0 4 7 6 5 --- 省略 --- 2 1 6 4 0 8 7 5 3

システムの最適化

－ ３．組合せ最適化（ Combinatorial Optimization ） －

－３．組合せ最適化（ Combinatorial Optimization ）－