如何以最小代价分割n×n×n 3D numpy矩阵的两个切片（26连通）

问题描述 #

给定一个元素为代价的n×n×n 3D numpy矩阵，需要找到一组n×n的元素，以最小代价完全分隔指定的前后切片（比如沿x轴的源切片[0, :, :]和汇切片[n-1, :, :]），元素采用26连通规则（即每个元素与上下左右前后及所有斜向相邻的26个元素连通）。之前尝试用NetworkX，但该工具仅支持单个源点/汇点，无法直接处理整个切片作为源/汇的需求。

核心思路：转化为带超级源汇的最小割问题 #

这个问题本质是最小割问题，通过构造超级源点和超级汇点，把整个切片的节点统一关联起来，就能适配NetworkX的单源单汇限制。具体步骤如下：

1. 图结构建模 #

• 节点拆分：把3D矩阵里的每个元素(x,y,z)拆成两个节点：(x,y,z)_in和(x,y,z)_out，给这两个节点之间加一条边，边的容量设为该元素的代价。这样“选择这个元素作为分隔”就等价于切断这条边，代价刚好对应元素值。
• 连通边构建：对每个元素，遍历它的26个连通邻居，给当前元素的_out节点到邻居的_in节点加一条容量无穷大的边——这是为了确保最小割只会切断元素自身的入出边，不会切断相邻节点之间的连接（无穷大的边不会被选作割边）。
• 超级源汇：创建一个超级源点S，给源切片里所有元素的_in节点连一条无穷大容量的边；再创建超级汇点T，给汇切片里所有元素的_out节点连一条无穷大容量的边。这样整个源切片就等价于一个“超级源”，汇切片等价于“超级汇”。

2. 计算最小割 #

根据最大流最小割定理，最小割的容量等于从S到T的最大流流量。用NetworkX的最大流算法计算后，就能得到分隔源汇切片的最小代价元素集合。

代码示例 #

import networkx as nx
import numpy as np

def build_cut_graph(matrix):
    n = matrix.shape[0]
    G = nx.DiGraph()
    
    # 遍历所有元素，拆点并添加自身代价边
    for x in range(n):
        for y in range(n):
            for z in range(n):
                node_in = (x, y, z, "in")
                node_out = (x, y, z, "out")
                G.add_edge(node_in, node_out, capacity=matrix[x, y, z])
                
                # 添加26连通的邻边
                for dx in (-1, 0, 1):
                    for dy in (-1, 0, 1):
                        for dz in (-1, 0, 1):
                            if dx == 0 and dy == 0 and dz == 0:
                                continue
                            nx_, ny_, nz_ = x + dx, y + dy, z + dz
                            if 0 <= nx_ < n and 0 <= ny_ < n and 0 <= nz_ < n:
                                neighbor_in = (nx_, ny_, nz_, "in")
                                G.add_edge(node_out, neighbor_in, capacity=np.inf)
    
    # 添加超级源汇
    source = "super_source"
    sink = "super_sink"
    # 连接源切片所有节点到超级源
    for y in range(n):
        for z in range(n):
            G.add_edge(source, (0, y, z, "in"), capacity=np.inf)
    # 连接汇切片所有节点到超级汇
    for y in range(n):
        for z in range(n):
            G.add_edge((n-1, y, z, "out"), sink, capacity=np.inf)
    
    return G, source, sink

def find_min_separator(matrix):
    G, source, sink = build_cut_graph(matrix)
    # 计算最小割，返回割的容量和节点分区
    cut_cost, partition = nx.minimum_cut(G, source, sink)
    # 从源侧分区中筛选出被割的节点（即_out节点对应的原元素）
    separator = []
    for node in partition[0]:
        if isinstance(node, tuple) and node[-1] == "out":
            x, y, z, _ = node
            separator.append((x, y, z))
    # separator是分隔元素的坐标列表，cut_cost是总代价
    return separator, cut_cost

关键说明 #

• 拆点法是核心：把节点代价转化为边的容量，完美适配最小割“割边”的逻辑，确保我们选的是代价最小的元素集合。
• 无穷大容量的邻边：保证最小割不会通过相邻节点的连接来分隔，只会选择切断元素自身的入出边，符合问题要求。
• 超级源汇的作用：把整个切片的节点统一绑定，解决了NetworkX只能处理单源单汇的限制。

内容的提问来源于stack exchange，提问作者MrJorisdh