탐욕스러운 알고리즘을 사용하여 여행중인 영업 사원에게 캐스팅 관련 문제가 있음

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); 

} 
} 

알고리즘 후, 다음의 거리를 참조하는리스트 cityList을, 입력으로하는 int 이차원 배열을 findMinDistance로 전달할 것이다 제가 지금까지이하면이된다. 주석 처리 된 부분은 findMinDistance의 결과가 int 배열로 변환되어 finalResultArray로 반환되지만 해당 부분은 아직 중요하지 않습니다.

findMinDistance는 정수의 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-s가 발생하고 있습니다. 나는 문자 그대로 16 시간 동안이 일을 어지럽 혀왔다. 그리고 나는 왜 그런지에 대한 아이디어가 없다. 어떤 아이디어?

Answer 1

귀하의 캐스팅 문제는 다음과 같은

List<List<Integer>> initialCityInput 정수와 목록을 포함하는 목록입니다.

따라서 initalCityInput.get(index)은 not not int를 반환하며 int로 캐스트 할 수 없습니다.

Answer 2

글쎄, 조금 주위를 둘러 보았고 기본적으로 다차원 arraylists를 사용하여 작업을 과도하게 복잡하게 만들었습니다. 내가 코드를 꽤 변경 :

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; 
    } 
} 

이것은 욕심 알고리즘