每日算法 — 使用java实现异星工厂：物流网络最大流与传送带瓶颈分析

引言

《异星工厂》（Factorio）是一款以自动化生产为核心的沙盒游戏，玩家需要设计高效的工厂物流网络，将原材料通过传送带、机械臂和管道运输到各个生产设施。一个核心算法问题是：给定工厂的物流拓扑结构，如何计算网络的最大吞吐量，并识别出限制整体产能的瓶颈节点？ 本文用Java将工厂物流网络建模为流网络，使用Edmonds-Karp最大流算法分析传送带系统的流量瓶颈，为工厂布局优化提供算法支撑。

物流网络建模

核心数据结构

import java.util.*;

/**
 * 物流网络中的节点：可以是采矿机、熔炉、组装机、箱子、分流器等
 */
class FactoryNode {
    public final String id;
    public final NodeType type;
    public final double processingRate;    // 处理速率（物品/秒）
    public double currentLoad = 0;          // 当前负载

    // 节点位置（用于可视化）
    public final int x, y;

    public FactoryNode(String id, NodeType type, double rate, int x, int y) {
        this.id = id;
        this.type = type;
        this.processingRate = rate;
        this.x = x;
        this.y = y;
    }

    /**
     * 计算节点的利用率
     */
    public double getUtilization() {
        if (processingRate <= 0) return 0;
        return Math.min(1.0, currentLoad / processingRate);
    }

    @Override
    public String toString() {
        return String.format("%s[%s] 速率:%.1f 负载:%.1f 利用率:%.1f%%",
            id, type, processingRate, currentLoad, getUtilization() * 100);
    }
}

enum NodeType {
    SOURCE,          // 源头：采矿机、抽油机
    PROCESSOR,       // 处理器：熔炉、组装机、化工厂
    SPLITTER,        // 分流器：将输入均分到多个输出
    MERGER,          // 合并器：将多个输入合并
    BUFFER,          // 缓冲：箱子、储液罐
    SINK             // 汇点：目标产物存储
}

/**
 * 物流边：传送带、机械臂、管道等连接
 */
class LogisticsEdge {
    public final FactoryNode from;
    public final FactoryNode to;
    public final double capacity;        // 最大流量（物品/秒）
    public double flow = 0;              // 当前流量
    public final EdgeType type;

    public LogisticsEdge(FactoryNode from, FactoryNode to, double capacity, EdgeType type) {
        this.from = from;
        this.to = to;
        this.capacity = capacity;
        this.type = type;
    }

    /**
     * 计算边的利用率
     */
    public double getUtilization() {
        if (capacity <= 0) return 0;
        return flow / capacity;
    }

    @Override
    public String toString() {
        return String.format("%s -> %s [%.1f/%.1f %s]",
            from.id, to.id, flow, capacity, type);
    }
}

enum EdgeType {
    BELT_YELLOW,     // 黄色传送带：15物品/秒
    BELT_RED,        // 红色传送带：30物品/秒
    BELT_BLUE,       // 蓝色传送带：45物品/秒
    INSERTER,        // 机械臂：~1-3物品/秒
    PIPE             // 管道：流体运输
}

工厂物流网络

/**
 * 工厂物流网络：包含所有节点和边，支持最大流计算
 */
public class FactoryNetwork {
    private final Map<String, FactoryNode> nodes = new HashMap<>();
    private final Map<String, List<LogisticsEdge>> adjacency = new HashMap<>();
    private final List<LogisticsEdge> allEdges = new ArrayList<>();

    public void addNode(FactoryNode node) {
        nodes.put(node.id, node);
        adjacency.putIfAbsent(node.id, new ArrayList<>());
    }

    public void addEdge(FactoryNode from, FactoryNode to, double capacity, EdgeType type) {
        LogisticsEdge edge = new LogisticsEdge(from, to, capacity, type);
        adjacency.get(from.id).add(edge);
        allEdges.add(edge);
    }

    public FactoryNode getNode(String id) {
        return nodes.get(id);
    }

    public List<LogisticsEdge> getEdgesFrom(String nodeId) {
        return adjacency.getOrDefault(nodeId, new ArrayList<>());
    }

    /**
     * 获取所有源点（采矿机等）
     */
    public List<FactoryNode> getSources() {
        return nodes.values().stream()
            .filter(n -> n.type == NodeType.SOURCE)
            .toList();
    }

