人工知能2 2005Apr26,May10

人工知能 Lecture 6
問題の分解、AND/OR
ハノイの塔
田中美栄子
第一部のおさらい
• 問題の定式化:
オペレータ:今の状態→次の状態
• 探索アルゴリズム(知識を用いない探索)
depth-1st, breadth-1st , optimal
• ヒューリステック探索:
• 小テスト1
A*-algorithm
ロボットの迷路抜け
• (1,1)から(4,4)へ
(1,1)
3
(2,4)
(1,4)
(2,3)
(3,4)
(4,4)
(2,3)
(2,4)
(3,3)
(2,2)
2
(3,2)
(1,4)
(2,2)
(3,4)
(3,2)
(3,1)
4
(4,4)
(1,1)
(3,1)
(3,3)
探索の基本アルゴリズム
•
•
•
•
•
•
•
•
Search algorithm{
1.初期節点をopenリストに入れる
2. if(open==empty)break;(探索失敗)
3. n=first(open);
4. if(goal(n))print(n);break;(探索終了)
5. remove(n,open);
6. 次に調べる節点をopenに入れる
7. 2へもどる}
例題:S→A→B→E→G
• S(1,1)からG(4,4)へ
(2,4)
(1,4)
(2,3)
(3,4)
S(1,1)
(4,4)
A(2,3)
B(2,4)
(3,3)
C(2,2)
2
H(3,2)
D(1,4)
(2,2)
E(3,4)
(3,2)
I(3,1)
4
G(4,4)
(1,1)
(3,1)
F(3,3)
Heuristic search
• 最良優先探索:best-first-search
• 各節点からゴールまでのコスト(距離)h(n)が
予想出来るとき使える
• ステップ6で予想値h’(n)の昇順に並べる
ヒューリスティック探索の問題点
• ヒューリスティック関数(h’)の推定が悪いと、失敗
• 例:迷路の問題
h’=|Ax ー Gx|+|Ay ー Gy|
経路のつながり具合によって成功することもあり、
失敗することもある。(使えるヒント:正しい保障はない)
こういうヒントを多用して解を発見
ヒューリスティック
h=|nのx座標-Gのx座標|+| nのy座標-Gのy座標|
• S(1,1)からG(4,4)へ
(2,4)
(1,4)
(2,3)
(3,4)
(3,3)
S(1,1)6
(4,4)
A(2,3)3
B(2,4)2
C(2,2)4
2
H(3,2)
D(1,4)3
(2,2)
E(3,4)1
(3,2)
I(3,1)
4
G(4,4)0
(1,1)
(3,1)
F(3,3)
A*ーアルゴリズム
•
•
•
•
•
•
•
A*-search algorithm{
1.初期節点をopenリストに入れる
2. if(open==empty)break;(探索失敗)
3. n=first(open);
4. if(goal(n))print(n);break;(探索終了)
5. remove(n,open); add(n,closed);
6. 次に調べる節点をopenに入れる(nを展開し、全ての子節
点niをopenに入れ、推定コストf(ni)の昇順に並べる) ここで
f(ni)=g’(ni)+h’(ni)であり、推定値h’(ni)が本当の値h(ni)以下で
あるとする。(これが成立しないとA*-search でなく、 A-search
になり、解は保証されない ) g’(ni)はg(ni)の推定値だが、出発
点からniまでの、解っているコストの内で最小のもの。
niからnへポインタを付けておく
• 7. 2へもどる}
h=|nのx座標-Gのx座標|+| nのy座標-Gのy座標|
• S(1,1)からG(4,4)へ
(2,4)
(1,4)
(2,3)
(3,4)
(3,3)
S(1,1)6
(4,4)
A(2,3)3
B(2,4)2
C(2,2)4
2
H(3,2)
D(1,4)3
(2,2)
E(3,4)1
(3,2)
I(3,1)
4
G(4,4)0
(1,1)
(3,1)
F(3,3)
比較:深さ優先、幅優先、A*
open list
Counter D-1st B-1st
1
S
S
2
A
A
3
BC
BC
4
DEC CDE
5
EC DEHI
A*
S(6)
A(6)
B(6)C(8)
E(6)D(8)C(8)
G(6)FDC
Problem reduction representation
• 問題を分割し、すぐ解ける副問題の集合に変換
• 許された変換は「オペレータ(作用素)」として定義
• すぐ解ける問題は原始問題primitive problemとよぶ
• 問題分割を用いた問題表現は、
1.開始問題記述
2,問題を副問題群に変換する作用素
3.原始問題記述の集合
問題分割表現の例:ハノイの塔
• 大きさが順に大きくなる3つの円盤、A,B,Cと3つの
柱1,2,3. 最初円盤は全て柱1の上に、一番小さい
Aを一番上に、Cを一番下にして積み重ねられてい
る。これを柱3にAが一番上になるように移す、但し
一度に1個だけ円盤を動かせる、どの円盤もそれよ
り小さい円盤の上に置けない
• 最初に出来るのはAを柱2か柱3に移すことだが、そ
のあとAの上にはBもCも置けないので、つまりはA
を移さなかった柱にBを移して置いて、その上にAを
移し、空いた柱3にCを移すことができれば成功であ
る.次にそのCの上にBを載せ、その上にAを載せる
8段階を右の3段階と見る
1.ABC
1. BC
1.
C
1. C
2. _
2. _
2. B
2. AB
3._
3. A
3. A
3.__
高さ2の山を1.
から2. へ移す
高さ1を1.から3.へ
1.__
1. A
1. A
1.__
2. AB
2. B
2. _
2.__
3. C
3. C
3. BC
3. ABC
高さ2の山を2.
から3. へ移す
円盤をN個に増やしても右の3段階
1.AB..C
1. C
2. _
3._
高さN-1の山
を1.から2. へ
2. AB.. 3.__
高さ1を1.から3.へ
1.__ 2. AB..
3. C
高さN-1の山
を2.から3. へ
1.__ 2.__ 3. ABC
目標:高さ3の山を柱1から柱3へ移す
小目標:高さ2の
山を柱1から柱2
へ避難させる
原始問題:高さ
1の山を柱1か
ら柱3へ移動
高さ1の
高さ1の 山を柱3
高さ1 山を柱1 から柱2
の山を から柱2 へ移動
柱1か へ移動
ら柱3
へ移動
小目標:高さ2の
山を柱2から柱3
へ移す
高さ1の山を
高さ1の山 柱2から柱3
を柱2から へ移動
柱1へ移動
高さ1の
山を柱1
から柱3
へ移動
ハノイの塔(N=2)始→中1→中2→終
始
中1
中2
終
ハノイの塔(N=2)は中間2ステップ
始状態(大小円盤が軸1にある)
大円盤を軸1に残し小円盤を軸2に移動
大円盤を軸3に移動し小円盤は軸2
終状態(大小円盤が軸3にある)
ハノイの塔(N=3)始→中1→中2→終
始
始→1’→2’→中1
中1
中2
終
中2→1”→2”→終
ハノイの塔(N=3)始→中1→中2→終
始
中1
中2
終
ハノイの塔(N=3)は中間6ステップ(中間2ス
テップの前後に各々下部中間2ステップ)
始状態(大中小が軸1にある)
小を軸3に移す。大中は軸1のまま
中を軸2に移す小は軸3、大は軸1
大は軸1.中小は軸2
大を軸3に移動し中小は軸2
小を軸1に中は軸2、大は軸3
小は軸1、大中は軸3
終状態(大中小円盤が軸3にある)
ハノイの塔(N=4)始→中1→中2→終
始
1
2
終
ハノイの塔(N=4)始→中1→中2→終
始
1
2
終
ハノイの塔(N=4)は中間14ステップ
始状態(大中小が軸1にある)
小を軸3に移す。大中は軸1のまま
中を軸2に移す小は軸3、大は軸1
大は軸1.中小は軸2
大を軸3に移動し中小は軸2
小を軸1に中は軸2、大は軸3
小は軸1、大中は軸3
終状態(大中小円盤が軸3にある)
ハノイの塔(N=5)始→中1→中2→終
始
中1
中2
終
ハノイの塔(N=5)
問題
• N=5のハノイの塔は始状態と終状態の間に
何ステップ余分に必要か?
• N円盤のハノイの塔は始状態と終状態の間
に何ステップ余分に必要か?
Nilsson(1971)によるAND/ORグラフ
1)各節点は単一問題か一連の問題であり、グラフは
開始節点(元問題)を含む.
2)終端節点(原始問題)=葉
3)問題Pに対しこれを一組の副問題に変える作用素
があり、これを適用した結果生じる副問題に対応す
る節点へ向かって有向枝がある.このいずれかの
子節点が解かれたときPが解けるのなら、OR節点
(OR-node) 、全ての子節点が解かれたときPが解
けるのならAND節点(AND-node)とよぶ.AND節点
には枝を水平線で結ぶ
開始問題が解けるかどうかを示すグ
ラフ(or,木)を解グラフ(解木)という
• 解ける節点の条件として、
1)それが終端節点(原始問題)である
2)子節点が全て解けるAND節点であるような
非終端節点であるか、または
3)子節点がOR節点でそのうち少なくとも一つ
が解ける
• 解けない節点の条件
1)子節点のない非終端節点(どの作用素も適
用できないような非原始問題)
2)その子節点がAND節点で、そのうち少なくと
も一つが解けないような非終端節点
3)その子節点がOR節点で、その全てが解け
ないような非終端節点
問題の分解:ゲームの手の決定
• ゲームの木:チェスや碁等の特徴:交互にプレイす
る二人のプレーヤが参加し、最良の手を打つ、とい
うゲームに対してその全ての可能な手が表現されて
いる.
• 状態空間木との違いは、プレーヤが交互に選択す
ること:rootは初期状態で第1のプレーヤの手番、次
の子節点は第1のプレーヤが一手で到達できる状
態、その次の子節点は第2のプレーヤの応手で作ら
れる状態。終端節点は、勝、負、引分けのいずれか
• AND/OR木で表現できる(Aの立場からは自分の手
番はORで選べるが相手の手番はANDに対応)
例:tic-tac-toe(3目並)
* * *
* * *
* * *
* * *
X * *
全部引分
*
*
*
X
*
*
*
X
O
*
O
*
X
*
*
*
X
O X *
*
X *
*
* *
O
*
*
X
*
X
*
*
O
*
*
*
X
O
*
*
*
O *
*
O
X X
*
*
X
*
O
X
*
*
*
*
O
*
O
X *
*
*
*
* * *
*
X
*
X X
* *
*
*
X
*
* X *
*
X
O X
*
*
* O *
X *
*
O
O
*
* *
*
O X X
X
X
O
*
O
*
X
*
*
*
O
O X X
X
*
*
*
O
X
O
X
X
*
O X
*
O
X
O X X
O X O
*
O X X
X
*
*
O
X
O
X O
X
X
O
O X O
O X X
*
O
X
O X X
X O
X O
*
O X O
*
O *
X O *
*
O *
* O *
*
X *
*
X *
X X *
* X *
X
*
*
* *
*
* X *
*
*
* *
* O O
* O O
* X *
X * *
X O
*
*
X
*
*
*
O
*
* *
X O
*
*
O
*
*
X
*
X X
*
X X O
*
X
*
*
*
O
*
X O
*
*
X X
*
X X O
X O
X O O
O
O
X
*
X X
*
X O
*
O *
X X *
* X
*
* X
*
X O O
*
*
O X X
*
*
*
O X X
O
O X
*
* * *
O
O X *
O
O
X * *
* * *
* * *
O
* * *
* X *
* * *
O
*
X
X X O
O
O
* *
X X
X X O
O * *
O X X
X X O
O O *
O X X
X X O
O O X
X O O
* X *
X * *
X O O
O X *
X * *
X O O
O X *
X * X
X勝
*
X O
*
X X X
O
*
O
X勝
*
X O O
*
*
O
*
X勝
*
X
*
*
*
X O O
O X X
*
X O
引分
例:tic-tac-toe(3目並)
* * *
* * *
* * *
* * *
X * *
* * *
* * *
* X *
* * *
* * *
X * *
* * *
* O *
O X *
O
*
*
O
*
*
X *
*
X
*
*
X X
*
* *
O X *
*
*
*
X
*
*
*
*
O O
*
O
*
X
*
*
*
X
O X X
X *
*
*
*
*
*
O O X
O
*
*
O X *
*
X
*
O X X
*
*
*
X
*
O *
X *
X O *
O O X
O X O
*
X
*
*
X
*
O
*
X
X
O
*
X
O
O
X
O
X
X
O
X
X
O
*
O
X
*
O
X
*
X
O
*
*
*
O
O X X
X
*
O X O
O X X
X X
*
O
X
X * *
O X O
O O X
X X O
O
*
X
O X X
X O
* *
*
X *
*
* *
* X *
* * *
O
*
X
*
X
*
*
O
*
*
*
X
*
X
O
*
*
X
*
O
*
*
O
*
X
*
* X *
* X X
* * X
O O *
X *
*
* O
* X
*
* X O
* X
* X O
* X *
* O X
* X *
X O O
* X O
*
*
*
*
O
*
O
O
X
O
O
*
X
*
*
* O X
* X
*
X O
O X
X *
X O
X X O
*
O X
O X
X X
X X O
*
*
*
X
*
*
O X O
O O X
X X O
O X
全部引分
* O
*
* O
*
*
*
O
O
*
* X
*
X X
O
* O
*
*
O
* O *
全部引分 *
*
O O X
*
O
*
*
O X
X X O
O X O
X
O
X
X
O
X
X
O
X
X
*
*
X
O
*
X
O
*
X
O
*
X O X
O X O
O X O
* O O
X
*
*
X *
O O
X *
X O
X O O
* X X
* X O
X O O
O X X
* X O
X
*
* * X
O O X
*
X
*
*
*
X
O O X
*
X O
*
*
X
X勝
*
* *
*
* O X
*
O
*
O X X
* *
X O
*
*
O X X
* *
X O
*
*
*
* *
*
*
O X
*
X
*
O
*
*
*
O X
*
X
*
O
*
X
*
O X
O X X
*
X O
X
O
*
O X X
*
* X
* O
X O *
*
O
X
X O O
X O X
O X X
*
X O
O
*
X
*
O
引分
X
X勝
例:tic-tac-toe(3目並)
* * *
* * *
* * *
* * *
X * *
* * *
* X *
* * *
X * *
* * *
* * *
O
* *
*
X *
*
* *
* * *
* O *
* X *
* * *
全部引分
*
O *
X O *
*
O *
* O *
*
X *
*
X *
X X *
* X *
X
* *
*
* *
*
* X *
X O O
O X *
X * X
* *
X O
** O *
X O O
X X
XX X O
O X X
O
*
X勝
X勝
X
O
X勝
*
*
*
X O
引分