人工知能2 2005Apr26,May10

人工知能 Lecture 6
問題の分解、AND/OR
ハノイの塔
田中美栄子
第一部のおさらい
• 問題の定式化：
オペレータ：今の状態→次の状態
• 探索アルゴリズム（知識を用いない探索）
depth-1st, breadth-1st , optimal
• ヒューリステック探索：
• 小テスト１
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{
１．初期節点をopenリストに入れる
2. if(open==empty)break;（探索失敗）
3. n=first(open);
4. iｆ(goal(n))print(n);break;（探索終了）
5. remove(n,open);
6. 次に調べる節点をopenに入れる
7. ２へもどる｝
例題：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)が
予想出来るとき使える
• ステップ６で予想値h’(n)の昇順に並べる
ヒューリスティック探索の問題点
• ヒューリスティック関数（h’）の推定が悪いと、失敗
• 例：迷路の問題
h’＝｜Aｘー Gx｜＋｜Aｙー Gｙ｜
経路のつながり具合によって成功することもあり、
失敗することもある。（使えるヒント：正しい保障はない）
こういうヒントを多用して解を発見
ヒューリスティック
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{
１．初期節点をopenリストに入れる
2. if(open==empty)break;（探索失敗）
3. n=first(open);
4. iｆ(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. ２へもどる｝
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-１st B-１st
１
S
S
２
A
A
３
BC
BC
４
DEC CDE
５
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とよぶ
• 問題分割を用いた問題表現は、
１．開始問題記述
２，問題を副問題群に変換する作用素
３．原始問題記述の集合
問題分割表現の例：ハノイの塔
• 大きさが順に大きくなる３つの円盤、A,B,Cと３つの
柱1,2,3. 最初円盤は全て柱１の上に、一番小さい
Aを一番上に、Cを一番下にして積み重ねられてい
る。これを柱３にAが一番上になるように移す、但し
一度に１個だけ円盤を動かせる、どの円盤もそれよ
り小さい円盤の上に置けない
• 最初に出来るのはAを柱2か柱3に移すことだが、そ
のあとAの上にはBもCも置けないので、つまりはA
を移さなかった柱にBを移して置いて、その上にAを
移し、空いた柱3にCを移すことができれば成功であ
る．次にそのCの上にBを載せ、その上にAを載せる
８段階を右の３段階と見る
１.ABC
１. BC
１.
C
１. C
2. ＿
2. ＿
2. B
2. AB
3.＿
3. A
3. A
3.＿＿
高さ２の山を1.
から2. へ移す
高さ１を1.から3.へ
１.＿＿
１. A
１. A
１.＿＿
2. AB
2. B
2. ＿
2.＿＿
3. C
3. C
3. BC
3. ABC
高さ２の山を2.
から3. へ移す
円盤をN個に増やしても右の３段階
１.AB..C
１. C
2. ＿
3.＿
高さN-1の山
を1.から2. へ
2. AB.. 3.＿＿
高さ１を1.から3.へ
１.＿＿ 2. AB..
3. C
高さN-1の山
を2.から3. へ
１.＿＿ 2.＿＿ 3. ABC
目標：高さ３の山を柱１から柱３へ移す
小目標：高さ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→中２→終
始
中1
中２
終
ハノイの塔（N=2)は中間2ステップ
始状態（大小円盤が軸１にある）
大円盤を軸1に残し小円盤を軸２に移動
大円盤を軸3に移動し小円盤は軸２
終状態（大小円盤が軸３にある）
ハノイの塔（N=３）始→中1→中２→終
始
始→1’→２’→中1
中1
中２
終
中2→1”→２”→終
ハノイの塔（N=３）始→中1→中２→終
始
中1
中2
終
ハノイの塔（N=3)は中間6ステップ（中間2ス
テップの前後に各々下部中間2ステップ）
始状態（大中小が軸１にある）
小を軸3に移す。大中は軸１のまま
中を軸2に移す小は軸3、大は軸１
大は軸1.中小は軸２
大を軸3に移動し中小は軸２
小を軸1に中は軸２、大は軸３
小は軸1、大中は軸３
終状態（大中小円盤が軸３にある）
ハノイの塔（N=４）始→中1→中２→終
始
1
2
終
ハノイの塔（N=４）始→中1→中２→終
始
1
2
終
ハノイの塔（N=4)は中間14ステップ
始状態（大中小が軸１にある）
小を軸3に移す。大中は軸１のまま
中を軸2に移す小は軸3、大は軸１
大は軸1.中小は軸２
大を軸3に移動し中小は軸２
小を軸1に中は軸２、大は軸３
小は軸1、大中は軸３
終状態（大中小円盤が軸３にある）
ハノイの塔（N=5）始→中1→中2→終
始
中1
中2
終
ハノイの塔（N=5）
問題
• N=5のハノイの塔は始状態と終状態の間に
何ステップ余分に必要か？
• N円盤のハノイの塔は始状態と終状態の間
に何ステップ余分に必要か？
Nilsson（1971）によるAND/ORグラフ
１）各節点は単一問題か一連の問題であり、グラフは
開始節点（元問題）を含む．
２）終端節点（原始問題）＝葉
３）問題Pに対しこれを一組の副問題に変える作用素
があり、これを適用した結果生じる副問題に対応す
る節点へ向かって有向枝がある．このいずれかの
子節点が解かれたときＰが解けるのなら、OR節点
（OR-node）、全ての子節点が解かれたときPが解
けるのならAND節点（AND-node）とよぶ.AND節点
には枝を水平線で結ぶ
開始問題が解けるかどうかを示すグ
ラフ（or,木）を解グラフ（解木）という
• 解ける節点の条件として、
１）それが終端節点（原始問題）である
2)子節点が全て解けるAND節点であるような
非終端節点であるか、または
３）子節点がOR節点でそのうち少なくとも一つ
が解ける
• 解けない節点の条件
1)子節点のない非終端節点（どの作用素も適
用できないような非原始問題）
2)その子節点がAND節点で、そのうち少なくと
も一つが解けないような非終端節点
３）その子節点がOR節点で、その全てが解け
ないような非終端節点
問題の分解：ゲームの手の決定
• ゲームの木：チェスや碁等の特徴：交互にプレイす
る二人のプレーヤが参加し、最良の手を打つ、とい
うゲームに対してその全ての可能な手が表現されて
いる．
• 状態空間木との違いは、プレーヤが交互に選択す
ること：rootは初期状態で第１のプレーヤの手番、次
の子節点は第1のプレーヤが一手で到達できる状
態、その次の子節点は第２のプレーヤの応手で作ら
れる状態。終端節点は、勝、負、引分けのいずれか
• AND/OR木で表現できる（Aの立場からは自分の手
番はORで選べるが相手の手番はANDに対応）
例:tic-tac-toe（３目並）
* * *
* * *
* * *
* * *
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（３目並）
* * *
* * *
* * *
* * *
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（３目並）
* * *
* * *
* * *
* * *
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
引分

Download Report