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つのクイーン
の場所を取り替える。このとき、目的関数値の減少
が最大となるものを選択する。少し前に交換したク
イーンを覚えといて、それと交換しないようにする
(属性)。
ダウンロード

Nクイーン問題