N クイーン問題 N×N のチェス盤の上に、将棋の飛車と角 行の動きを同時にできる駒（クイーン） をお互いに動きを妨げないように N 個置 け。

Presentation on theme: "N クイーン問題 N×N のチェス盤の上に、将棋の飛車と角 行の動きを同時にできる駒（クイーン） をお互いに動きを妨げないように N 個置 け。"— Presentation transcript:

1 N クイーン問題 N×N のチェス盤の上に、将棋の飛車と角 行の動きを同時にできる駒（クイーン） をお互いに動きを妨げないように N 個置 け。

2 1 千万王妃問題に対するアルゴリズ ム開発 N の値安全な 配置数 11 20 30 42 510 お互いに取り合わな い配置を安全な配置 と呼ぶ。 安全な配置数は N の値 が大きくなるにつれ て増えていくが、増 え方は不規則である。

3 安全な配置の見つけ方 1 N=4 の場合・・・まず 1 行 2 列目にクイーン を置きそこからナイ ト飛びにクイーンを 置く。半分まで置い たら今度は 1 列目にク イーンを置けば出来 上がり。 N=10,16,22 ・・・,4+ 6i(i=0,1,2, ・・・ ) も同 様にして求められる。

4 安全な配置の見つけ方 2 N=5 の場合は、 N=4 と 同じように置いたあ と、対角線上の (5,5) の位置に置けばよい。

5 貪欲アルゴリズム 1 規則的ではなく、ランダ ムに配置を決め安全な配 置を一つ求めるアルゴリ ズムが必要。 貪欲アルゴリズムと呼ば れる構築法は、まずチェ ス盤の 1 行目にランダム にクイーンを置き 2 行目、 3 行目・・・と置いてい く。その際置いてはいけ ない場所に印をつけるこ とによって安全な場所を 知ることができる。

6 貪欲アルゴリズム 1 規則的ではなく、ランダ ムに配置を決め安全な配 置を一つ求めるアルゴリ ズムが必要。 貪欲アルゴリズムと呼ば れる構築法は、まずチェ ス盤の 1 行目にランダム にクイーンを置き 2 行目、 3 行目・・・と置いてい く。その際置いてはいけ ない場所に印をつけるこ とによって安全な場所を 知ることができる。

7 貪欲アルゴリズム 1 規則的ではなく、ランダ ムに配置を決め安全な配 置を一つ求めるアルゴリ ズムが必要。 貪欲アルゴリズムと呼ば れる構築法は、まずチェ ス盤の 1 行目にランダム にクイーンを置き 2 行目、 3 行目・・・と置いてい く。その際置いてはいけ ない場所に印をつけるこ とによって安全な場所を 知ることができる。

8 貪欲アルゴリズム 1 規則的ではなく、ランダ ムに配置を決め安全な配 置を一つ求めるアルゴリ ズムが必要。 貪欲アルゴリズムと呼ば れる構築法は、まずチェ ス盤の 1 行目にランダム にクイーンを置き 2 行目、 3 行目・・・と置いてい く。その際置いてはいけ ない場所に印をつけるこ とによって安全な場所を 知ることができる。

9 貪欲アルゴリズム 2 図のようにしてしま うと安全な場所がな くなってしまうので その時ははじめから やりなおす。 また再帰を使った列 挙法に途中から移行 する方法としてタ ブーサーチがある。

10 貪欲アルゴリズム 2 図のようにしてしま うと安全な場所がな くなってしまうので その時ははじめから やりなおす。 また再帰を使った列 挙法に途中から移行 する方法としてタ ブーサーチがある。

11 貪欲アルゴリズム 2 図のようにしてしま うと安全な場所がな くなってしまうので その時ははじめから やりなおす。 また再帰を使った列 挙法に途中から移行 する方法としてタ ブーサーチがある。

12 初期解構築のプログラム タブーサーチの改善法を適用するために、 まず初期解を見つける方法を作ることが 必要である。 この方法では、クイーンの角行の動きを 封じて安全な配置を求める。これを擬似 安全な配置とする。

13 タブーサーチの設計 初期解構築のプログラムで求めた配置から安全 なクイーンの配置を見つけるために安全ではな い度合（危険なクイーン・・・斜め方向で取り 合っているクイーン）を目的関数にして、それ を 0 にする。 危険なクイーンが存在するとき、今のクイーン の配置をちょっと変えて再び各行、各列にク イーンが 1 つずつ入るようにする（近傍）。つま り、 2 つのクイーンの場所を取り替える。このと き、目的関数値の減少が最大となるものを選択 する。少し前に交換したクイーンを覚えといて、 それと交換しないようにする（属性）。