4

我喜欢玩Ticket to Ride，所以我决定尝试在 Python 中实现部分游戏逻辑作为辅助编程项目。游戏板本质上是一个加权多重图，因此使用NetworkX复制游戏的基本结构是轻而易举的事。

我遇到麻烦的一个部分是分析在给定玩家拥有的火车卡清单的情况下是否有可能通过棋盘的特定路径。我认为这更像是一个数学问题，而不是编程问题本身，我可能可以拼凑出一种蛮力方法来解决问题，但认为必须有一种更有效的方法。

对于那些不了解游戏的人：在任何给定时间，每个玩家都有一些八种颜色中的一种的火车卡，以及一个特殊的“机车”类别，用作外卡。这些颜色与游戏板上的火车线颜色相对应（此处显示），除了灰色线，您可以使用任何颜色，只要该段中的所有汽车颜色相同即可。（有一些涉及隧道和渡轮的极端案例，但我们暂时将它们放在一边。）

使用现在的代码，我可以找到两个给定城市之间的所有路径，并返回需要多少每种颜色的火车卡才能走这条特定的路径，除非路径涉及灰色段。我先做非灰色部分，因为它们更简单——路径中的每个红色/绿色/蓝色部分都有足够的红色/绿色/蓝色卡片，或者你没有。使用灰色，因为您可以为每个部分选择任何颜色，它会涉及更多。

对于只有一个灰色段的路径，它仍然很容易——要么你有足够的任何一种颜色的卡片来填充它，要么没有。但是，对于多个灰色段，可能会遇到为第一段选择的颜色无法完成第二或第三段的情况。

举个例子，假设一个玩家的卡牌库存是 4 红色，2 绿色，3 蓝色，我们试图弄清楚他是否可以从巴黎到维也纳。看图板，很容易看出这张卡组合的唯一可能路线是去巴黎--（3灰色）-->苏黎世--（2绿色）-->威尼斯--（2灰色）-- > Zagrad --(2 灰色)--> 维也纳。我的算法从绿色部分开始，并在那里分配两张绿卡。然后它需要决定如何使用剩余的 4 张红卡和 3 张蓝卡来覆盖长度为 3、2 和 2 的灰色段。

答案当然是使用巴黎和苏黎世之间的 3 张蓝卡，威尼斯到萨格拉德和萨格拉德到维也纳各两张红卡。但是，对于涉及更多颜色和更多段的不太明显的情况，如何编写一个通用算法来解决这个问题呢？

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

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

（“重量”是火车车厢中段的长度。）

我觉得这里潜伏着一个非常微不足道的解决方案，我无法指望。有任何想法吗？

4

3 回答 3

3

正如 Daniel Brückner 所说，找到将卡片颜色分配给灰色部分的问题对应于装箱问题，彩色卡片的集合对应于箱，灰色部分对应于要打包的对象。

现在，装箱问题是NP-hard问题，但在这种情况下这不是灾难，因为可以使用动态规划在伪多项式时间内（即，在时间上是箱大小的多项式）解决问题，这对于您的应用程序来说应该已经足够好了，因为垃圾箱的大小受游戏中卡片数量的限制。这是一个 bin 打包的示例实现，使用装饰器对其进行记忆：@functools.lru_cache

从 functools 导入 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

这可用于确定是否可以在 Ticket to Ride 中遵循路径：

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

于 2013-01-23T16:41:05.080 回答
0

这个问题与装箱问题、子集总和和其他类似问题有一些相似之处。提到的和许多相关的问题都是NP完全的，因此可能会证明没有（已知的）有效算法可以解决这个问题，但我目前无法证明这一点——这只是一种直觉。我会再考虑一下，然后更新这个答案。

于 2013-01-23T17:03:41.440 回答
0

解决此问题的另一种方法是构建搜索树，如下所示：

  • 每个节点都标有一个城市名称、一组卡片和一些火车。这对应于特定路线的起始城市以及您可用的卡片和火车件。

  • 节点的每个子节点对应于您可以从父节点到达的城市，以及完成从父节点到节点的路线后留在您手中的卡片和火车部件。

例如，树的根可能对应于蒙特利尔，有 4 个蓝色、1 个白色和 1 个通配符，以及 45 个火车件。根的孩子将是：

  • 多伦多，（1蓝，1白，1野），42#使用3张蓝卡
  • Toronto, (2 blue, 1 white), 42 #使用2蓝色和外卡
  • 纽约，（1蓝，1白，1野），42#使用3张蓝卡
  • 纽约，（2蓝色，1白色），43#使用2蓝色和外卡
  • 波士顿，（3蓝色，1白色），43＃使用1蓝色和外卡
  • 波士顿，（2蓝，1白，1野），43#使用2张蓝卡
  • 波士顿，（4蓝色），43＃使用1白色和外卡

现在，您只需要在这棵树中执行深度优先搜索，看看您是否可以到达目的地城市。您添加到搜索树的边缘受您手中的牌的限制（即，您不能直接从蒙特利尔前往 Sault St. Marie，因为您手上总共没有 6 张黑色/百搭牌）以及剩余的火车数量（如果你只剩下 3 张卡，你就不能从卡尔加里到西雅图）。

于 2013-01-23T18:06:28.093 回答