두 개의 거의 동일한 구현이 큰 실행 시간 차이가 나는 이유는 무엇입니까?

Question

나는 on this site으로 bactracking을 사용하여 Knight Tour problem을 해결하려고합니다.

구현 사이트에서 주어진 takes about 0.49 seconds on ideone.

int solveKTUtil(int x, int y, int movei, int sol[N][N], int xMove[N], 
       int yMove[N]) 
{ 
    int k, next_x, next_y; 
    if (movei == N*N) 
     return true; 

    /* Try all next moves from the current coordinate x, y */ 
    for (k = 0; k < 8; k++) 
    { 
     next_x = x + xMove[k]; 
     next_y = y + yMove[k]; 
     if (isSafe(next_x, next_y, sol)) 
     { 
     sol[next_x][next_y] = movei; 
     if (solveKTUtil(next_x, next_y, movei+1, sol, xMove, yMove) == true) 
      return true; 
     else 
      sol[next_x][next_y] = -1;// backtracking 
     } 
    } 

    return false; 
} 

거의 동일 내게로 구현 한 동안 showing time limit exceeded(more than 5 seconds) on ideone입니다.

int generateMoves(int x, int y, int moveNum, int soln[][N], int xMoves[], int yMoves[])//making move number 'moveNum' from x and y. 
{ 
     if(moveNum == N*N){ 
       return 1; 
     } 
     else{ 
       int i, nextX, nextY; 
       for(i=0; i<8; ++i){ 
         nextX = x + xMoves[i]; 
         nextY = y + yMoves[i]; 

         if(isSafe(nextX, nextY, soln)){ 
           soln[nextX][nextY] = moveNum; 
           if(generateMoves(nextX, nextY, moveNum+1, soln, xMoves, yMoves)){ 
             return 1; 
           } 
           else{ 
             soln[nextX][nextY] = -1; 
           } 
         } 
       } 
       return 0; 
     } 
} 

내 코드에 너무 오래 무엇을 실행?

Answer 1

xMoves/yMoves를 변경하면 작동합니다.. 검색 순서에 따라 솔루션을 더 빨리 찾을 수 있습니다.

마지막 남은 사각형에 도달 할 수없는 63, 62, 61 등 길이 투어가 너무 많습니다. 무차별 강제 검색은 최악의 경우 모두를 통과해야합니다. 효과가있는 알고리즘은 솔루션을 조기에 발견하여 운이 좋았습니다.

Answer 2

귀하의 게시물은 귀하의 코드와 원래의 것의 차이를 나타내지 않습니다. 주의 깊게 코드를 보면
Infact는은, 오직 당신과 올바른 사이는 다음과 같습니다

int xMoves[] = { 2, 1, -1, -2, -2, -1, 1, 2 };//{2, 2, 1, 1, -1, -1, -2, -2}; 
int yMoves[] = { 1, 2, 2, 1, -1, -2, -2, -1 };//{1, -1, -2, 2, -2, 2, -1, 1}; 

순서가 다르다. 가능한 움직임을 종이에 그리면 오른쪽에있는 순서가 반 시계 방향으로 이루어지고 완전히 혼란 스럽습니다.
그 원인으로 인해 문제가 발생했습니다.