Search Problem
所謂search problem就是在一個問題的可能解決地圖中，找到一條解決路徑，最好也是optimal的解決路徑，Scala課程中以倒水問題為例，而功課則要學生找出Bloxorz這個遊戲的解決路徑。
倒水問題如下：
有n個已知容量的空杯子，試求最少步驟能裝出x容量的水？我們能對杯子做的動作有:
1. 倒滿
2. 清空
3. 從a杯倒到b杯
Modeling States
這個跟我之前上Berkely AI課程的小精靈問題一樣，我們先把n個空杯子用一個Vector[Int]來代表，任何Vector[Int]可能的值就是一個state，並且先列出所有可以走的actions組合，因為待會就要在search space中利用這些actions來建立search path:
class Pouring(capacity: Vector[Int]) { //各種容量的杯子
//states
type State = Vector[Int]
val initalState = capacity map (_ => 0) //一開始所有杯子是空的
//move types
trait Move
case class Empty(glass: Int) extends Move
case class Fill(glass: Int) extends Move
case class Pour(from: Int, to: Int) extends Move
//all indices
val glasses = 0 until capacity.length
//all possible moves/actions
val moves =
(for(g <- glasses) yield Empty(g)) ++
(for(g <- glasses) yield Fill(g)) ++
(for(g1 <- glasses; g2 <- glasses; if g1 != g2)
yield Pour(g1,g2))
}
Modeling Moves
我們會從initial state開始長出三個可能的move path，分別是Empty, Fill, Pour，所以我們還需要知道從某個state經過一個move之後，會變成哪一個state? 我們在trait Move中加入一個change method：
(這邊的邏輯比較不直覺，我會寫成State有一個change(move:Move)的方法，而不是在Move class中寫一個change(state:State))
//move types
trait Move {
def change(state:State):State
}
case class Empty(glass: Int) extends Move {
override def change(state: State): State = state updated(glass, 0)
}
case class Fill(glass: Int) extends Move {
override def change(state: State): State = state updated(glass, capacity(glass))
}
case class Pour(from: Int, to: Int) extends Move{
override def change(state: State): State = {
val amount = math.min( state(from), capacity(to) - state(to) )
(state updated(from, state(from)-amount)) updated (to, state(to) + amount)
}
}
collection的updated method是一個immutable method，會產生一個新的collection，但是在某個index的value不同而已。
Modeling Paths
我們接著要來model path，某一條path其實就是每次move的歷史，我們把最新的move放在list head，有了這個history，我們可以利用每個move間的change來計算出最後的end state:
//Pathsclass Path(history:List[Move]) {
def extend(move:Move) = (new Path(move::history))
override def toString = (history.reverse mkString(" ")) + "-->" + endState
def endState: State = trackState(history)
private def trackState(xs: List[Move]): State = xs match {
case Nil => initalState case move::xs1 => move change trackState(xs1)
}
}
val initialPath = new Path(Nil)
上面trackState會先recursively抵達Nil，然後把initialState當作參數傳給第一個move的change method:
(lastMove change ...... (move2 chage (move1 change initialState)))
所以這是一個foldRight operation，我們可以把endState改寫成：
def endState: State = history.foldRight(initalState)( _ change _ )
Search space exploration
我們有了所有的models，現在可以開始做Breadth-first search。BFS search的過程類似從洋蔥的核心(initalState)，一層層往外extend出同樣長度的path，對洋蔥中的某一層來說，已經長出了一些paths，接下來要長出下一層，這邊就要用到Streams：
def from(paths:Set[Path]): Stream[Set[Path]] =
if (paths.isEmpty) Stream.empty
else {
val more:Set[Path] = for {
path:Path <- paths
extendedPath:Path <- moves map(x => path.extend(x))
} yield extendedPath
paths #:: from(more) //union the extended paths }
val pathSets = from(Set(initialPath))
用set的原因是，重複的path對我們來說沒有意義。用stream的原因則是要控制exploration深度，如果用list的話，必須要加上搜尋深度的限制才行，否則變成無窮迴圈。
開始搜尋解答
假設有兩個容量為4和6的空瓶：
val problem = new Pouring(Vector(4,6))
problem.moves
所有的可能moves如下：
res0: IndexedSeq[problem.Move] = Vector(Empty(0), Empty(1), Fill(0), Fill(1), Pour(0,1), Pour(1,0))
搜尋一層可能的paths，
problem.pathSets.take(1).toList
res1: List[Set[problem.Path]] = List(Set(-->Vector(0, 0)))
搜尋二層可能的paths，
problem.pathSets.take(2).toList
res1: List[Set[problem.Path]] = List(
Set(-->Vector(0, 0)),
Set(
Pour(0,1)-->Vector(0, 0),
Fill(0)-->Vector(4, 0),
Empty(1)-->Vector(0, 0),
Empty(0)-->Vector(0, 0),
Pour(1,0)-->Vector(0, 0),
Fill(1)-->Vector(0, 6))
)
我們現在可以寫這個倒水問題的solution method:
def solution(target:Int): Stream[Path] =
for {
pathSet <- pathSets path <- pathSet
if path.endState contains target
} yield path
這個邏輯就是stream神奇的地方，pathSets是一個Stream[Set[Path]] type，本來應該是不會evaluate，但是由於stream的head是strict evaluation，所以head一定會evaluate，直到遇到第一個滿足if條件為止，此時stream就不會在evaluate下去。
深度不能確定是多少，要看滿足第一個if的path何時出現。This is not an optimized solution, might be very slow and not optimal!
total source code for now:
class Pouring(capacity: Vector[Int]) { //各種容量的杯子
//states type State = Vector[Int]
val initalState = capacity map (_ => 0) //一開始所有杯子是空的
//move types trait Move {
def change(state:State):State }
case class Empty(glass: Int) extends Move {
override def change(state: State): State = state updated(glass, 0)
}
case class Fill(glass: Int) extends Move {
override def change(state: State): State = state updated(glass, capacity(glass))
}
case class Pour(from: Int, to: Int) extends Move{
override def change(state: State): State = {
val amount = math.min( state(from), capacity(to) - state(to) )
(state updated(from, state(from)-amount)) updated (to, state(to) + amount)
}
}
//all indices
val glasses = 0 until capacity.length
//all possible moves/actions
val moves:IndexedSeq[Move] =
(for(g <- glasses) yield Empty(g)) ++
(for(g <- glasses) yield Fill(g)) ++
(for(g1 <- glasses; g2 <- glasses; if g1 != g2)
yield Pour(g1,g2))
//Paths (我們記錄所有的moves，List head是最後的move)
class Path(history:List[Move]) {
def extend(move:Move) = (new Path(move::history))
def endState: State = history.foldRight(initalState)( _ change _ )
override def toString = (history.reverse mkString(" ")) + "-->" + endState
}
val initialPath = new Path(Nil)
def from(paths:Set[Path]): Stream[Set[Path]] =
if (paths.isEmpty) Stream.empty
else {
val more:Set[Path] = for {
path:Path <- paths
extendedPath:Path <- moves map(x => path.extend(x))
} yield extendedPath
paths #:: from(more) //union the extended paths
}
val pathSets = from(Set(initialPath))
def solution(target:Int): Stream[Path] =
for {
pathSet <- pathSets
path <- pathSet
if path.endState contains target
} yield path
}
