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

Question

我正在尝试使用本网站上给出的bactracking 解决Knight Tour问题.

在网站上给出的实现 在ideone上大约需要0.49秒.

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

而我实施的几乎相同的一个显示超过了ideone的时间限制(超过5秒).

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似乎有效:ideone.它可能只是搜索顺序,导致它更早地找到解决方案.

有太多可能的63,62,61等长度巡回赛无法到达最终的剩余方格.在最坏的情况下,蛮力搜索必须经历所有这些搜索.通过尝试一系列导致早期解决方案的移动,算法运行得很幸运.