旅行推销员问题（动态解）

问：

我已经设法实现了一个动态 TSP 算法，并且代码可以工作并运行，但它为更大的数据集产生了错误的输出

这是我的代码

    //TSP Dynamic Application
    public static int tspDynamic(int[][] costMatrix) 
    {
    int numCities = costMatrix.length;
    int numSets = 1 << numCities;
    int[][] dp = new int[numSets][numCities];

    // Initialize dp array with max values
    for (int[] row : dp) {
        Arrays.fill(row, Integer.MAX_VALUE / 2); // Divide by 2 to avoid integer overflow
    }
    
    dp[1][0] = 0; // Starting from city 0
    
    for (int set = 1; set < numSets; set += 2) {
        for (int u = 1; u < numCities; u++) {
            if ((set & (1 << u)) != 0) {
                for (int v = 0; v < numCities; v++) {
                    if ((set & (1 << v)) != 0 && u != v) {
                        dp[set][u] = Math.min(dp[set][u], dp[set ^ (1 << u)][v] + costMatrix[v][u]);
                    }
                }
            }
        }
    }
    
    int finalSet = (1 << numCities) - 1;
    int minCost = Integer.MAX_VALUE;
    for (int u = 1; u < numCities; u++) {
        minCost = Math.min(minCost, dp[finalSet][u] + costMatrix[u][0]);
    }
    
    return minCost;
}

A 在 17x17 矩阵上尝试了这个问题，它给出了正确的输出，但是当我在 33x33 矩阵或更高级别的矩阵上尝试它时。它总是给出错误的输出。您可以在此处找到 atsp 文件： https://drive.google.com/drive/folders/1IsmLCUlo9-LHKkXFICYDVyhdNHWjYxd_?usp=sharing 17x17 矩阵是 testFile.atsp

输出的答案可在此处获得 http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/ATSP.html

这是我的readfile方法

     public static int [][] ReadTSPFile(String file, String delimiter)
     {
     //declaration
     int [][] costMatrix = null;
     int numOfCities;
     int numCol = -1;

     try
     {
         BufferedReader br = new BufferedReader(new FileReader(file));
         
         //reads the first line to get #no of cities
         String line = br.readLine();
         numOfCities = Integer.parseInt(line);
         int no = 0;
         
         //skips the empty line
         br.readLine();
         
         //2D Array that stores cost matrix
         costMatrix = new int[numOfCities][numOfCities];
         
         //counter for rows
         int rows = 0;
         int columns  = 0;
         
         //reads remaining lines and populates the cost matrix
          while ((line = br.readLine()) != null && rows < numOfCities) 
          {
            no++;
            //splits by commas
            String[] values = line.trim().split(delimiter);
            
            if(numCol == -1)
            {
                numCol = values.length;
            }
            
                for (String value : values) 
                {
                    costMatrix[rows][columns] = Integer.parseInt(value);
                    columns++;

                if (columns >= numOfCities) 
                {
                    columns = 0;
                    rows++;

                    if (rows >= numOfCities) 
                    {
                        break; // Stop reading if you've filled the entire matrix
                    }
                }
            }

          }
         //closes the file reader
         br.close();
     }
     catch(IOException e )
     {
         e.printStackTrace();
     }

     return costMatrix;