怎么用一个容量为 3 公斤的桶和一个容量 5 公斤的桶称量出 4 公斤量的水?
题目:怎么用一个容量为 3 公斤的桶和一个容量 5 公斤的桶称量出 4 公斤量的水?
分析
设两个桶分别为 A 和 B,容量分别为 M 和 N。目标为任一桶的当前盛水容量为 G。
开始状态: 两个桶均为空。
过程: 桶没有刻度,针对这两个桶每次所能完成的动作只能是以下 6 种之一:
- 把 A 桶的水清空;
- 把 B 桶的水清空;
- 把 A 装潢水;
- 把 B 装满水;
- 把 A 的水倒入 B;
- 把 B 的水倒入 A。
结束状态: 其中一个桶装入的水容量为 G。
完整过程: 从开始状态开始,每次可以选择一个动作之一,然后判断是否到达结束状态。
很显然,从开始到结束的这些状态,应该构成一个图。图的顶点就是各个状态,图的边就是动作之一。 我们要做的,就是从图的开始状态顶点找到所有能到达结束状态顶点的所有路径。我相信你的脑海里面已经构造出这个图了。
通常,我们把这种问题称作是关于图的状态空间搜索问题,而采用的算法则可以是广度优先搜索。
实现
下面开始写算法实现,不要忘记广度优先搜索算法怎么写就好。
Go Playground: https://play.golang.org/p/_xK0_vOvmQi
package main
import "fmt"
// State 状态,构成图的顶点
type State struct {
// A、B 两桶当前装水的容量
a, b int
// 遍历时记录父顶点,即记住路径
parent *State
// 所作的动作
action string
}
const (
// M 为 A 桶的最大容量
M = 3
// N 为 B 桶的最大容量
N = 5
// G 为想要得到的容量
G = 4
)
const (
actionFillA = `Fill A`
actionFillB = `Fill B`
actionClearA = `Clear A`
actionClearB = `Clear B`
actionFillAWithB = `Fill A With B`
actionFillBWithA = `Fill B With A`
)
var (
// A 桶的范围是 [0,M],B 桶的范围是 [0,N]
// 所以去重后的状态总数是 (M+1)*(N+1)
maxStates = (M + 1) * (N + 1)
// 状态集合。
states = make([]*State, 0, maxStates)
// 已访问的状态。
// 这里用一维数组,方便初始化
visited = make([]bool, maxStates)
)
// 把未访问过的状态加入到待遍历队列
func tryAddState(a, b int, parent *State, action string) {
p := (N+1)*a + b
if visited[p] {
return
}
states = append(states, &State{
a: a,
b: b,
parent: parent,
action: action,
})
visited[p] = true
}
// 到达结束状态时递归回溯并显示出路径
func backtrace(s *State) {
if s != nil {
backtrace(s.parent)
fmt.Printf("(%d,%d) %s\n", s.a, s.b, s.action)
}
}
func min(a, b int) int {
if a < b {
return a
}
return b
}
func main() {
// 加入开始状态,准备广度优先搜索遍历
tryAddState(0, 0, nil, `Initialize`)
// 遍历所有状态(不要使用 range,因为 range 是立即求值)
for i := 0; i < len(states); i++ {
s := states[i]
// 如果到达结束条件
if s.a == G || s.b == G {
// 回溯并输出当前路径
backtrace(s)
fmt.Println()
continue
}
// 如果没达到结束条件,把当前顶点的所有出度加入列表
tryAddState(0, s.b, s, actionClearA)
tryAddState(s.a, 0, s, actionClearB)
tryAddState(M, s.b, s, actionFillA)
tryAddState(s.a, N, s, actionFillB)
// A 最多可以给 B 的量
t1 := min(s.a, N-s.b)
// B 最多可以给 A 的量
t2 := min(s.b, M-s.a)
tryAddState(s.a+t2, s.b-t2, s, actionFillAWithB)
tryAddState(s.a-t1, s.b+t1, s, actionFillBWithA)
}
fmt.Printf("Processed %d states\n", len(states))
}
运行输出结果:
(0,0) Initialize
(0,5) Fill B
(3,2) Fill A With B
(0,2) Clear A
(2,0) Fill A With B
(2,5) Fill B
(3,4) Fill A With B
(0,0) Initialize
(3,0) Fill A
(0,3) Fill B With A
(3,3) Fill A
(1,5) Fill B With A
(1,0) Clear B
(0,1) Fill B With A
(3,1) Fill A
(0,4) Fill B With A
Processed 16 states
可以看到,总共有 2 种答案。