アルゴリズム・データ構造 I 第9回
幅優先探索で8パズルを解く
名城大学理工学部情報工学科
山本修身
復習
もう一つの探索方法：幅優先探索 (1)
データ構造：キュー（queue; FIFO: First In First Out)
取り出すときは左から
入れるときは右から
JavaScriptでは，配列に
a = []
a.push(23)
a.push(55)
puts(a.shift())
a.push(89)
puts(a.shift())
puts(a.shift())
キューの機能がついてい
23
55
89
る．データを入れる場合に
はpush(), データを取り出す
場合にshift()を用いる
2
復習
3
もう一つの探索方法：幅優先探索 (2)
もう一つの木の辿り方：深さ優先探索では深いところまでまず，降り
て行き，降りられなくなったら戻るという方法をとった．もう一つの
方法は，根 (root) に近いところから順に見て行く方法である．木の
深さが無限大でも探索することができる．
幅優先探索：BFS (breadth first search)
A
A
A
A
A
A
A
A
A A
A
L LL L L L L L LL L L L L L
復習
もう一つの探索方法：幅優先探索 (3)
•
深さ優先探索が再帰的なプログラミングで実現できるのに対し
て，幅優先探索は繰り返しを用いて実現できる．
queue = [根のノード]
while (queue.length > 0){
node = queue.shift()
node 個別の処理
nodeの子供をqueueに付け加える
}
この方法ではqueueの長さが爆発する可能性がある
4
5
8パズルとは
•
３x３のボードの上に１∼8までの数の書かれたコマが置かれて
いて，一カ所だけ空いている（左下の図を参照）．
•
空白のマスの周りにあるコマを空白のマスに移動させることに
より，このパズルの状態を変化させることができる．
•
このパズルの目的は，適当にコマを何回か移動させて，右下の
ようなゴール状態に変化させることである．
4
7
8
1
5
2
3
6
適当な初期状態
1
2
3
4
5
6
7
8
ゴール状態
6
8パズルの状態と遷移を表現する
•
８パズルの状態を表現するには，それぞれの位置にどのコマが
置かれているを表現すれば良い．そのために配列を用いる．
•
最終状態は，とりあえず [0, 1, 2, 3, 4, 5, 6, 7, 8]
とする．
•
また，遷移は空白の位置へ動かす駒の動く方向によって表現す
る．空白を中心として，空白に接するコマをどちらに動かすか
で，r, l, d, u を用いて表現する．
d
2
5 l
r3
4u
7
8パズルを実行できる環境 (1)
•
ここでは，8パズルの動きを表示できるプログラミング環境を用
意している．
8
8パズルを実行できる環境 (2)
•
この環境では2つの関数が用意されている．一つは
set_board_state(state)
であり，コマの配置を大きさ9の配列stateで指定する．もう一つの
関数は，
play_moves("lluurrdd")
であり，空欄へ動かすコマの移動方向を示す文字列を引数として渡
す．これらの関数による命令は，プログラムが実行された後に実行さ
れる．
9
8パズルをランダムに動かしてみる (1)
•
まず，パズルを動かす環境をつくる．
function move(i){
var z = find_zero()
var ix = z % 3
var iy = Math.floor(z / 3)
if (i == DOWN && iy > 0){
state[z] = state[z - 3]
state[z - 3] = 0
} else if (i == UP && iy < 2){
function find_zero(){
state[z] = state[z + 3]
for (var i =0; i < 9; i++){
state[z + 3] = 0
if (state[i] == 0) return i
} else if (i == RIGHT && ix > 0){
}
state[z] = state[z - 1]
return null
state[z - 1] = 0
}
} else if (i == 3 && ix < 2){
state[z] = state[z + 1]
state[z + 1] = 0
}
}
var
var
var
var
var
var
state
UP = 0
DOWN = 1
RIGHT = 2
LEFT = 3
dir = "udrl"
10
•
8パズルをランダムに動かしてみる (2)
実際に動かす関数を作る．
↓初期状態
function make_random_state(N){
function next_move_list(pat,
state = [0, 1, 2, 3, 4, 5, 6, 7, 8]
last_move){
var last_move = null
var moves = []
var res = ""
var z = find_zero()
for (var n = 0; n < N; n++){
var ix = z % 3
var moves =
var iy = Math.floor(z / 3)
next_move_list(state, last_move)
if (ix > 0 && last_move
var m = Math.floor(
!= LEFT)moves.push(RIGHT)
Math.random() * moves.length)
if (ix < 2 && last_move
res = res + dir[moves[m]]
!= RIGHT) moves.push(LEFT)
move(moves[m])
if (iy > 0 && last_move
last_move = moves[m]
!= UP)moves.push(DOWN)
}
if (iy < 2 && last_move
return res
!= DOWN)moves.push(UP)
}
return moves
}
配列 moves に現時点で動くことが可
能な方向を入れて，その中からラン
ダムに1つ適当な方向を選ぶ
最後に動かした履歴を文字列として返す
11
8パズルをランダムに動かしてみる (3)
実際に動かした最終状態から逆戻しに初期状態まで動かしてみる
function work(){
var res = make_random_state(200) ←200回ほどランダムにコマを動かす
var transform = function (c){
if (c == 'u') c = 'd'
else if (c == 'd') c = 'u'
else if (c == 'r') c = 'l' 逆戻しの動きを作る
else if (c = 'l') c = 'r'
return c
}
set_board_state(state) ←ボードに最後の状態をセットする
resx = ""
for (var i = 0; i < res.length; i++)
resx = transform(res[i]) + resx ←文字列を入れ換えてひっくり返す
play_moves(resx)
←動きのアニメーションを表示
}
work()
12
8パズルをランダムに動かしてみる (4)
•
以下のように変化して初期状態に戻すことができる
200ステップ
ururdlulddruurdldluurrddl
uldruldrruulddruullddrruu
ldlurrddllurrulddluurrddl
lurdruldluurrddllurrulldd
rurdlurdlurdlluruldrrdllu
urdlurrdlulddruldrruuldrd
lurullddruurdlurdllurdrdl
uulddruulddrruuldrullddrr
13
幅優先探索で8パズルを解く (1)
幅優先探索で8パズルを解くには，まず，それぞれのノードをどのように表現するか
を考える必要がある．
•
•
•
明らかにそれぞれの状態はそれぞれのコマの配置を表現しなければならない．
さらにどのような動作で，その状態に至ったかがわからないといけない．
また，自分の親の状態が何なのかを知る必要がある
6
1
2
3
8
5
7
4
LEFT
6
1
2
3
8
5
7
4
[6,1,2,3,8,5,7,0,4]
[6,1,2,3,8,5,0,7,4]
DOWN
6
3
1
2
8
5
7
4
[6,1,2,0,8,5,3,7,4]
14
幅優先探索で8パズルを解く (2)
ここではノードを以下のように表現する：
[LEFT, [6,1,2,3,8,5,7,0,4], 親のノード]
LEFT
幅優先探索を用いるために，このように表現され
たノードをキューに入れて処理する．純粋に幅優
6
1
2
先探索を用いて，それ以上の手がかりを使うこと
3
8
5
は考えない．【実はコマの配置から解に近そうな
ノードとそうでないノードを区別することが可能
である．そのような情報を用いて高速に解を導く
方法が考えられる】
7
4
[6,1,2,3,8,5,7,0,4]
幅優先探索で8パズルを解く (3)
•
15
いくつかの部品を改良する．大域変数stateをなくす
function find_zero(state){
function move(state, i){
for (var i =0; i < 9; i++){
state = state.slice(0)
if (state[i] == 0) return i
var z = find_zero(state)
}
var ix = z % 3
return null
var iy = Math.floor(z / 3)
空白の位置を探す
}
if (i == DOWN && iy > 0){
function next_move_list(state,
state[z] = state[z - 3]
last_move){
state[z - 3] = 0
var moves = []
} else if (i == UP && iy < 2){
var z = find_zero(state)
state[z] = state[z + 3]
var ix = z % 3
state[z + 3] = 0
} else if (i == RIGHT && ix > 0){ var iy = Math.floor(z / 3)
if (ix > 0 && last_move != LEFT)
state[z] = state[z - 1]
moves.push(RIGHT)
state[z - 1] = 0
if (ix < 2 && last_move != RIGHT)
} else if (i == 3 && ix < 2){
moves.push(LEFT)
state[z] = state[z + 1]
if (iy > 0 && last_move != UP)
state[z + 1] = 0
moves.push(DOWN)
}
次に動かせる方向 if (iy < 2 && last_move != DOWN)
return state
moves.push(UP)
}
のリストを作る→
return moves
}
state上のコマを動かす
幅優先探索で8パズルを解く (4)
• さらにいくつかの部品を追加する
function make_random_state(N, state){
var last_move = null
for (var n = 0; n < N; n++){
var moves = next_move_list(state, last_move)
var m = Math.floor(Math.random() * moves.length)
state = move(state, moves[m])
last_move = moves[m]
}
N回ランダムに動かして新たな配置を作る
return state
}
function make_node(dir, pat, parent){
return [dir, pat, parent]
}
ノードを作る
function eq_pat(pat1, pat2){
for (var i = 0; i < 9; i++){
if (pat1[i] != pat2[i]) return 1
}
return 0
パターンが等しいかどうかを調べる
}
16
17
幅優先探索で8パズルを解く (5)
•
さらに部品を追加する
function encode(pat){
var s = 0
for (var i = 0; i < 9; i++)
s = s * 9 + pat[i]
return s
コマの配置を数で表現する
}
function in_list(a, lst){
for(var i = 0; i < lst.length; i++){
if (a == lst[i]) return true
}
return false
数のリスト lst の中に数 a が存在するかどう
}
かを調べる
幅優先探索で8パズルを解く (6)
• 幅優先探索でパズルを解く
• 移動回数が最も少ない解を見つける
function work(){
18
var state1 = [0, 1, 2, 3, 4, 5, 6, 7, 8]
var state = make_random_state(40, state1) ランダムなパターンを作る
puts(state)
var mm = [] １回出現したパターンを蓄える
var queue = [make_node(null, state, null)] 初期のキューを作る
while (queue.length > 0){
var node = queue.shift()
if (eq_pat(node[1], state1) == 0) break
var mlist = next_move_list(node[1], node[0])
for (var i = 0; i < mlist.length; i++){
一度見つかった配置
var st = move(node[1], mlist[i])
が再度現れたら
if (in_list(encode(st), mm)) continue
キューに入れない
var node1 = make_node(mlist[i], st, node)
mm.push(encode(st))
action = ""
queue.push(node1)
while (true){
}
if (node[0] == null) break
}
action = dir[node[0]] + action
node = node[2]
}
puts(action)
}
19
幅優先探索で8パズルを解く (7)
•
幅優先探索を純粋に実行すると計算量が大きくなりすぎる．その
ために，一度出て来たパターンは2回目は使わないようにする．
0
if (in_list(encode(st), mm)) continue
var node1 = make_node(mlist[i], st, node)
mm.push(encode(st))
幅優先探索ではこちらの
方が必ず先に出現する
1
2
3
ン
ー
タ
じ
同
パ
より根に近いものがあれ
ば，遠いものは調べる必
要がない．
20
幅優先探索で8パズルを解く (8)
•
修了状態が得られたら，そこから根に
根 (root)
A
結果の取り出し
A=[null, p1, null]
r
むけてサーチし，根からの動きを出力
する．
B= [‘r’, p2, A]
B
u
それぞれのコマの配置を出力する必要
はない．初期状態（根におけるコマの
C
配置）がわかっていれば，そこから作
り出すことができる．
action = ""
while (true){
if (node[0] == null) break
action = dir[node[0]] + action
node = node[2]
}
puts(action)
C= [‘u’, p2, B]
l
D
“ruld”
D= [‘l’, p3, C]
d
E
E= [‘d’, p4, D]
終了状態
© Copyright 2024 ExpyDoc
