python - 拼图在房间和走廊的网格中从开始行移动到结束行的最大数量

Question

我有这个谜题，它提供了一个由走廊连接在一起的房间网格，在入口房间里有一群人，你需要将他们通过走廊移动到导出房间，这个谜题有以下规则:

1. 网格元素 path[A][B] = C 描述了这条走廊通向 从 A 到 B 每个时间步可以容纳 C 个人。
2. 最多有 50 个房间由走廊相连，最多 2000000 个 一次适合的人。
3. 入口和导出从不 重叠。

所以我需要找出中间每条走廊的每个方向同时可以容纳多少人。例如求解下面的网格:

entrances = [0, 1]
exits = [4, 5]
grid = [
    [0, 0, 4, 6, 0, 0],
    [0, 0, 5, 2, 0, 0],
    [0, 0, 0, 0, 4, 4],
    [0, 0, 0, 0, 6, 6],
    [0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0],
]

在每个时间步中，可能会发生以下情况:

• 0 将 4/4 人发送给 2，将 6/6 人发送给 3
• 1 派 4/5 人给 2 人，2/2 人给 3 人
• 2 派 4/4 人给 4 人，4/4 人给 5 人
• 3 派 4/6 人给 4 人，4/6 人给 5 人

因此，总共有 16 个人可以在每个时间步到达第 4 排和第 5 排的导出。 (请注意，在此示例中，房间 3 可以将 8 人发送到 4 和 5，例如 2/6 和 6/6，但最终答案保持不变。)

我试图通过从顶部开始并将人们沿着网格移动到隔壁房间的下一个可用走廊直到我到达导出然后我计算到达导出的人数来解决它。这适用于像上面的例子这样的简单情况，但它没有考虑从一个房间的多个可用走廊中选择最佳走廊，这将允许最大数量的人通过导出，也没有考虑您可以从任何房间发送任何组合的人。这是我到目前为止的代码:

grid2 = [
#    0  1  2  3  4  5  6  7  8  9 10 11
    [0, 0, 4, 6, 0, 9, 8, 0, 5, 0, 0, 0], # 0
    [0, 0, 5, 2, 7, 0, 9, 9, 0, 6, 0, 0], # 1
    [0, 0, 0, 3, 4, 9, 0, 2, 8, 0, 8, 0], # 2
    [0, 0, 0, 0, 6, 6, 1, 8, 0, 7, 0, 9], # 3
    [0, 0, 0, 0, 0, 3, 9, 0, 4, 0, 0, 0], # 4
    [0, 0, 0, 0, 0, 0, 9, 6, 0, 4, 9, 0], # 5
    [0, 0, 0, 0, 0, 0, 0, 7, 2, 3, 6, 1], # 6
    [0, 0, 0, 0, 0, 0, 0, 0, 9, 9, 9, 9], # 7
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 8, 6, 2], # 8
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 9, 6], # 9
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], # 10
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], # 11
]

def solve (entrances, exits, path):
    rows = len (path)
    cols = len (path[0])
    station = [x for x in path]
    for r in range (rows):
        for c in range (cols):
            if path[r][c]:
                val = station[r][c]
                station[r][c] = [val, val] if r in entrances else [val, 0]
    total = 0
    for r in [x for x in range (rows) if x not in exits]:
        for c in range (cols):
            if station[r][c] and station[r][c][1]:
                count = station[r][c][1]
                if c not in exits:
                    for i in range (cols):
                        if station[c][i] and not station[c][i][1]: 
                                num = min (count, station[c][i][0])
                                station[c][i][1] = num
                                break
                else: total += count
    return total

解决这个难题的最佳方法是什么？是否有一个好的算法可以在这里实现？

Answer 1

这个问题似乎有点模棱两可，但这是我最好的尝试:

最大流量。从示例来看，基本上您在这里尝试做的是尝试为该矩阵中提供给您的残差网络找到最大流量。这在规范中没有说，但看起来像:

1. 在任何给定时间，人们只能在走廊 - 边缘(节点的容量为 0)。
2. 人们只能在一个“浪潮”中进入网络。

感谢那些人，您可以将其视为一个经典的流动问题 - 您有一个具有特定容量的管道网络，并且您试图随时查看液体通过这些管道的最大流量是多少.

除了可以使用许多流行算法解决的最大流问题之外，这里还有一个技巧可以使用。

由于您的网络中有多个入口和导出节点，您需要添加 2 个人工节点，我们称它们为 -1 和 +inf。它们将分别是“superentrance”和“superexit”。 -1 将连接到所有具有无限容量的“虚拟”边缘的入口(您可以对其进行硬编码)，类似地，所有导出节点将连接到具有无限容量的“虚拟”边缘的 +inf。通过这种方式，您可以将 -1 和 +inf 视为网络的唯一入口和导出 - 它们的容量将与最小切割(瓶颈；给定时间的最大流量等于最小切割为遵循 Max-flow min-cut theorem )，因此添加它们不会改变总流量。然而，它会为您提供一种简单的方法来让您的网络拥有单一输入和输出，而不是多个输入和输出。

至于算法的选择，取决于你的图的大小和图的结构。这是一个 list of popular algorithms - 您可以选择适合您的情况。如果您的数据允许您这样做，您可能希望坚持使用流行且更简单的方法，例如 Ford-Fulkerson 或 Edmonds-Karp，尤其是您可以在网上找到许多实现。