Number Maze Solving 알고리즘

Question

나는 "number maze"라고 불리는 독특한 형태의 미로에 대한 해법을 연구 중이다. 본질적으로 당신이있는 모든 위치는 다음 가능한 이동 위치 (위, 아래, 대각선)를 나타내는 숫자 (1-4)입니다. 여기에 내가 말하는 것을 분명히하는 그림이있다.

마지막으로, 모든 위치가 한 번만 방문 할 수 있습니다. 목표는 미로를 통해 가장 긴 경로를 찾을 수있게하는 것입니다.

현재 내가 성공적으로 각각의 위치에서 가능한 움직임을 찾아 미로에서 가능한 모든 경로를 통해 반복 할 수 있습니다. 이 프로그램은 미로의 "끝"이 무엇인지 알지 못하지만 나중에 구현하기 쉽습니다. 현재 내가 가지고있는 문제는 가능한 모든 경로를 분석하고 어느 경로가 가장 길 냐를 알아 내기 위해 "경로 메모리"를 구현하는 방법을 모르겠다는 것입니다. 본질적으로 나는 모든 다른 경로를 저장하고 분석 할 방법이 필요합니다. 나는 ArrayList<String> MovePath으로 그렇게하려고 시도했지만, 결국 작동하지 않게되었습니다. 나는 이것의 전체 재귀 측면이 나를 트립시키고 있다고 생각한다. 내 코드의 모든 중요한 부분이 아래에 게시됩니다. 모든 포인터는 감사하겠습니다.

private static String changeString(String currentstring, String addendum) { 
     return currentstring + addendum; 
    } 

static ArrayList<String> solve(int X, int Y, String path, ArrayList<String> MovePath, int[][] PuzzleBoard) { 

     if (PuzzleBoard[X][Y] == 0) { 
      //If current position is blank, don't attempt to find moves 

    } else { 

     ArrayList<Point> AllMoves = FindMoves(PuzzleBoard, X, Y); //Find possible moves from current board location based on piece type 


     for (int i = 0; i < AllMoves.size(); i++) {//Iterate through possible moves 
      PuzzleBoard[X][Y] = 0; //set current position to 0 (empty) 
      X = (int) AllMoves.get(i).getX();//get move X coordinate 
      Y = (int) AllMoves.get(i).getY();//get move Y coordinate 

      String xstring = String.valueOf(X); 
      String ystring = String.valueOf(Y); 

      path = changeString(path, xstring);//Adds the current X coordinate to a string 
      path = changeString(path, ystring);//Adds the current Y coordinate to a string 

      MovePath.add(path); 

      solve(X, Y, path, MovePath, PuzzleBoard); 

     } 
    } 

    return MovePath; 
} 

public static void main(String[] args) { 

    int[][] BoardArray = new int[][]{ 
      {4, 0, 0, 0, 1, 0}, 
      {0, 1, 1, 1, 1, 0}, 
      {0, 1, 0, 0, 3, 0}, 
      {0, 0, 2, 0, 0, 0}, 
      {0, 0, 0, 0, 0, 0}, 
      {0, 0, 3, 0, 1, 9} 
     //0 = empty 
     //9 = end 

    int x = 0; //starting x 
    int y = 0; //starting y 
    String paths = ""; 
    ArrayList<String> MovePath = new ArrayList<String>(); 
    ArrayList<String> Answer = new ArrayList<String>(); 

    Answer = solve(x, y, paths, MovePath, BoardArray) 

    String longestpath = Collections.max(Answer, Comparator.comparing(s -> s.length())); 
    System.out.println(longestpath); 

} 

은}

Answer 1

내 첫번째 생각은 모두 완성 된 경로 후 업데이트됩니다 최대 경로를 포함하는 VAR를 추가합니다. 재귀 깊이를 저장하고 완료 후 최대 값과 비교합니다.

Answer 2

나는 당신이 작은 부분에서 문제를 휴식하고 그것을 해결 제안 :

1 그것은 문제를 찾는 간단한 그래프 최단 경로입니다. 첫 번째 단계는 데이터에서 그래프 행렬을 만드는 것입니다. 숫자가있는 노드는 해당 셀에 표시된 번호의 비용으로 인접 노드 (n 노드 떨어져있는 노드)로 이동할 수 있으므로 (0,0)에서 (0,4)/(4,0)/(4/4)으로 이동하는 비용은 4입니다. 내가 언급으로, (최단 경로) 그래프

2에 문제점을 줄일 수 있도록 솔루션에 원하는 경로를 찾는 알고리즘을 구현합니다. 나는 더 빠른 Dijkstra 또는 A* 알고리즘을 제안하지만, 원할 경우 depth first 또는 breadth first 검색을 시도 할 수도 있습니다. 이러한 알고리즘을 인터넷에 구현하는 방법에 대한 많은 자습서와 예제가 있습니다. Dijkstra에 대해 this, A*에 대해 this을 찾았습니다.

3- (가능한 가장 긴 경로에 대한) 모든 가중치를 무효로하고 최단 경로를 찾을 수 벨만 - 포드 알고리즘을 사용합니다. 당신이 모든 무게를 무효화했기 때문에 당신은 결과로서 가장 긴 길을 발견 할 것입니다. This 당신을 도울 수있다.