暴力TSP算法Java堆内存溢出问题优化方案咨询

嘿，我看了你的问题和代码，核心问题出在你把所有可能的排列都存储在accum列表里了——当节点数超过10时，n!的排列数会指数级暴涨（比如11个节点就有近4000万条排列），直接把堆内存撑爆。咱们从几个关键方向优化，既能解决OOM问题，还能提升计算效率：

1. 最关键：不要存储所有排列，实时计算并保留最优解 #

原代码把所有路径都存在accum里，这是内存爆炸的元凶。我们可以改成生成一个完整路径就计算一次距离，只记录当前最短的路径和距离，这样内存里永远只保留少量数据（当前生成的路径和最优路径），内存复杂度从O(n!)直接降到O(n)。

2. 优化递归过程，减少不必要的对象复制 #

原代码每次递归都创建新的newPrefix和numsLeft列表，会产生大量临时对象，增加GC压力。我们可以用回溯法：复用同一个列表，添加元素后递归，递归结束再移除元素，避免频繁创建新列表。

3. 预计算距离矩阵，避免重复计算 #

每次创建Path对象计算距离会重复计算两点间的距离，我们可以提前计算一个二维距离矩阵，存下所有节点对之间的距离，后续直接查表即可，减少计算开销和对象创建。

4. 利用TSP的对称性减少计算量 #

TSP的路径是环形的，固定第一个节点（比如第一个节点永远是起点），只生成剩下n-1个节点的排列，这样排列数直接从n!降到(n-1)!，计算量减少n倍（比如10个节点从360万降到36万）。

修改后的完整代码示例 #

import com.sybrand.TSP.*;
import java.util.*;

public class BruteForce extends TSP_Algorithm {
    private ArrayList<Coordinate> coords;
    private ArrayList<Coordinate> shortestRoute;
    private float shortestDistance = Float.MAX_VALUE;
    // 预计算距离矩阵
    private float[][] distanceMatrix;

    public BruteForce(ArrayList<Coordinate> coords) {
        this.coords = new ArrayList<>(coords);
        // 初始化距离矩阵
        initDistanceMatrix();
        // 固定第一个节点，只排列剩下的节点
        ArrayList<Coordinate> remaining = new ArrayList<>(coords.subList(1, coords.size()));
        // 用回溯法生成排列，实时计算
        backtrack(new ArrayList<>(Collections.singletonList(coords.get(0))), remaining);
    }

    private void initDistanceMatrix() {
        int n = coords.size();
        distanceMatrix = new float[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (i == j) {
                    distanceMatrix[i][j] = 0;
                    continue;
                }
                Coordinate c1 = coords.get(i);
                Coordinate c2 = coords.get(j);
                // 这里直接计算两点距离，替换成你Path类里的距离计算逻辑
                distanceMatrix[i][j] = (float) Math.sqrt(
                    Math.pow(c2.getX() - c1.getX(), 2) + Math.pow(c2.getY() - c1.getY(), 2)
                );
            }
        }
    }

    private void backtrack(ArrayList<Coordinate> currentRoute, ArrayList<Coordinate> remaining) {
        if (remaining.isEmpty()) {
            // 计算当前路径的总距离（回到起点）
            float totalDistance = calculateTotalDistance(currentRoute);
            // 更新最短路径
            if (totalDistance < shortestDistance) {
                shortestDistance = totalDistance;
                // 复制当前路径作为最短路径
                shortestRoute = new ArrayList<>(currentRoute);
            }
            return;
        }

        for (int i = 0; i < remaining.size(); i++) {
            // 选择第i个节点加入当前路径
            Coordinate next = remaining.remove(i);
            currentRoute.add(next);
            // 递归
            backtrack(currentRoute, remaining);
            // 回溯：移除刚才添加的节点，放回原位置
            currentRoute.remove(currentRoute.size() - 1);
            remaining.add(i, next);
        }
    }

    private float calculateTotalDistance(ArrayList<Coordinate> route) {
        float total = 0;
        int n = route.size();
        for (int i = 0; i < n; i++) {
            Coordinate from = route.get(i);
            Coordinate to = route.get((i + 1) % n); // 最后回到起点
            // 查距离矩阵
            int fromIndex = coords.indexOf(from);
            int toIndex = coords.indexOf(to);
            total += distanceMatrix[fromIndex][toIndex];
        }
        return total;
    }

    public ArrayList<Coordinate> getSortedCoordinates() {
        return shortestRoute;
    }
}

额外说明 #

• 即使做了这些优化，暴力法的时间复杂度还是O(n!)，所以节点数最多也就能到12-13左右（12!是4.7亿次计算，13!是62亿），如果要支持更多节点，还是得考虑动态规划、遗传算法、模拟退火这类启发式算法，但这已经超出暴力法的范畴了。
• 如果coords里的节点有重复，indexOf可能会出问题，建议给Coordinate类加唯一标识，或者在初始化时用Map存节点到索引的映射，避免查找错误。

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