    /**
     * 获取所有汇点（产物存储）
     */
    public List<FactoryNode> getSinks() {
        return nodes.values().stream()
            .filter(n -> n.type == NodeType.SINK)
            .toList();
    }

    /**
     * 打印网络拓扑
     */
    public void printTopology() {
        System.out.println("=== 工厂物流网络拓扑 ===");
        for (FactoryNode node : nodes.values()) {
            System.out.println(node);
            for (LogisticsEdge edge : getEdgesFrom(node.id)) {
                System.out.println("  " + edge);
            }
        }
    }
}

Edmonds-Karp最大流算法

Edmonds-Karp是Ford-Fulkerson方法的一种实现，使用BFS寻找增广路径，时间复杂度为O(V × E²)。

/**
 * Edmonds-Karp最大流算法实现
 */
public class MaxFlowAnalyzer {
    private final FactoryNetwork network;
    private final Map<String, Map<String, LogisticsEdge>> residualGraph;

    public MaxFlowAnalyzer(FactoryNetwork network) {
        this.network = network;
        this.residualGraph = new HashMap<>();
        buildResidualGraph();
    }

    /**
     * 构建残量图：每条边生成正向残量边和反向残量边
     */
    private void buildResidualGraph() {
        for (FactoryNode node : network.getSources()) {
            residualGraph.putIfAbsent(node.id, new HashMap<>());
        }
        for (LogisticsEdge edge : network.allEdges) {
            residualGraph.putIfAbsent(edge.from.id, new HashMap<>());
            residualGraph.putIfAbsent(edge.to.id, new HashMap<>());

            // 正向边：剩余容量 = 总容量 - 当前流量
            residualGraph.get(edge.from.id).put(edge.to.id, edge);

            // 反向边：初始剩余容量 = 当前流量（初始为0）
            // 通过查找或创建反向边
            LogisticsEdge reverse = residualGraph.get(edge.to.id).get(edge.from.id);
            if (reverse == null) {
                reverse = new LogisticsEdge(edge.to, edge.from, 0, edge.type);
                residualGraph.get(edge.to.id).put(edge.from.id, reverse);
            }
        }
    }

    /**
     * 计算从源点到汇点的最大流
     * @param sourceId 源点ID
     * @param sinkId 汇点ID
     * @return 最大流量值
     */
    public double computeMaxFlow(String sourceId, String sinkId) {
        // 重置所有边的流量
        for (LogisticsEdge edge : network.allEdges) {
            edge.flow = 0;
        }

        double maxFlow = 0;

        while (true) {
            // BFS寻找增广路径
            List<String> path = findAugmentingPath(sourceId, sinkId);
            if (path == null) break; // 不存在增广路径，算法结束

            // 计算路径上的最小残量
            double pathFlow = Double.POSITIVE_INFINITY;
            for (int i = 0; i < path.size() - 1; i++) {
                String u = path.get(i);
                String v = path.get(i + 1);
                LogisticsEdge edge = residualGraph.get(u).get(v);
                double residualCapacity = edge.capacity - edge.flow;
                pathFlow = Math.min(pathFlow, residualCapacity);
            }

            // 沿增广路径更新流量
            for (int i = 0; i < path.size() - 1; i++) {
                String u = path.get(i);
                String v = path.get(i + 1);

                LogisticsEdge forward = residualGraph.get(u).get(v);
                forward.flow += pathFlow;

                // 更新反向边
                LogisticsEdge backward = residualGraph.get(v).get(u);
                if (backward != null) {
                    backward.flow -= pathFlow;
                }
            }

            maxFlow += pathFlow;
        }

        return maxFlow;
    }

    /**
     * BFS寻找从源到汇的增广路径
     */
    private List<String> findAugmentingPath(String source, String sink) {
        Map<String, String> parent = new HashMap<>();
        Queue<String> queue = new LinkedList<>();
        Set<String> visited = new HashSet<>();

        queue.offer(source);
        visited.add(source);
        parent.put(source, null);

        while (!queue.isEmpty()) {
            String current = queue.poll();

            if (current.equals(sink)) {
                // 重构路径
                List<String> path = new ArrayList<>();
                String node = sink;
                while (node != null) {
                    path.add(0, node);
                    node = parent.get(node);
                }
                return path;
            }

            Map<String, LogisticsEdge> neighbors = residualGraph.get(current);
            if (neighbors == null) continue;

            for (Map.Entry<String, LogisticsEdge> entry : neighbors.entrySet()) {
                String next = entry.getKey();
                LogisticsEdge edge = entry.getValue();

                if (!visited.contains(next) && edge.flow < edge.capacity) {
                    visited.add(next);
                    parent.put(next, current);
                    queue.offer(next);
                }
            }
        }

        return null; // 无增广路径
    }

