알고리즘 - 긴 경로 그리드 퍼즐

그래서 상황은 다음과 같습니다 그것은 사각형 격자가 그래서
1.에서는 N × N 그리드가
2. 내부
3. 모든 셀을 받게됩니다 단계의 최대 금액이 될 것입니다 그리드에는 최대 금액을 줄이는 특정 금액이 있습니다
4. 우회전과 우회전 만 가능합니다.
5. 시작점은 그리드의 왼쪽 상단이고 목표는 그리드의 오른쪽 하단입니다.
6. 우리는 가장 긴 경로 결과가 그 것이다알고리즘 - 긴 경로 그리드 퍼즐

그래서 현재 내가 이미 코드를 작성 -1 것
7. 어떤 경로 수있는 경우 (왼쪽 단계의 최소 최대 값을 가진 하나를) 결정해야 어떤 경우에는 작동하지만 여전히 최적의 상태는 아닙니다.
내가 지금하고있는 일은 다음과 같습니다.
1. 다음 올바른 값과 그 이하의 값이 있는지 확인하십시오.
2. 더 큰 값으로 이동하십시오.
3. 최대 스텝 량이 0이되면 이전 셀로 역 추적하고 다른 방향으로 이동하십시오.
4. 올바른 값과 아래 값이 같으면 다음 셀 다음의 셀을 검사합니다.

문제는 4 번째 포인트와 같습니다. 나는 X가 기회 오른쪽 값이 X보다 큰 수 있도록 Y 단계의 수는 더 큰 Y보다 큰 경우 대체가 추측

private static int determineBestNext(int[][] grid, int currentX, int currentY) { 
    int nextRight = 0; 
    int nextBelow = 0; 
    int numberOfRows = grid.length - 1; 
    for(int i=currentX+1;i<numberOfRows-1;i++) { 
     nextRight += grid[currentY][i+1]; 
     if(currentY != numberOfRows) { 
      nextRight += grid[currentY+1][i+1]; 
     } 
    } 
    for(int i=currentY+1;i<numberOfRows-1;i++) { 
     nextBelow = grid[i+1][currentX]; 
     if(currentX != numberOfRows) { 
      nextBelow += grid[i+1][currentX+1]; 
     } 
    } 
    if(nextRight > nextBelow) { 
     return 1; 
    } else if (nextBelow > nextRight) { 
     return 2; 
    } else { 
     return determineBestNext(grid, currentX+1,currentY+1); 
    } 
}

이 4 점에 대한 내 코드입니다 그 반대.

다른 생각이 있으십니까? 감사!

감사합니다.

출처

2014-12-04 Niko Adrianus Yuwono

O(n^2)에서 가장 좋은 경로를 찾을 수 있습니다. 왼쪽 위 셀 (시작점)과 격자 (i, j)를 셀의 값으로 (1,1) 호출합니다. 그리고 단계 (i, j)는 셀 (i, j)에 도달하는 데 필요한 최소한의 단계입니다. 만 하나의 가능한 경로가 있기 때문에

빠르게, 그것도 쉽게 i = 1 또는 j = 1 또는 i = j = 1 경우 관계

steps(i,j) = min(steps(i-1,j), steps(i,j-1)) + grid(i,j) // if i,j > 1

를 식별 할 수 있습니다.

steps(N,N)을 계산하려면 steps(N,N) = min(steps(N-1,N), steps(N,N-1)) + grid(N,N)이 필요합니다. 계산을 위해서는 steps(N-1,N)과 steps(N,N-1)이 필요합니다. 따라서 steps(N-1,N) = min(steps(N-2,N), steps(N-1,N-1)) + grid(N-1,N) 및 steps(N,N-1) = min(steps(N-1,N-1), steps(N,N-2)) + grid(N,N-1)입니다. 이 결과 각각에 대해 steps(N-1,N-1) 값이 필요하다는 것을 알 수 있습니다. 이 값을 두 번 계산하는 것은 허리입니다. 우리가 하나만 계산하고 그 값을 기억한다면, 우리는 하나의 계산을 저장할 수 있습니다. 이러한 일은 매우 자주 발생합니다.

기억할 가장 좋은 방법은 고정 된 평가 순서를 유지하는 것입니다. 7 날 당신은 몇 가지 세부 사항을 놓치고 있다고 생각합니다

function getBestPath(grid, N) 
    steps = new N x N int-array //initialized with 0 

    //first row 
    steps[0][0] = grid[0][0] 
    // only one path to get to (0,0), it's doing nothing 
    for (i = 1; i < N; i++) 
     steps[0][i] = steps[0][i-1] + grid[0][i] 
     // only one path each, just going right 

    //other rows 
    for (row = 1; row < N; row++) 
     steps[row][0] = steps[row-1][0] + grid[row][0] 
     //only one way to get to (row,0), only go down 

     for (i = 1; i < N; i++) 
      steps[row][i] = min(steps[row-1][i], steps[row][i-1]) + grid[row][i] 

    return steps[N-1][N-1]

출처

2014-12-04 09:08:50 user38034

내 질문에 약간의 오해가있을 것이라고 생각하지만 답은 나를 이끌어 줄 것입니다. 실제로 내가 얻고 싶은 것은 최단 경로가 아니라 가장 값 비싼 경로입니다. –

포인트 : 는 여기에 몇 가지 의사 코드입니다.

경로가없는 경우는 언제입니까? 단계의 양이 음수가 아니어야한다는 가정입니까?

그렇지 않은 경우 경로가 항상 가능하며 다른 대답과 마찬가지로 쉬운 동적 프로그래밍 O (N^2) 알고리즘이 가능합니다.

문제를 수정하고 프로세스의 중요한 세부 사항을 빠뜨려 일부 프로그래밍 테스트를 속이려고합니까?

출처

2014-12-04 16:45:08 AnswerCommenteratinator

알고리즘 - 긴 경로 그리드 퍼즐

답변

관련 문제