III. 探索空間

探索空間

私たちがある問題を解決しようとするとき、私たちはいくつかの候補の中で最もよい解を探します。すべての実行可能な解の空間は、探索空間と呼ばれています。探索空間内の各点が、１つの実行可能な解をあらわしています。どの実行可能な解も、その値または問題に対する適合度で"マーク"されます。私たちは、実行可能な解－つまり探索空間内の点－の中から問題に対する答え１つ（もしくはそれ以上）を探します。

解を探すということは、探索空間内のいくつかの極値（最小値、もしくは最大値）を探すことと同じです。

問題は探索が非常に難しくなりうるということです。１つは探している解がどこにあるのか、またどこから始めればいいのかがわからないということです。いくつかの適切な解(つまり最高の解である必要はないのです)を探す方法として、ヒルクライミング、タブーサーチ、シミュレーテッドアニーリング、遺伝的アルゴリズムなど、たくさんの方法があります。これらの方法によって見つかった解はしばしば、よい解としてかんがえられます。なぜなら、本当の最適解を証明するのはたいてい可能なことではないのです。

NP困難問題

"伝統的な"方法で解くことのできない難しい問題をＮＰ問題といいます

また、アルゴリズム的に解くことが不可能な問題もあります。そして多項式の時間で解くことができない問題があることが証明されている。

NP問題に関して、ちらっと見ただけで明らかに解を見つけることができる単純なアルゴリズムをもっているという特徴があります。それはすべての可能な解を調べることです。しかしこのアルゴリズムは非常に遅いです（普通２のｎ乗のオーダーです、たとえちょっとした問題の例でさえも、そのアルゴリズムは全く使うことができません。）

今日、より速くて正確なアルゴリズムを知っている人は誰もいません。新しい研究者（もちろんあなたも! :-) )に対して大きな問題として残っています。しかし、たくさんの人々はそのようなアルゴリズムがあるとは思っていませんそして、彼らは別の方法を探しています。これらの方法の例として遺伝的アルゴリズムがあります。