    /**
     * 识别网络中的所有瓶颈边（流量等于容量的边）
     */
    public List<LogisticsEdge> findBottlenecks() {
        List<LogisticsEdge> bottlenecks = new ArrayList<>();
        for (LogisticsEdge edge : network.allEdges) {
            if (edge.flow >= edge.capacity * 0.99) { // 考虑浮点误差
                bottlenecks.add(edge);
            }
        }
        return bottlenecks;
    }

    /**
     * 计算每条边的利用率并排序
     */
    public List<LogisticsEdge> getUtilizationRanking() {
        return network.allEdges.stream()
            .sorted((e1, e2) -> Double.compare(e2.getUtilization(), e1.getUtilization()))
            .toList();
    }

    /**
     * 分析特定节点的输入/输出平衡
     */
    public NodeBalance analyzeNodeBalance(String nodeId) {
        double totalIn = 0, totalOut = 0;

        for (LogisticsEdge edge : network.allEdges) {
            if (edge.to.id.equals(nodeId)) {
                totalIn += edge.flow;
            }
            if (edge.from.id.equals(nodeId)) {
                totalOut += edge.flow;
            }
        }

        FactoryNode node = network.getNode(nodeId);
        double imbalance = totalIn - totalOut;
        boolean isStarved = totalIn < node.processingRate * 0.9;
        boolean isBackedUp = totalOut < totalIn * 0.9;

        return new NodeBalance(nodeId, totalIn, totalOut, imbalance, isStarved, isBackedUp);
    }

    public static class NodeBalance {
        public final String nodeId;
        public final double totalInput;
        public final double totalOutput;
        public final double imbalance;
        public final boolean isStarved;     // 输入不足
        public final boolean isBackedUp;    // 输出阻塞

        public NodeBalance(String id, double in, double out, double imbalance, 
                          boolean starved, boolean backedUp) {
            this.nodeId = id;
            this.totalInput = in;
            this.totalOutput = out;
            this.imbalance = imbalance;
            this.isStarved = starved;
            this.isBackedUp = backedUp;
        }

        @Override
        public String toString() {
            return String.format("%s: 入=%.1f 出=%.1f 差=%.1f %s%s",
                nodeId, totalInput, totalOutput, imbalance,
                isStarved ? "[饥饿]" : "", isBackedUp ? "[堆积]" : "");
        }
    }
}

工厂场景构建与瓶颈分析

public class FactorioNetworkBuilder {

    /**
     * 构建经典的"铁板生产线"场景：
     * 采矿机 -> 传送带 -> 熔炉 -> 传送带 -> 箱子
     * 分析瓶颈并给出升级建议
     */
    public static FactoryNetwork createIronPlateProductionLine() {
        FactoryNetwork network = new FactoryNetwork();

        // 源头：3台采矿机，每台0.5物品/秒
        FactoryNode miner1 = new FactoryNode("采矿机1", NodeType.SOURCE, 0.5, 0, 0);
        FactoryNode miner2 = new FactoryNode("采矿机2", NodeType.SOURCE, 0.5, 0, 2);
        FactoryNode miner3 = new FactoryNode("采矿机3", NodeType.SOURCE, 0.5, 0, 4);
        network.addNode(miner1);
        network.addNode(miner2);
        network.addNode(miner3);

        // 合并节点
        FactoryNode merger = new FactoryNode("合并点", NodeType.MERGER, 999, 2, 2);
        network.addNode(merger);

        // 熔炉：2台，每台处理速率1.0/秒（铁矿->铁板耗时3.2秒，故速率约0.3125/秒）
        FactoryNode furnace1 = new FactoryNode("熔炉1", NodeType.PROCESSOR, 0.3125, 5, 1);
        FactoryNode furnace2 = new FactoryNode("熔炉2", NodeType.PROCESSOR, 0.3125, 5, 3);
        network.addNode(furnace1);
        network.addNode(furnace2);

        // 分流节点
        FactoryNode splitter = new FactoryNode("分流器", NodeType.SPLITTER, 999, 4, 2);
        network.addNode(splitter);

        // 汇点
        FactoryNode chest = new FactoryNode("铁板箱", NodeType.SINK, 999, 7, 2);
        network.addNode(chest);

        // 连接：采矿机 -> 合并点（黄色传送带 15/s）
        network.addEdge(miner1, merger, 15, EdgeType.BELT_YELLOW);
        network.addEdge(miner2, merger, 15, EdgeType.BELT_YELLOW);
        network.addEdge(miner3, merger, 15, EdgeType.BELT_YELLOW);

        // 合并点 -> 分流器（黄色传送带）
        network.addEdge(merger, splitter, 15, EdgeType.BELT_YELLOW);

        // 分流器 -> 熔炉（机械臂，约2/s）
        network.addEdge(splitter, furnace1, 2, EdgeType.INSERTER);
        network.addEdge(splitter, furnace2, 2, EdgeType.INSERTER);

        // 熔炉 -> 箱子（黄色传送带）
        network.addEdge(furnace1, chest, 15, EdgeType.BELT_YELLOW);
        network.addEdge(furnace2, chest, 15, EdgeType.BELT_YELLOW);

        return network;
    }

