算法解《机械迷城》游戏三：扳手关水管
一、游戏介绍
小萝卜头来到了下水道，下水道里面有一些错综复杂的水管，如图所示（红色箭头表示进水口和出水口）：
其中出水口的水流进了蓄水池，而小萝卜头打算进入蓄水池里，所以只能想办法关闭这个出水口。
水管上面总共有11个阀门，而下水道里面只能找到3个扳手，每个扳手能关掉一个阀门。
那么问题来了：你能帮小萝卜头关闭3个阀门，让出水口流不出水吗？
二、游戏分析
我们遇到了新类型的游戏，这个游戏可以看成一个连通图，阀门就是连通图的节点，那么问题可以转化为：如何通过去掉3个节点，让进水口和出水口不相通?
如果用X来表示进水口，用Y表示出水口，用A ~ K来标记11个阀门，结果如图所示：
那么如何来构建这张连通图呢？
首先要找出图中所有相连的节点，可以用元组(X, Y)来表示节点X和节点Y相连。
找出所有两两相连的节点后，就可以用这些相连的节点来构建一个连通图。
以进水口节点X为例，与节点X相连的节点为[G, H, K, B]，如图所示：
那么可以用一个元组数组来表示节点X的连通关系：
1
2
3
| link_valves = [
('X', 'G'), ('X', 'H'), ('X', 'K'), ('X', 'B'),
]
|
假如接下来要寻找节点G的连通关系，由于G与X已经相连了，已经存在(X, G)，那么连通数组就可以不必加入(G, X)。
当然，如果要加入也是没关系的，不加入的话看起来比较简洁。
由于水管错综复杂，要找出所有节点的连通关系是一件很麻烦的事情，所以只能使用人工智能来寻找了。
这是一个纯体力活，耗费了两个打怪的时间才找完所有节点，节点的连通数组如下所示：
1
2
3
4
5
6
7
8
| link_valves = [
('X', 'G'), ('X', 'H'), ('X', 'K'), ('X', 'B'),
('Y', 'C'), ('Y', 'D'), ('Y', 'E'), ('Y', 'J'),
('Y', 'B'), ('Y', 'H'), ('Y', 'I'),
('A', 'D'), ('A', 'C'), ('A', 'I'), ('A', 'J'),
('A', 'F'), ('A', 'G'),
('B', 'I'), ('F', 'K'),
]
|
三、游戏编写
1、阀门类的实现
由于阀门节点要记录与其相连的阀门，所以不能够用基础数据类型来表示，定义一个阀门类比较方便。
阀门类使用阀门名字来初始化（阀门名字为英文字母）：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
|
class Valve:
"""阀门类
Attributes:
name: 阀门名字
closed: 是否关闭
outlets: 连接的阀门对象数组
"""
def __init__(self, name):
"""使用阀门名字初始化阀门
Args:
name: 阀门名字
"""
self.name = name
self.closed = False
self.outlets = []
def link(self, valve):
"""连接某个阀门
Args:
valve: 阀门对象
"""
self.outlets.append(valve)
def show(self):
"""打印阀门名和连接的阀门
Print: "阀门名(是否关闭) : [连接的阀门名数组]"
"""
outlet_names = [x.name for x in self.outlets]
print("%s(%d) : %s"%(self.name, self.closed, outlet_names))
valve_a = Valve('A')
valve_b = Valve('B')
valve_a.link(valve_b)
valve_a.show()
|
测试代码将阀门B与阀门A相连，执行结果为：
进水口和出水口可以视为特殊的阀门，即不可关闭，永远可以让水通过。
2、游戏类的实现
游戏类可以维护一个字典，以便快速根据阀门名来找到阀门对象。
新建一个游戏类，用相连的阀门节点数组初始化游戏：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
|
class Game:
"""扳手关水管游戏
Attributes:
valve_dict: 存放阀门的字典{阀门名:阀门对象}
water_inlet: 入水口
water_outlet: 出水口
"""
def __init__(self, link_valves):
"""使用连接的阀门数组初始化游戏
Args:
link_valves: 相连的阀门数组
"""
self.valve_dict = {}
for link_valve in link_valves:
from_name, to_name = link_valve
self.add_link_valve(from_name, to_name)
self.water_inlet = self.valve_dict['X']
self.water_outlet = self.valve_dict['Y']
def add_link_valve(self, from_name, to_name):
"""添加相连的阀门
Args:
from_name: 起始阀门名
to_name: 目的阀门名
"""
from_valve = self.valve_dict.get(from_name)
if not from_valve:
from_valve = Valve(from_name)
self.valve_dict[from_name] = from_valve
to_valve = self.valve_dict.get(to_name)
if not to_valve:
to_valve = Valve(to_name)
self.valve_dict[to_name] = to_valve
from_valve.link(to_valve)
to_valve.link(from_valve)
def show(self):
"""打印出所有阀门的值"""
for key in self.valve_dict:
valve = self.valve_dict[key]
valve.show()
link_valves = [
('X', 'G'), ('X', 'H'), ('X', 'K'), ('X', 'B'),
('Y', 'C'), ('Y', 'D'), ('Y', 'E'), ('Y', 'J'),
('Y', 'B'), ('Y', 'H'), ('Y', 'I'),
('A', 'D'), ('A', 'C'), ('A', 'I'), ('A', 'J'),
('A', 'F'), ('A', 'G'),
('B', 'I'), ('F', 'K'),
]
game = Game(link_valves)
game.show()
|
代码执行结果为：
1
2
3
4
5
6
7
8
9
10
11
12
13
| A(0) : ['D', 'C', 'I', 'J', 'F', 'G']
C(0) : ['Y', 'A']
B(0) : ['X', 'Y', 'I']
E(0) : ['Y']
D(0) : ['Y', 'A']
G(0) : ['X', 'A']
F(0) : ['A', 'K']
I(0) : ['Y', 'A', 'B']
H(0) : ['X', 'Y']
K(0) : ['X', 'F']
J(0) : ['Y', 'A']
Y(0) : ['C', 'D', 'E', 'J', 'B', 'H', 'I']
X(0) : ['G', 'H', 'K', 'B']
|
如果要判断两个节点是否相通，需要使用递归来进行判断。
由于我们目前已经知道进水口X和出水口Y是相连通的，但是阀门X连接的节点为['G', 'H', 'K', 'B']，里面没有Y。所以要遍历每一个连接的阀门，判断某个阀门是否和Y连通。
假如能够找到某条相通的路径，例如X -> B -> Y，就说明X和Y是相通的。如果遍历完所有路径都找不到，就说明两个阀门不相通。
判断两个阀门是否相通的深度优先遍历算法如下所示：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
|
class Game:
def is_connected(self, from_valve, to_valve):
"""判断两个阀门是否相通
Args:
from_valve: 起始阀门
to_valve: 目的阀门
Returns: 是否相通
"""
visited = set()
def dfs(valve):
"""使用DFS判断
Args:
valve: 阀门对象
Returns: 是否相通
"""
if valve.closed:
return False
if valve == to_valve:
return True
if valve.name in visited:
return False
visited.add(valve.name)
for valve in valve.outlets:
if dfs(valve):
return True
if from_valve.closed or to_valve.closed:
return False
return dfs(from_valve)
print(game.is_connected(game.water_inlet, game.water_outlet))
|
执行结果为：
说明进水口和出水口是相通的。
四、游戏解法
首先实现一下判断游戏是否完成的方法，如果进水口和出水口不相通，就相当于出水口被关闭了，那么可以写出下面的方法：
1
2
3
4
5
6
7
8
|
class Game:
def is_done(self):
"""判断是否完成游戏
Returns: 是否完成游戏
"""
return not self.is_connected(self.water_inlet, self.water_outlet)
|
这个游戏可以使用回溯算法来求解答案，回溯算法跟深度优先搜索算法差不多。
如果广度优先搜索算法是孙悟空用分身走迷宫的话，那么深度优先搜索算法就是猪八戒走迷宫，猪八戒不能分身，只能先沿着迷宫某个岔路口一直走到最深处（深度优先的含义），如果发现是死路，再选择别的岔路口去尝试。
同理，这个游戏先尝试关闭前3个阀门，判断是否完成游戏。如果没完成游戏，就把第3个阀门打开，关闭第4个阀门，这样一直尝试下去，直到游戏完成为止。
回溯算法如下所示：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
|
class Game:
def backtrack(self):
"""使用回溯求解答案
Returns: 是否找到了答案
"""
if len(self.ops) == 3:
return self.is_done()
valve_names = [
'A', 'B', 'C', 'D', 'E', 'F',
'G', 'H', 'I', 'J', 'K',
]
for valve_name in valve_names:
valve = self.valve_dict[valve_name]
if valve.closed:
continue
valve.closed = True
self.ops.append(valve.name)
if self.backtrack():
return True
valve.closed = False
self.ops.pop()
def solve(self):
"""调用回溯算法求解答案"""
if self.backtrack():
print(self.ops)
game.solve()
|
执行结果为：
将[A, B, H]这3个阀门关闭的话，就能完成游戏，如图所示：
五、完整代码
完整的代码见：https://github.com/poboke/Machinarium
