欲張りアルゴリズムを使用している旅行営業担当者にキャストの問題がある

Question

私はアルゴリズムを解決する一般的な考え方を持っていますが、実装は私を逃しているようです。私がこれまで持っていることはこれです：

public class GreedySalesman { 


public static int[] greedySalesmanSolution(int[][] distances) { 
    List cityList = new ArrayList(); 
      for(int[] array: distances) { 
       cityList.add(Arrays.asList(array)); 
      } 
    List<Integer> initialResult = new ArrayList(); 
    initialResult.add(0); 
    List<Integer> finalResult = findMinDistance(cityList, cityList, initialResult, 0); 
      /*int finalResultArray = new int[finalResult.size()+1]; 
    int i = 0; 
    while (!(finalResult.isEmpty)) { 
       finalResultArray[i] = finalResult.poll(); 
       i++; 
    } 

    return finalResultArray; 
    */ 
      return null; 
     } 

public static List<Integer> findMinDistance(List<List<Integer>> initialCityInput, List<List<Integer>> cityInput, List<Integer> distanceResult, int index) { 
     if(cityInput.isEmpty()) { 
      distanceResult.add(0); 
      return distanceResult; 
     } 
     int min = Collections.min(initialCityInput.get(index)); 
     List<Integer> city = initialCityInput.get(index); 
     index = city.indexOf(min); 
     distanceResult.add(index); 
     cityInput.remove(city); 

     return findMinDistance(initialCityInput,cityInput,distanceResult,index); 

} 
} 

アルゴリズムはfindMinDistanceにそれを渡した後、距離を参照リストcityListを行い、その後、入力としてint型の2次元配列を取る、すなわち。コメントアウトされた部分は、findMinDistanceの結果がintの配列に変換され、finalResultArrayとして返される部分ですが、その部分はまだ重要ではありません。

findMinDistanceは、整数の2次元リストを2回取ります。結果の整数のリストとインデックスを表すintのリストです。 この関数は、cityInputが空になったときにdistanceResultを返します。それ以外の場合は、インデックスに基づいて最初の都市から開始し、そのリストおよびそのインデックスからの最小距離を取得し、distanceResultにインデックスを追加します。 これが完了すると、都市はcityInputから削除され、プログラムはcityInputが空になるまで再帰的に移動します。

私は現在取得しています問題は、いくつかのテストデータを使用してプログラムを実行しようとすると

int min = Collections.min(initialCityInput.get(index)); 

そしてメインでの I cannot be cast to java.lang.Integer です。 助けていただければ幸いです。

======

編集：私は自分のコードに変更を加え

public class GreedyTSP { 

    public int[] greedySalesmanSolution(int[][] distances) { 
       List<List<Integer>> cityList = new ArrayList(); 
       List<List<Integer>> initialCityList = new ArrayList(); 
       int iLength = distances.length; 
       for (int i = 0; i < iLength; ++i) { 
        int jLength = distances[0].length; 
        cityList.add(new ArrayList(jLength)); 
        initialCityList.add(new ArrayList(jLength)); 
        for (int j = 0; j < jLength; ++j) { 
         cityList.get(i).add(distances[i][j]); 
         initialCityList.get(i).add(distances[i][j]); 
        } 
       } 

     List<Integer> initialResult = new ArrayList(); 
     initialResult.add(0); 
     List<Integer> finalResult = findMinDistance(initialCityList, cityList, initialResult, 0); 
       int[] finalResultArray = new int[finalResult.size()]; 
       Iterator<Integer> iterator = finalResult.iterator(); 
       for (int i = 0; i < finalResultArray.length; i++){ 
        finalResultArray[i] = iterator.next().intValue(); 
       } 
     return finalResultArray; 


      } 

     public List<Integer> findMinDistance(List<List<Integer>> initialCityInput, List<List<Integer>> cityInput, List<Integer> distanceResult, int initialIndex) { 
      if(cityInput.isEmpty()) { 
       distanceResult.add(0); 
       return distanceResult; 
      } 
      List<Integer> city = initialCityInput.get(initialIndex); 
      Integer min = findMin(city, distanceResult, initialIndex); 
      int resultIndex = city.indexOf(min); 
      distanceResult.add(resultIndex); 
      cityInput.remove(city); 
      return findMinDistance(initialCityInput,cityInput,distanceResult,resultIndex); 
    } 

     public Integer findMin(List<Integer> city, List<Integer> distanceResult, int inputIndex) { 
      Integer min = Integer.MAX_VALUE; 
      for(int i = 0; i < city.size();i++) { 
       if (city.get(i) > inputIndex && city.get(i) < min) min = city.get(i); 
      } 
      int resultIndex = city.indexOf(min); 
      if(distanceResult.contains(resultIndex)) { 
       return findMin(city, distanceResult, inputIndex); 
      } 

      return min; 
     } 
} 

イムは、現時点ではすべてのキャストエラーを持っていないが、それは思われる部品の再帰を扱うプログラムがStackOverflowErrorを引き起こしています。私は今16時間文字通りこのことをやってきました。なぜ私はすべてのアイデアから外れています。何か案は？

Answer 1

あなたのキャストの問題点は、以下の

List<List<Integer>> initialCityInputは整数でリストを含むリストです。

したがって、initalCityInput.get(index)はintにキャストできないInt notをListとして返します。

Answer 2

まあ、私は少し周りを見て、私は基本的に多次元のArrayListを使用してタスクを過度に複雑ました。私はコードをかなり変更：

public class GreedyTSP { 

    public static int[] greedySolution(int[][] adjacencyMatrix) { 
     List<Integer> visitedCities = new ArrayList<>(); 
     int min = Integer.MAX_VALUE; 
     int startLocation = 0; 
     int tempStartLocation = 0; 
     int[] resultArray = new int[adjacencyMatrix.length+1]; 
     visitedCities.add(0); 


     while(visitedCities.size() < adjacencyMatrix.length){ 
      for(int i = 0; i < adjacencyMatrix.length; i++){ 
       if(!visitedCities.contains(i) && adjacencyMatrix[startLocation][i] < min){ 
        min = adjacencyMatrix[startLocation][i]; 
        tempStartLocation = i; 
       } 

      } 
      startLocation = tempStartLocation; 
      visitedCities.add(tempStartLocation); 
      min = Integer.MAX_VALUE; 
     } 

     visitedCities.add(0); 
     for(int i = 0; i < resultArray.length; i++){ 
      int temp = visitedCities.get(i); 
      resultArray[i] = temp; 
     } 
     return resultArray; 
    } 
} 

これは貪欲アルゴリズム