“Ticket to Ride”桌游灰色路线逻辑

Question

我喜欢玩《车票之旅》，所以我决定用Python实现游戏逻辑的一部分，作为一个额外的编程项目。游戏板基本上是一个加权的多重图，所以用NetworkX来复制游戏的基本结构非常简单。

我现在遇到的一个问题是，分析玩家手中拥有的火车卡片是否能走出某条特定的路径。我觉得这更像是一个数学问题，而不是纯粹的编程问题，我可能可以拼凑出一个暴力破解的方法来解决，但我想应该有更高效的办法。

对于那些不知道这个游戏的人：在任何时候，每个玩家都有一定数量的火车卡，颜色有八种，还有一种特殊的“机车”类别，作为万能卡。这些颜色对应于游戏板上的火车线路颜色（如图所示），除了灰色线路，灰色线路可以使用任何颜色，只要该段的所有车厢颜色相同。（还有一些涉及隧道和渡轮的特殊情况，但我们暂时不讨论这些。）

根据现在的代码，我可以找到两个城市之间的所有路径，并返回每条路径需要多少张每种颜色的火车卡，除非路径涉及灰色段。我先处理非灰色段，因为它们更简单——要么你有足够的红色/绿色/蓝色卡来覆盖路径中的每个红色/绿色/蓝色段，要么没有。对于灰色段，因为你可以选择任何颜色来使用，所以就复杂一些。

对于只有一个灰色段的路径，还是比较简单的——要么你有足够的某种颜色的卡来填补它，要么没有。然而，对于多个灰色段，就可能出现选择第一个段的颜色会导致无法完成第二或第三个段的情况。

举个例子，假设一个玩家的卡片库存是4张红色、2张绿色、3张蓝色，我们要弄清楚他是否能从巴黎到维也纳。看着游戏板，很容易发现这个卡片组合的唯一可能路线是：巴黎 --(3灰色)--> 苏黎世 --(2绿色)--> 威尼斯 --(2灰色)--> 扎格雷布 --(2灰色)--> 维也纳。我的算法从绿色段开始，分配了两张绿色卡。然后它需要决定如何使用剩下的4张红色和3张蓝色卡来覆盖长度为3、2和2的灰色段。

答案当然是用3张蓝色卡在巴黎和苏黎世之间，威尼斯到扎格雷布和扎格雷布到维也纳各用2张红色卡。但如何写出一个通用的算法来解决这个问题，以应对涉及更多颜色和更多段的更复杂情况呢？

我现在的代码看起来是这样的：

def can_afford(path, cards):
    grays = list()
    for segment in path:
        if segment.color == 'Gray':
            grays.append(segment)
        else:
            if cards.get(segment.color, 0) >= segment.weight:
                cards[segment.color] -= segment.weight
            else:
                return False
    for gray in grays:
        # Halp!
        pass
    return True

（“weight”是段的长度，以火车车厢为单位。）

我觉得这里面潜藏着一个非常简单的解决方案，但我就是想不出来。有什么想法吗？

Answer 1

另一种处理这个问题的方法是构建一个搜索树，具体步骤如下：

• 每个节点上标记着一个城市名、一组卡片和一些火车。这代表着某条路线的起始城市，以及你手上可以使用的卡片和火车。

• 每个节点的子节点对应着你可以从父节点到达的城市，同时也显示了在完成从父节点到这个子节点的路线后，你手中剩下的卡片和火车。

举个例子，树的根节点可以是蒙特利尔，手上有4张蓝卡、1张白卡和1张万能卡，还有45个火车。根节点的子节点可能是：

• 多伦多，（1张蓝卡，1张白卡，1张万能卡），42个火车 # 使用了3张蓝卡
• 多伦多，（2张蓝卡，1张白卡），42个火车 # 使用了2张蓝卡和1张万能卡
• 纽约，（1张蓝卡，1张白卡，1张万能卡），42个火车 # 使用了3张蓝卡
• 纽约，（2张蓝卡，1张白卡），43个火车 # 使用了2张蓝卡和1张万能卡
• 波士顿，（3张蓝卡，1张白卡），43个火车 # 使用了1张蓝卡和1张万能卡
• 波士顿，（2张蓝卡，1张白卡，1张万能卡），43个火车 # 使用了2张蓝卡
• 波士顿，（4张蓝卡），43个火车 # 使用了1张白卡和1张万能卡

现在，你只需要在这个树上进行深度优先搜索，看看能否到达目标城市。你在搜索树上添加的边（也就是路线）受限于你手上的卡片（比如，你不能直接从蒙特利尔到索尔特·圣·玛丽，因为你手上没有足够的6张黑卡或万能卡）和剩余的火车数量（如果你只剩下3张卡，就不能从卡尔加里到西雅图）。

Answer 2

这个问题和一些其他问题有点相似，比如箱子装物、子集求和等。提到的这些问题以及许多相关的问题都是NP完全的，这意味着可能没有（已知的）高效算法来解决这个问题，但我现在无法证明这一点——这只是我的一种直觉。我会再想想这个问题，然后更新我的回答。

Answer 3

正如Daniel Brückner所说，把卡片的颜色分配给灰色区域的问题，实际上和一个叫做装箱问题是一样的。在这个问题中，彩色卡片就像是箱子，而灰色区域就像是需要放进去的物品。

现在，装箱问题是个NP难题，但在这种情况下并不算糟糕，因为我们可以用伪多项式时间来解决这个问题（也就是说，解决的时间和箱子的大小成多项式关系），通过动态规划的方法来实现，这对于你的应用来说应该是足够的，因为箱子的大小是由游戏中的卡片数量限制的。下面是一个使用@functools.lru_cache装饰器来记忆化的装箱问题的示例实现：

from functools import lru_cache

@lru_cache(maxsize=None)
def packing(bins, objects):
    """Return a packing of objects into bins, or None if impossible. Both
    arguments are tuples of numbers, and the packing is returned in
    the form of a list giving the bin number for each object.

    >>> packing((4,5,6), (6,5,4))
    [2, 1, 0]
    >>> packing((4,5,6), (1,1,2,4,5))
    [0, 0, 0, 1, 2]

    """
    if not objects:
        return []
    o = objects[0]
    rest = objects[1:]
    for i, b in enumerate(bins):
        if o <= b:
            p = packing(bins[:i] + (b - o,) + bins[i+1:], rest)
            if p is not None:
                return [i] + p
    return None

这个方法可以用来判断在《票到达》游戏中是否可以走某条路径：

def can_afford(path, cards):
    """Return True if path can be followed using cards, False if not.
    cards might be updated, so pass a copy if you don't want that to
    happen.

    """
    grays = []
    for segment in path:
        c, w = segment.color, segment.weight
        if c == 'Gray':
            grays.append(w)
        elif cards.get(c, 0) >= w:
            cards[c] -= w
        else:
            return False
    return packing(tuple(cards.values()), tuple(grays)) is not None

注意，如果你把cards变成一个collection.Counter，那么你就可以直接写cards[c]，而不是cards.get(c, 0)。