Nクイーン問題 N×Nのチェス盤の上に、将棋の飛車と角行の動きを同時にできる駒（クイーン）をお互いに動きを妨げないようにN個置け。 1千万王妃問題に対するアルゴリズム開発 Nの値 1 2 3 4 5 安全な配置数 1 0 0 2 10 • お互いに取り合わない配置を安全な配置と呼ぶ。 • 安全な配置数はNの値が大きくなるにつれて増えていくが、増え方は不規則である。安全な配置の見つけ方1 • N=4の場合・・・まず1行 2列目にクイーンを置きそこからナイト飛びにクイーンを置く。半分まで置いたら今度は1列目にクイーンを置けば出来上がり。 • N=10,16,22・・・,4+6i(i =0,1,2,・・・)も同様にして求められる。安全な配置の見つけ方2 • N=5の場合は、N=4と同じように置いたあと、対角線上の(5,5)の位置に置けばよい。貪欲アルゴリズム1 • 規則的ではなく、ランダムに配置を決め安全な配置を一つ求めるアルゴリズムが必要。 • 貪欲アルゴリズムと呼ばれる構築法は、まずチェス盤の1行目にランダムにクイーンを置き2行目、3行目・・・と置いていく。その際置いてはいけない場所に印をつけることによって安全な場所を知ることができる。貪欲アルゴリズム1 • 規則的ではなく、ランダムに配置を決め安全な配置を一つ求めるアルゴリズムが必要。 • 貪欲アルゴリズムと呼ばれる構築法は、まずチェス盤の1行目にランダムにクイーンを置き2行目、3行目・・・と置いていく。その際置いてはいけない場所に印をつけることによって安全な場所を知ることができる。貪欲アルゴリズム1 • 規則的ではなく、ランダムに配置を決め安全な配置を一つ求めるアルゴリズムが必要。 • 貪欲アルゴリズムと呼ばれる構築法は、まずチェス盤の1行目にランダムにクイーンを置き2行目、3行目・・・と置いていく。その際置いてはいけない場所に印をつけることによって安全な場所を知ることができる。貪欲アルゴリズム1 • 規則的ではなく、ランダムに配置を決め安全な配置を一つ求めるアルゴリズムが必要。 • 貪欲アルゴリズムと呼ばれる構築法は、まずチェス盤の1行目にランダムにクイーンを置き2行目、3行目・・・と置いていく。その際置いてはいけない場所に印をつけることによって安全な場所を知ることができる。貪欲アルゴリズム2 • 図のようにしてしまうと安全な場所がなくなってしまうのでその時ははじめからやりなおす。 • また再帰を使った列挙法に途中から移行する方法としてタブーサーチがある。貪欲アルゴリズム2 • 図のようにしてしまうと安全な場所がなくなってしまうのでその時ははじめからやりなおす。 • また再帰を使った列挙法に途中から移行する方法としてタブーサーチがある。貪欲アルゴリズム2 • 図のようにしてしまうと安全な場所がなくなってしまうのでその時ははじめからやりなおす。 • また再帰を使った列挙法に途中から移行する方法としてタブーサーチがある。初期解構築のプログラム • タブーサーチの改善法を適用するために、まず初期解を見つける方法を作ることが必要である。 • この方法では、クイーンの角行の動きを封じて安全な配置を求める。これを擬似安全な配置とする。タブーサーチの設計 • 初期解構築のプログラムで求めた配置から安全なクイーンの配置を見つけるために安全ではない度合（危険なクイーン・・・斜め方向で取り合っているクイーン）を目的関数にして、それを0にする。 • 危険なクイーンが存在するとき、今のクイーンの配置をちょっと変えて再び各行、各列にクイーンが1つずつ入るようにする（近傍）。つまり、2つのクイーンの場所を取り替える。このとき、目的関数値の減少が最大となるものを選択する。少し前に交換したクイーンを覚えといて、それと交換しないようにする（属性）。