    /**
     * 构建更复杂的多级生产网络：
     * 铁矿 -> 铁板 -> 齿轮 -> 传送带 -> 科技包
     */
    public static FactoryNetwork createMultiStageFactory() {
        FactoryNetwork network = new FactoryNetwork();

        // 第一层：采矿（总产出2.0/秒）
        FactoryNode ironSource = new FactoryNode("铁矿源", NodeType.SOURCE, 2.0, 0, 0);
        network.addNode(ironSource);

        // 第二层：熔炼（铁板）
        FactoryNode furnace = new FactoryNode("熔炉组", NodeType.PROCESSOR, 1.25, 3, 0);
        network.addNode(furnace);

        // 第三层：齿轮生产（1铁板->1齿轮，耗时0.5秒）
        FactoryNode gearAssembler = new FactoryNode("齿轮组装", NodeType.PROCESSOR, 2.0, 6, 0);
        network.addNode(gearAssembler);

        // 第四层：传送带生产（1铁板+1齿轮->2传送带，耗时0.5秒）
        FactoryNode beltAssembler = new FactoryNode("传送带组装", NodeType.PROCESSOR, 2.0, 9, 0);
        network.addNode(beltAssembler);

        // 第五层：科技包生产（需要多种原料）
        FactoryNode scienceAssembler = new FactoryNode("科技包组装", NodeType.PROCESSOR, 1.0, 12, 0);
        network.addNode(scienceAssembler);

        // 原料补充源
        FactoryNode copperSource = new FactoryNode("铜矿源", NodeType.SOURCE, 1.0, 0, 3);
        network.addNode(copperSource);

        // 汇点
        FactoryNode scienceSink = new FactoryNode("科技包存储", NodeType.SINK, 999, 15, 0);
        network.addNode(scienceSink);

        // 连接
        network.addEdge(ironSource, furnace, 15, EdgeType.BELT_YELLOW);
        network.addEdge(furnace, gearAssembler, 15, EdgeType.BELT_YELLOW);
        network.addEdge(furnace, beltAssembler, 15, EdgeType.BELT_RED);  // 铁板去传送带
        network.addEdge(gearAssembler, beltAssembler, 15, EdgeType.BELT_YELLOW); // 齿轮去传送带
        network.addEdge(beltAssembler, scienceAssembler, 15, EdgeType.BELT_YELLOW); // 传送带去科技
        network.addEdge(copperSource, scienceAssembler, 15, EdgeType.BELT_YELLOW); // 铜去科技
        network.addEdge(scienceAssembler, scienceSink, 15, EdgeType.BELT_YELLOW);

        return network;
    }

