为什么两个几乎相同的实现有很大的执行时间差？

我正在尝试使用作为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; 
}

虽然我实现的几乎相同的是。

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

什么在我的代码中执行了这么久？

来源

2012-07-28 Eight

你有没有尝试分析你的代码，看看它花费的时间？在这两种情况下'isSafe'功能是否相同？ – 2012-07-28 13:57:15

是的，isSafe在两者中都是一样的。请参阅我的完整代码http://ideone.com/RP068，其他代码在这里http://ideone.com/qfsf3 – Eight 2012-07-28 14:00:08

您的代码版本由于某种原因永远运行。看不出明显的原因。我建议再次查看代码，看看有什么不同。 – gnobal 2012-07-28 14:07:26

更改xMoves/yMoves似乎工作：ideone。它可能只是搜索顺序导致它更早地找到解决方案。

有太多的可能63，62，61周长度之旅不能达到最终保留的方格。在最坏的情况下，蛮力搜索必须经历所有这些。通过尝试一系列导致早期解决方案的动作，工作的算法变得很幸运。

来源

2012-07-28 14:01:14 fgb

太棒了...非常感谢。你还解释了这种行为的原因？请。 – Eight 2012-07-28 14:11:25

您的文章不显示您的代码和原来的代码之间的区别。
逸岸，如果你在你的代码仔细一看，只有你和那个合适的人之间是这样的：

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

的顺序是不同的。你在纸上画出可能的动作，并且你可以发现正确的一个是逆时针的，而你的是完全混乱的。
这一定是导致你的问题的原因。

来源

2012-07-28 16:30:42 duleshi

为什么两个几乎相同的实现有很大的执行时间差？

回答

相关问题