행렬에서 최단 경로를 찾는 데 문제가 있습니다.

Question

프로그램의 일부를 썼지 만 계속할 방법을 찾지 못했습니다. 이것은 제 숙제이며 10 일 동안 열심히 노력하고 있으며 시간이 곧 만료됩니다. 내 프로그램 요구 사항 : a) 키워드로 N을 입력으로 가져옵니다. b) 1과 N * N 사이의 임의의 정수를 생성하십시오. N c)이 정수로 행렬을 채우십시오. 이 작업을 수행했지만 더 많은 작업을 수행 할 수 없었습니다.

예 : 예를 들어 사용자가 입력 할 때 3을 입력합니다. 매트릭스

1 2~6

4 8 5

3 7 9

추천 프로그램 복귀 최단 경로 1,2,6,5,7이다. 다른 예시적인 사용자

14 11 6 8

15 3 16 1

104 2~5

12 9 7 13

같은 입력 및 프로그램 복귀 매트릭스 4 입력 최단 경로는 14,11,3,4,2,5,13, ​​

일 수 있으며 교차 단계는 경로에 허용되지 않습니다.

내 코드는 다음과 같습니다.

import java.util.*; 

public class Challenge1 { 

    public static void main(String[] args) { 
     Scanner input = new Scanner(System.in); 
     System.out.println("Enter a value for the matrix size."); 
     int length = input.nextInt(); 
     int[][] x = randomMatrix(length); 

     for (int i = 0; i < x.length; i++) { 
      for (int j = 0; j < x[i].length; j++) { 
       System.out.print(x[i][j] + " "); 
      } 
      System.out.println(); 
     } 
    } 

    public static int[][] randomMatrix(int n) { 
     Random r = new Random(); 
     int[][] matrix = new int[n][n]; 
     boolean[] trying = new boolean[n * n]; 
     for (int i = 0; i < matrix.length; i++) { 
      for (int j = 0; j < matrix[i].length; j++) { 
       matrix[i][j] = r.nextInt(n * n) + 1; 
       if (trying[matrix[i][j] - 1] == false) 
        trying[matrix[i][j] - 1] = true; 

       else { 
        while (trying[matrix[i][j] - 1] == true) { 
         matrix[i][j] = r.nextInt(n * n) + 1; 
        } 
        trying[matrix[i][j] - 1] = true; 
       } 
      } 
     } 
     return matrix; 
    } 

} 

Answer 1

여기에 제가 언급 한 해결책을위한 python-ish 의사 코드가 있습니다. shortestPath을 처음에는 비어있는 목록으로하고 shortestPathCost은 아직 발견되지 않은 최단 경로의 합계가되게하십시오. 초기 값은 +infinity입니다. 둘 다 전 세계적으로 볼 수 있습니다.

Procedure exhaustiveSearch (currentCost, currentPath, endNode): 
     currentNode = currentPath.last 
     if currentNode == endNode and currentCost < shortestPathCost: 
      shortestPath = currentPath 
      shortestPathCost = currentCost 
      return 

     for each neighbouringNode of currentNode not in currentPath: 
      exhaustiveSearch (currentCost + neighbouringNode.cost, 
          currentPath + neighbouringNode, 
          endNode) 

꽤 많이 있습니다. 매개 변수는 값으로 복사됩니다. 당신이 등을 호출 할 경우

shortestPath 및 shortestPathCost

exhaustiveSearch(0, [firstNode], endNode); 

하면 그리드의 가장 짧은 경로 중 하나를 개최 예정. 분명히 해결책은 Java보다 약간 높은 수준이지만 구현하기는 쉽습니다.