    public static void main(String[] args) {
        System.out.println("=== 异星工厂物流网络最大流分析 ===\n");

        // 场景1：简单铁板生产线
        System.out.println("--- 场景1：铁板生产线 ---");
        FactoryNetwork line = createIronPlateProductionLine();
        line.printTopology();

        MaxFlowAnalyzer analyzer1 = new MaxFlowAnalyzer(line);
        double maxFlow1 = analyzer1.computeMaxFlow("采矿机1", "铁板箱");
        System.out.printf("\n采矿机1 -> 铁板箱 最大流: %.3f 物品/秒%n", maxFlow1);

        System.out.println("\n瓶颈分析:");
        for (LogisticsEdge bottleneck : analyzer1.findBottlenecks()) {
            System.out.println("  瓶颈: " + bottleneck);
        }

        // 场景2：多级生产网络
        System.out.println("\n--- 场景2：多级生产网络（铁矿->科技包）---");
        FactoryNetwork factory = createMultiStageFactory();
        factory.printTopology();

        MaxFlowAnalyzer analyzer2 = new MaxFlowAnalyzer(factory);
        double maxFlow2 = analyzer2.computeMaxFlow("铁矿源", "科技包存储");
        System.out.printf("\n铁矿源 -> 科技包存储 最大流: %.3f 物品/秒%n", maxFlow2);

        System.out.println("\n所有边利用率排序:");
        for (LogisticsEdge edge : analyzer2.getUtilizationRanking()) {
            System.out.printf("  %.1f%% %s%n", edge.getUtilization() * 100, edge);
        }

        System.out.println("\n节点平衡分析:");
        for (String nodeId : Arrays.asList("熔炉组", "齿轮组装", "传送带组装", "科技包组装")) {
            MaxFlowAnalyzer.NodeBalance balance = analyzer2.analyzeNodeBalance(nodeId);
            System.out.println("  " + balance);
        }

        // 优化建议
        System.out.println("\n=== 优化建议 ===");
        List<LogisticsEdge> bottlenecks = analyzer2.findBottlenecks();
        if (bottlenecks.isEmpty()) {
            System.out.println("当前网络无明显瓶颈，产能主要受限于源点产出。");
        } else {
            System.out.println("建议优先升级以下瓶颈连接:");
            for (LogisticsEdge e : bottlenecks) {
                String upgrade = e.type == EdgeType.BELT_YELLOW ? "升级为红色传送带(30/s)" :
                                e.type == EdgeType.BELT_RED ? "升级为蓝色传送带(45/s)" :
                                "增加并行机械臂";
                System.out.printf("  %s -> %s: %s%n", e.from.id, e.to.id, upgrade);
            }
        }
    }
}

最小割与瓶颈等价性

根据最大流最小割定理，网络的最大流等于最小割的容量。最小割将网络分为两部分，割集上的边就是瓶颈所在。

/**
 * 最小割分析：找出限制网络的最大流的关键边集
 */
class MinCutAnalyzer {

    /**
     * 在最大流计算完成后，通过BFS遍历残量图找到最小割
     */
    public static List<LogisticsEdge> findMinCut(FactoryNetwork network, 
                                                  MaxFlowAnalyzer analyzer,
                                                  String sourceId) {
        // 在残量图中从源点出发，只走容量>0的边，能到达的节点构成S集
        Set<String> reachable = new HashSet<>();
        Queue<String> queue = new LinkedList<>();
        queue.offer(sourceId);
        reachable.add(sourceId);

        while (!queue.isEmpty()) {
            String current = queue.poll();
            for (LogisticsEdge edge : network.getEdgesFrom(current)) {
                if (edge.flow < edge.capacity && !reachable.contains(edge.to.id)) {
                    reachable.add(edge.to.id);
                    queue.offer(edge.to.id);
                }
            }
        }

        // 最小割 = 从S集到T集的所有边
        List<LogisticsEdge> minCut = new ArrayList<>();
        for (LogisticsEdge edge : network.allEdges) {
            if (reachable.contains(edge.from.id) && !reachable.contains(edge.to.id)) {
                minCut.add(edge);
            }
        }

        return minCut;
    }
}

算法复杂度分析

对于典型工厂网络（V<100, E<200），Edmonds-Karp在毫秒级完成。对于更大规模的工厂（V>1000），可采用Dinic算法（O(V² × E)）或Push-Relabel算法（O(V³)）获得更好的性能。

扩展方向

1. 多商品流：当工厂同时生产多种产品（铁板、铜板、齿轮、电路板）时，需要多商品流算法分析各生产线的相互影响。

2. 动态瓶颈检测：随着工厂扩建，网络拓扑不断变化。可以增量更新最大流，而非每次都重新计算。

3. 最优布局搜索：将工厂布局问题建模为带约束的优化问题，用遗传算法或模拟退火自动寻找最优的设施位置。

4. 流体网络扩展：对于石油精炼、化工生产等涉及流体的场景，需要引入压力-流量关系的非线性约束。

总结

本文用Java将异星工厂的物流网络抽象为流网络模型，并运用Edmonds-Karp最大流算法精确计算了网络的吞吐量上限和瓶颈位置。最大流算法不仅适用于工厂物流，也是交通网络、通信网络、供应链等任何”管道系统”的核心分析工具。读者可以在本文基础上扩展多商品流、动态更新、布局优化等功能，打造一个完整的工厂设计与分析系统。