Java实现旅行商问题最近邻算法的排列bug排查与修复咨询

「排列异常、依赖输入顺序」问题成因 #

该问题核心是实现逻辑未遵循最近邻算法的状态约束，常见错误点如下：

• 未固定算法起始点，每次随打乱后的输入列表动态变更起始城镇，路径自然完全不同
• 未独立维护已访问、未访问城镇集合，直接遍历原始输入列表找下一个节点，输入顺序变化时遍历优先级改变，遇到距离相等的节点时会选出不同结果
• 错误遍历全量城镇而非未访问城镇，导致已访问的节点被重复纳入计算，甚至出现路径跳点、重复点的问题

最近邻算法的正确实现逻辑 #

标准TSP最近邻算法的执行流程完全不受输入顺序影响，固定步骤如下：

• 第一步明确指定起始城镇：可固定选输入集合中坐标最小的点、或者由调用方显式传入，起始点一旦固定全流程不再变更
• 初始化两个状态集合：已访问集合仅包含起始点，未访问集合包含除起始点外的所有城镇
• 迭代计算：每一步从当前所在城镇出发，遍历所有未访问城镇计算距离，选出距离最小的作为下一个访问节点
• 状态更新：将新选出的节点加入已访问集合、从未访问集合移除，更新当前节点为该新节点
• 终止：未访问集合为空后，可选择将最后一个节点与起始点相连形成闭合路径
  只要起始点、距离计算逻辑、等距优先级规则固定，无论输入列表如何打乱，最终输出路径完全一致

Java代码修复方案 #

以下是可直接验证的正确实现，替换你原有tspnn方法即可：

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

// 你的Point类根据实际实现调整，此处假设已实现getX、getY方法
class Point {
    private double x;
    private double y;
    // 构造方法、getter省略
}

public class TSPNearestNeighbor {
    public List<Point> tspnn(List<Point> towns) {
        // 空输入直接返回
        if (towns == null || towns.isEmpty()) return Collections.emptyList();
        // 复制输入列表避免修改原始输入，独立维护未访问集合
        List<Point> unvisited = new ArrayList<>(towns);
        List<Point> path = new ArrayList<>();
        
        // 固定起始点：此处取第一个点，也可自定义规则选固定起始点
        Point current = unvisited.remove(0);
        path.add(current);

        // 迭代直到所有点访问完成
        while (!unvisited.isEmpty()) {
            Point nearest = null;
            double minDistance = Double.MAX_VALUE;
            // 遍历所有未访问点找最近邻
            for (Point p : unvisited) {
                double distance = calculateDistance(current, p);
                if (distance < minDistance) {
                    minDistance = distance;
                    nearest = p;
                } else if (distance == minDistance) {
                    // 等距时固定优先级：按x坐标升序，x相等按y升序，避免输入顺序干扰
                    if (p.getX() < nearest.getX() || (p.getX() == nearest.getX() && p.getY() < nearest.getY())) {
                        nearest = p;
                    }
                }
            }
            // 更新状态
            current = nearest;
            unvisited.remove(nearest);
            path.add(current);
        }
        // 若需要闭合回路，放开下一行注释
        // path.add(path.get(0));
        return path;
    }

    // 欧几里得距离计算，根据你的实际距离规则调整
    private double calculateDistance(Point a, Point b) {
        double dx = a.getX() - b.getX();
        double dy = a.getY() - b.getY();
        return Math.sqrt(dx * dx + dy * dy);
    }
}

修复后再运行打乱顺序的测试用例，输出结果会和参考实现tspnn_simpleNN完全一致。

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