我的旅行商问题(TSP)最近邻算法实现存在什么问题？

我接到任务要实现旅行商问题的最近邻算法，要求方法尝试从每个城市作为起点运行，返回找到的最优路径。根据自动判分程序的反馈，我的实现在最基础用例下运行正常，但更复杂的用例仅能部分通过。
我不清楚哪里出了问题，希望各位帮忙检查代码的正确性，非常想知道问题所在以及正确的实现思路。

我的实现代码 #

/*
 * Returns the shortest tour found by exercising the NN algorithm 
 * from each possible starting city in table.
 * table[i][j] == table[j][i] gives the cost of travel between City i and City j.
 */
 public static int[] tspnn(double[][] table) {
     
     // number of vertices 
     int numberOfVertices = table.length;
     // the Hamiltonian cycle built starting from vertex i
     int[] currentHamiltonianCycle = new int[numberOfVertices];
     // the lowest total cost Hamiltonian cycle
     double lowestTotalCost = Double.POSITIVE_INFINITY;
     //  the shortest Hamiltonian cycle
     int[] shortestHamiltonianCycle = new int[numberOfVertices];
     
     // consider each vertex i as a starting point
     for (int i = 0; i < numberOfVertices; i++) {
         /* 
          * Consider all vertices that are reachable from the starting point i,
          * thereby creating a new current Hamiltonian cycle.
          */
         for (int j = 0; j < numberOfVertices; j++) {
             /* 
              * The modulo of the sum of i and j allows us to account for the fact 
              * that Java indexes arrays from 0.
              */
             currentHamiltonianCycle[j] = (i + j) % numberOfVertices;   
         }
         for (int j = 1; j < numberOfVertices - 1; j++) {
             int nextVertex = j;
             for (int p = j + 1; p < numberOfVertices; p++) {
                 if (table[currentHamiltonianCycle[j - 1]][currentHamiltonianCycle[p]] < table[currentHamiltonianCycle[j - 1]][currentHamiltonianCycle[nextVertex]]) {
                           nextVertex = p;
                 }
             }
             
             int a = currentHamiltonianCycle[nextVertex];
             currentHamiltonianCycle[nextVertex] = currentHamiltonianCycle[j];
             currentHamiltonianCycle[j] = a;
         }
         
         /*
          * Find the total cost of the current Hamiltonian cycle.
          */
         double currentTotalCost = table[currentHamiltonianCycle[0]][currentHamiltonianCycle[numberOfVertices - 1]];
         for (int z = 0; z < numberOfVertices - 1; z++) {
             currentTotalCost += table[currentHamiltonianCycle[z]][currentHamiltonianCycle[z + 1]];
         }
         
         if (currentTotalCost < lowestTotalCost) {
             lowestTotalCost = currentTotalCost;
             shortestHamiltonianCycle = currentHamiltonianCycle;
         }
     }
     return shortestHamiltonianCycle;
 }

补充说明 #

我已经针对简单示例用纸笔推演了代码运行过程，没有发现算法实现存在问题，因此我认为该实现应该在通用场景下也能正常运行。

补充说明2 #

我用以下模拟测试用例测试了我的实现：

double[][] table = {{0, 2.3, 1.8, 4.5}, {2.3, 0, 0.4, 0.1}, 
                {1.8, 0.4, 0, 1.3}, {4.5, 0.1, 1.3, 0}}; 

它似乎输出了最近邻算法的预期结果：3 -> 1 -> 2 -> 0
我现在不确定是自动判分程序有问题，还是我的实现确实无法适配通用场景。

你的代码核心错误只有一个，和自动判分程序无关：

• Java中数组属于引用类型，你代码里写的shortestHamiltonianCycle = currentHamiltonianCycle只是把两个数组变量指向了同一块内存地址，后续循环修改currentHamiltonianCycle的时候，之前保存的最优路径也会被同步覆盖。你测试的简单用例刚好最优路径是最后一次循环生成的，所以结果正确，复杂用例中最优路径出现在前面的循环时，就会被后续修改覆盖，自然无法通过测试。
• 你的最近邻算法逻辑本身没有问题。

把最优路径赋值的逻辑改为数组深拷贝即可：
把

if (currentTotalCost < lowestTotalCost) {
    lowestTotalCost = currentTotalCost;
    shortestHamiltonianCycle = currentHamiltonianCycle;
}

修改为

if (currentTotalCost < lowestTotalCost) {
    lowestTotalCost = currentTotalCost;
    shortestHamiltonianCycle = Arrays.copyOf(currentHamiltonianCycle, numberOfVertices);
}

如果不希望导入java.util.Arrays工具类，也可以手动循环复制元素：

if (currentTotalCost < lowestTotalCost) {
    lowestTotalCost = currentTotalCost;
    for (int k = 0; k < numberOfVertices; k++) {
        shortestHamiltonianCycle[k] = currentHamiltonianCycle[k];
    }
}

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