人工知能2 2005Apr26,May10

人工知能2
2008 April 28
状態空間表現
探索法(知識を用いない探索)
状態と演算(作用)
• 状態(state) → 次状態(next state)
↑
演算(作用)operator
• 状態遷移図(グラフ)が出来ればこれを解く
(問題から出発してここに至るまでが勝負)
例2:ロボットの迷路抜け
• 入り口から出口への経路を見つける(ロボット
は地図を知らない)
ロボットの迷路抜け
• 道の真ん中を歩く(両壁から均等の距離を保つ)
ロボットの迷路抜け
• 格子点上を一歩ずつ歩く:(1,1)から(4,4)へ
(4,4)
(1,1)
ロボットの迷路抜け
• (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)
グラフ探索(基本的には前向き推論)
• 目標節点(求める状態記述に即したもの)を
探索する
• open list に今後調べなければならない節点
を入れておく(調べ終わったらopenから出す)
• まず、始節点がgoalかどうか調べる(違ったら
次へ行く)
探索の基本アルゴリズム(木の場合)
•
•
•
•
•
•
•
•
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へもどる}
Depth-1ST-search(木の場合)
•
•
•
•
•
•
•
Depth-first-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に入れる(nを展開し、全
ての子節点niをopenの先頭に入れる)。
niからnへポインタを付けておく。
• 7. 2へもどる}
例題:S→A→B→D→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)
Depth-1ST深さ優先探索(graph)
•
•
•
•
•
•
•
Depth-first-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の先頭に入れる)。
niからnへポインタを付けておく。
• 7. 2へもどる}
Breadth-1ST幅優先探索(graph)
•
•
•
•
•
•
•
breadth-first-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の最後に入れる)。
niからnへポインタを付けておく。
• 7. 2へもどる}
Open list の変化
• 深さ優先の場合
S→A→BC→DEC→EC→GF
• (状態遷移はS→A→B→E→G)
• 幅優先の場合
S→A→BC→CDE→DEHI→EHI→HIGF→I
GF→GF
• (状態遷移はS→A→B→E→G)