積木の移動
前回は基本的な探索アルゴリズムである深さ優先探索、幅優先探索、反復深化を説明しました。今回は簡単な例題として、積木の移動手順を求めるプログラムを作ってみましょう。
●問題の説明
積木は赤 (red)、青 (blue)、緑 (green) の三種類あり、積木を置く場所は x, y, z の三か所あります。積木は、一回にひとつしか移動できません。また、上に積木が置かれている場合も、移動することはできません。上にある積木をどかしてから移動します。左図の初期状態の場合、積木 red を場所 y か場所 z へ動かすことはできますが、積木 blue や green を動かすことはできません。
問題はスタートから積木をひとつずつ動かして、ゴールになるまでの移動手順を求めることです。
●データ構造の定義
最初にデータ構造を決めましょう。積木は文字列 "red", "blue", "green" で表すことにします。積木はリストに格納して、そのリストをタプルに格納することにしましょう。すると、スタートとゴールの局面 (状態) は次のように表すことができます。
start: (List("red", "blue", "green"), Nil, Nil)
goal : (Nil, Nil, List("red", "blue", "green"))
タプルの 1 番目の要素が場所 x, 2 番目の要素が場所 y, 3 番目の要素が場所 z を表します。各場所の状態をリストで表すと、一番上の積木はリストのパターンマッチング x::xs で簡単に取り出すことができます。それから、局面を表す型が長くなるので、type で別名を定義します。
リスト : 積木の局面 type State = (List[String], List[String], List[String])
●積木を動かす
次は積木を動かすプログラムを作ります。積木の動かし方は次の 6 通りがあります。
x -> y, x -> z y -> x, y -> z z -> x, z -> y
これをそのままプログラムすると、次のようになります。
リスト : 積木を動かす
// x -> y
def moveXtoY(st: State): List[State] = st match {
case (x::xs, ys, zs) => List((xs, x::ys, zs))
case _ => Nil
}
// x -> z
def moveXtoZ(st: State): List[State] = st match {
case (x::xs, ys, zs) => List((xs, ys, x::zs))
case _ => Nil
}
// y -> x
def moveYtoX(st: State): List[State] = st match {
case (xs, y::ys, zs) => List((y::xs, ys, zs))
case _ => Nil
}
// y -> z
def moveYtoZ(st: State): List[State] = st match {
case (xs, y::ys, zs) => List((xs, ys, y::zs))
case _ => Nil
}
// z -> x
def moveZtoX(st: State): List[State] = st match {
case (xs, ys, z::zs) => List((z::xs, ys, zs))
case _ => Nil
}
// z -> y
def moveZtoY(st: State): List[State] = st match {
case (xs, ys, z::zs) => List((xs, z::ys, zs))
case _ => Nil
}
moveXtoY は x にある積み木を y へ移動します。パターンマッチングで場所 x の一番上にある積木 x を取り出して、それを場所 y のリスト ys の先頭に追加します。返り値は新しい状態 (State) をリストに格納したものです。場所 x に積み木がない場合は空リスト Nil を返します。他の関数も同じように一番上の積木を動かします。
これらの関数を使って、局面 st から積木を動かして新しい局面を作成し、それをリストに格納して返す関数 makeNewState を作ります。
リスト : 新しい局面を作る
// 移動関数表
val moveFunc = List(moveXtoY _, moveXtoZ _, moveYtoX _,
moveYtoZ _, moveZtoY _, moveZtoX _)
// 新しい局面を生成する
def makeNewState(st: State): List[State] = moveFunc.flatMap((f:State => List[State]) => f(st))
積木を移動する関数をリスト moveFunc に格納します。関数値を取り出していることに注意してください。関数 makeNewState は、現在の状態 st にこれらの関数を適用して、新しい状態を生成します。この場合、map を使うとリストの中にリストが格納される、つまり、返り値の型が List[List[State]] になってしまいます。このような場合、リストを平坦化 (flatten) すると List[List[State]] を List[State] に変換することができます。
リストのメソッド flatMap は map のあとに flatten を行ってくれます。簡単な例を示しましょう。
scala> List(1,2,3,4,5).map(x => List(x,x)) val res0: List[List[Int]] = List(List(1, 1), List(2, 2), List(3, 3), List(4, 4), List(5, 5)) scala> List(1,2,3,4,5).flatMap(x => List(x,x)) val res1: List[Int] = List(1, 1, 2, 2, 3, 3, 4, 4, 5, 5)
無名関数は引数 x を 2 つリストに格納して返します。map の場合、返り値の型は List[List[Int]] になりますが、flatMap ではマッピングのあとに平坦化が行われるので List[Int] になります。また、平坦化が行われるとき、Nil は削除されるので、makeNewState の返り値は新しい State を格納したリストになります。
それでは、実際に試してみましょう。
scala> import tumiki._
import tumiki._
scala> makeNewState((List("red", "blue", "green"), Nil, Nil))
val res0: List[tumiki.State] = List((List(blue, green),List(red),List()),
(List(blue, green),List(),List(red)))
scala> makeNewState((List("red"), List("blue"), List("green")))
val res1: List[tumiki.State] = List((List(),List(red, blue),List(green)),
(List(),List(blue),List(red, green)),
(List(blue, red),List(),List(green)),
(List(red),List(),List(blue, green)),
(List(red),List(green, blue),List()),
(List(green, red),List(blue),List()))
最初の例は、積木がある場所が x しかないので、生成される State は、red を y に移動したものと、z に移動したものの 2 つになります。次の例は x, y, z に積木があるので、生成される新しい State は 6 通りになります。
●深さ優先探索
あとのプログラムは簡単です。深さ優先探索は次のようになります。
リスト : 深さ優先探索
// 移動手順の表示
def printMove(move: List[State]): Unit = {
for (st <- move) println(st)
}
def depthFirstSearch(start: State, goal: State): Unit = {
def dfs(move: List[State]): Unit = {
val st = move.head
if (st == goal) {
printMove(move.reverse)
throw new Exception("Found")
} else {
for (newSt <- makeNewState(st) if (!(move contains newSt))) dfs(newSt::move)
}
}
try { dfs(List(start)) } catch { case e:Exception => () }
}
実際の処理は局所関数 dfs で行います。引数 move は State を格納したリストです。これで移動手順を表すことにします。move の先頭要素が現在の状態を表します。それを変数 st にセットして、goal に到達したかチェックします。そうであれば、printMove で手順を表示して、探索を終了するため大域脱出します。
goal に到達していない場合は、makeNewState で新しい局面を生成し、for 式で局面を順番に取り出して変数 newSt にセットします。そして、newSt が移動手順 move の中に含まれていなければ、newSt を move に追加して dfs を再帰呼び出しします。あとは、try 式の中で dfs を呼び出して catch で大域脱出を捕捉します。
それでは実行してみましょう。
scala> val start: State = (List("red", "blue", "green"), Nil, Nil)
val start: tumiki.State = (List(red, blue, green),List(),List())
scala> val goal: State = (Nil, Nil, List("red", "blue", "green"))
val goal: tumiki.State = (List(),List(),List(red, blue, green))
scala> depthFirstSearch(start, goal)
(List(red, blue, green),List(), List())
(List(blue, green), List(red), List())
(List(green), List(blue, red), List())
(List(), List(green, blue, red),List())
(List(), List(blue, red), List(green))
(List(blue), List(red), List(green))
(List(), List(red), List(blue, green))
(List(red), List(), List(blue, green))
(List(), List(), List(red, blue, green))
移動手順は手作業で直しています。興味のある方は、移動手順をきれいに表示するようにプログラムを修正してみてください。スタートからゴールまで 8 手かかっています。もちろん、これは最短手順ではありません。
●幅優先探索
次は幅優先探索で解いてみましょう。
リスト : 幅優先探索
def breadthFirstSearch(start: State, goal: State): Unit = {
val q = new Queue[List[State]]
var states = List(start)
q.enqueue(List(start))
while (!q.isEmpty()) {
val move = q.dequeue()
val st = move.head
if (st == goal) {
printMove(move.reverse)
return
}
for (newSt <- makeNewState(st) if (!(states contains newSt))) {
states = newSt::states
q.enqueue(newSt::move)
}
}
}
プログラムは経路の探索とほぼ同じです。ただし、一つだけ異なるところがあります。幅優先探索で最短手順を求める場合、すべての手順を記憶しておく必要はありません。n 手目の移動で作られた局面が、n 手目以前の局面で出現しているのであれば、n 手より短い手数で到達する移動手順があるはずです。したがって、この n 手の手順を記憶しておく必要はなく、探索を続けるのは今までに出現していない新しい局面だけになります。
新しく出現した局面は変数 states のリストに格納します。最初は、start の局面を格納しておきます。makeNewState で生成した局面 newSt が states にあるか contains で探索して、見つからなければ新しい局面です。states に newSt を追加して、キューに newSt::move を追加します。
それでは実行してみましょう。
scala> breadthFirstSearch(start, goal) (List(red, blue, green),List(), List()) (List(blue, green), List(red), List()) (List(green), List(blue, red),List()) (List(), List(blue, red),List(green)) (List(), List(red), List(blue, green)) (List(), List(), List(red, blue, green))
スタートからゴールまで 5 手で到達しました。これが最短手数になります。
●反復深化
最後に反復深化のプログラムを作ります。
リスト : 反復深化
def idSearch(start: State, goal: State): Unit = {
def dfs(limit: Int, move: List[State]): Unit = {
if (move.length == limit) {
if (move.head == goal) {
printMove(move.reverse)
throw new Exception("Found")
}
} else {
for (newSt <- makeNewState(move.head)) dfs(limit, newSt::move)
}
}
//
try {
for (i <- 1 to 10) dfs(i, List(start))
} catch {
case e:Exception => ()
}
}
このプログラムも経路の探索とほぼ同じです。難しいところは特にないと思います。
それでは実行してみましょう。
scala> idSearch(start, goal) (List(red, blue, green),List(), List()) (List(blue, green), List(red), List()) (List(green), List(blue, red),List()) (List(), List(blue, red),List(green)) (List(), List(red), List(blue, green)) (List(), List(), List(red, blue, green))
幅優先探索と同じく、5 手でゴールに到達しました。このように、反復深化でも最短手数の手順を求めることができます。
●プログラムリスト
//
// tumiki.scala : 積木の移動
//
// Copyright (C) 2014-2021 Makoto Hiroi
//
import dlist._
object tumiki {
// 局面 (x, y, z)
type State = (List[String], List[String], List[String])
// x -> y
def moveXtoY(st: State): List[State] = st match {
case (x::xs, ys, zs) => List((xs, x::ys, zs))
case _ => Nil
}
// x -> z
def moveXtoZ(st: State): List[State] = st match {
case (x::xs, ys, zs) => List((xs, ys, x::zs))
case _ => Nil
}
// y -> x
def moveYtoX(st: State): List[State] = st match {
case (xs, y::ys, zs) => List((y::xs, ys, zs))
case _ => Nil
}
// y -> z
def moveYtoZ(st: State): List[State] = st match {
case (xs, y::ys, zs) => List((xs, ys, y::zs))
case _ => Nil
}
// z -> x
def moveZtoX(st: State): List[State] = st match {
case (xs, ys, z::zs) => List((z::xs, ys, zs))
case _ => Nil
}
// z -> y
def moveZtoY(st: State): List[State] = st match {
case (xs, ys, z::zs) => List((xs, z::ys, zs))
case _ => Nil
}
// 移動関数表
val moveFunc = List(moveXtoY _, moveXtoZ _, moveYtoX _,
moveYtoZ _, moveZtoY _, moveZtoX _)
// 新しい局面の生成
def makeNewState(st: State): List[State] =
moveFunc.flatMap((f:State => List[State]) => f(st))
// 移動手順の表示
def printMove(move: List[State]): Unit = {
for (st <- move) println(st)
}
// 深さ優先探索
def depthFirstSearch(start: State, goal: State): Unit = {
def dfs(move: List[State]): Unit = {
val st = move.head
if (st == goal) {
printMove(move.reverse)
throw new Exception("Found")
} else {
for (newSt <- makeNewState(st) if (!(move contains newSt))) dfs(newSt::move)
}
}
try { dfs(List(start)) } catch { case e:Exception => () }
}
// 幅優先探索
def breadthFirstSearch(start: State, goal: State): Unit = {
val q = new Queue[List[State]]
var states = List(start)
q.enqueue(List(start))
while (!q.isEmpty()) {
val move = q.dequeue()
val st = move.head
if (st == goal) {
printMove(move.reverse)
return
}
for (newSt <- makeNewState(st) if (!(states contains newSt))) {
states = newSt::states
q.enqueue(newSt::move)
}
}
}
// 反復深化
def idSearch(start: State, goal: State): Unit = {
def dfs(limit: Int, move: List[State]): Unit = {
if (move.length == limit) {
if (move.head == goal) {
printMove(move.reverse)
throw new Exception("Found")
}
} else {
for (newSt <- makeNewState(move.head)) dfs(limit, newSt::move)
}
}
//
try {
for (i <- 1 to 10) dfs(i, List(start))
} catch {
case e:Exception => ()
}
}
}
改訂 2021 年 4 月 4 日
(1) 33 穴英国盤
(2) Hoppers
図 : ペグ・ソリテア
図 : Hoppers