算法解《机械迷城》游戏三:扳手关水管

时间:2020-06-07 | 分类:个人日志,学习园地 | 浏览:351 | 评论:0 | 发表评论

一、游戏介绍

小萝卜头来到了下水道,下水道里面有一些错综复杂的水管,如图所示(红色箭头表示进水口和出水口):

image

其中出水口的水流进了蓄水池,而小萝卜头打算进入蓄水池里,所以只能想办法关闭这个出水口。
水管上面总共有10个阀门,而下水道里面只能找到3个扳手,每个扳手能关掉一个阀门。

那么问题来了:你能帮小萝卜头关闭3个阀门,让出水口流不出水吗?


二、游戏分析

我们遇到了新类型的游戏,这个游戏可以看成一个连通图,阀门就是连通图的节点,那么问题可以转化为:如何通过去掉3个节点,让进水口和出水口不相通?
如果用X来表示进水口,用Y表示出水口,用A~K来标记10个阀门,结果如图所示:

image

那么如何来构建这张连通图呢?
首先要找出图中所有相连的节点,可以用元组(X, Y)来表示节点X和节点Y相连。
找出所有两两相连的节点后,就可以用这些相连的节点来构建一个连通图。

以进水口节点X为例,与节点X相连的节点为[G, H, K, B],如图所示:

image

那么可以用一个元组列表来表示节点X的连通关系:

link_valves = [
    ('X', 'G'), ('X', 'H'), ('X', 'K'), ('X', 'B'),
]

假如接下来要寻找节点G的连通关系,由于GX已经相连了,已经存在(X, G),那么连通列表就可以不必加入(G, X)
当然,如果要加入也是没关系的,不加入的话看起来比较简洁。

由于水管错综复杂,要找出所有节点的连通关系是一件很麻烦的事情,所以只能使用人工智能来寻找了。
这是一个纯体力活,耗费了两个打怪的时间才找完所有节点,节点的连通列表如下所示:

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、阀门类的实现

由于阀门节点要记录与其相连的阀门,所以不能够用基础数据类型来表示,定义一个阀门类比较方便。
阀门类使用阀门名字来初始化(阀门名字为英文字母):

#coding:utf-8

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相连,执行结果为:

A(0) : ['B']

进水口和出水口可以视为特殊的阀门,即不可关闭,永远可以让水通过。

2、游戏类的实现

游戏类可以维护一个字典,以便快速根据阀门名来找到阀门对象。
新建一个游戏类,用相连的阀门节点列表初始化游戏:

#coding:utf-8

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()

代码执行结果为:

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,就说明XY是相通的。如果遍历完所有路径都找不到,就说明两个阀门不相通。
判断两个阀门是否相通的深度优先遍历算法如下所示:

#coding:utf-8

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))

执行结果为:

True

说明进水口和出水口是相通的。


四、游戏解法

首先实现一下判断游戏是否完成的方法,如果进水口和出水口不相通,就相当于出水口被关闭了,那么可以写出下面的方法:

#coding:utf-8

class Game:
    def is_done(self):
        """判断是否完成游戏
        Returns: 是否完成游戏
        """
        return not self.is_connected(self.water_inlet, self.water_outlet)

这个游戏可以使用回溯算法来求解答案,回溯算法跟深度优先搜索算法差不多。
如果广度优先搜索算法是孙悟空用分身走迷宫的话,那么深度优先搜索算法就是猪八戒走迷宫,猪八戒不能分身,只能先沿着迷宫某个岔路口一直走到最深处(深度优先的含义),如果发现是死路,再选择别的岔路口去尝试。

同理,这个游戏先尝试关闭前3个阀门,判断是否完成游戏。如果没完成游戏,就把第3个阀门打开,关闭第4个阀门,这样一直尝试下去,直到游戏完成为止。
回溯算法如下所示:

#coding:utf-8

class Game:

    def backtrack(self):
        """使用回溯求解答案
        Returns: 是否找到了答案
        """
        # 如果关掉了3个阀门,就验证游戏结果
        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']

[A, B, H]这3个阀门关闭的话,就能完成游戏,如图所示:

image


六、完整代码

完整的代码见:https://github.com/poboke/Machinarium

标签: , ,
本文链接: 算法解《机械迷城》游戏三:扳手关水管
版权所有: 破博客, 转载请注明本文出处。

发表评论

您的昵称: *

您的邮箱: * (显示gravatar头像)

联系方式: