骑士之旅C++
我正在尝试使用递归回溯来解决骑士之旅问题。有人可以帮助我优化我的代码。我的代码工作到6X6板。 。在N = 7之后,需要几乎无限的时间来解决。 这里是我的代码:骑士之旅C++
#include <iostream>
#include "genlib.h"
#include "grid.h"
#include "vector.h"
#include <iomanip>
const int NOT_VISITED = -1;
//Size of the board
const int N = 6;
const int N2 = N*N;
typedef Grid<int> chess;
struct position{
int row;
int col;
};
//Initializes the board and makes each and every
//square value as NOT_VISITED
void initializeBoard(chess &board)
{
for(int i=0;i<board.numRows();i++)
for(int j=0;j<board.numCols();j++)
board[i][j] = NOT_VISITED;
}
//Returns true if the square is visited;
bool visited(chess &board,position square)
{
return board[square.row][square.col ] != NOT_VISITED;
}
//Returns true if the givien position variable is outside the chess board
bool outsideChess(chess &board, position square)
{
if(square.row <board.numRows() && square.col <board.numCols() && square.row >=0 && square.col >=0)
return false;
return true;
}
void visitSquare(chess &board,position square,int count)
{
board[square.row] [square.col] = count;
}
void unVisitSquare(chess &board,position square)
{
board[square.row] [square.col] = NOT_VISITED;
}
position next(position square,int irow, int icol)
{
square.row += irow;
square.col += icol;
return square;
}
Vector<position> calulateNextSquare(chess board,position square)
{
Vector<position> list;
for(int i=-2;i<3;i=i+4)
{
for(int j=-1;j<2;j=j+2)
{
list.add(next(square,i,j));
list.add(next(square,j,i));
}
}
return list;
}
bool knightTour(chess &board,position square, int count)
{
//cout<<count<<endl;
//Base Case if the problem is solved;
if(count>N2)
return true;
if(outsideChess(board,square))
return false;
//return false if the square is already visited
if(visited(board,square))
return false;
visitSquare(board,square,count);
Vector<position> nextSquareList = calulateNextSquare(board,square);
for(int i=0;i<nextSquareList.size();i++)
if(knightTour(board, nextSquareList[i], count+1))
return true;
unVisitSquare(board,square);
return false;
}
void printChess(chess &board)
{
for(int i=0;i<board.numRows();i++)
{
for(int j=0;j<board.numCols();j++)
cout<<setw(4)<<board[i][j];
cout<<endl;
}
}
int main()
{
chess board(N,N);
initializeBoard(board);
position start;
start.row = 0; start.col = 0;
if(knightTour(board,start,1))
printChess(board);
else
cout<<"Not Possible";
return 0;
}
我使用斯坦福106B库(网格是2维向量) 的Visual Studio 2008与所需的库文件https://docs.google.com/viewer?a=v&pid=explorer&chrome=true&srcid=0BwLe9NJT8IreNWU0N2M5MGUtY2UxZC00ZTY2LWE1YjQtMjgxYzAxMWE3OWU2&hl=en空白项目
我会说,一开始,摆脱这个:
Vector<position> nextSquareList = calulateNextSquare(board,square);
创建一个向量在每一步都需要很多时间。你可以使用一个数组(固定大小,因为你知道有8个可能的移动),或者unroll the loop entirely。与this version, similar to yours比较。
感谢它的工作! – Ganesh
一些修改,我想建议:
#include <iostream>
#include "genlib.h"
#include "grid.h"
#include "vector.h"
#include <iomanip>
const int NOT_VISITED = -1;
//Size of the board
const int N = 6;
const int N2 = N*N;
typedef int chess[N][N]; // <------------- HERE
struct position{
int row;
int col;
};
//Initializes the board and makes each and every
//square value as NOT_VISITED
void initializeBoard(chess &board)
{
for(int i=0;i<board.numRows();i++)
for(int j=0;j<board.numCols();j++)
board[i][j] = NOT_VISITED;
}
//Returns true if the square is visited;
bool visited(chess &board,position square)
{
return board[square.row][square.col ] != NOT_VISITED;
}
//Returns true if the givien position variable is outside the chess board
bool outsideChess(chess &board, position square)
{
if(square.row <board.numRows() && square.col <board.numCols() && square.row >=0 && square.col >=0)
return false;
return true;
}
void visitSquare(chess &board,position square,int count)
{
board[square.row] [square.col] = count;
}
void unVisitSquare(chess &board,position square)
{
board[square.row] [square.col] = NOT_VISITED;
}
position next(position square,int irow, int icol)
{
square.row += irow;
square.col += icol;
return square;
}
void calulateNextSquare(chess board,position square, Vector<position>& list) // <------------- HERE
{
// ------------- HERE
//Also, change this part to add only unvisited and not out-of-board positions.
for(int i=-2;i<3;i=i+4)
{
for(int j=-1;j<2;j=j+2)
{
list.add(next(square,i,j));
list.add(next(square,j,i));
}
}
}
bool knightTour(chess &board,position square, int count)
{
//cout<<count<<endl;
//Base Case if the problem is solved;
if(count>N2)
return true;
if(outsideChess(board,square))
return false;
//return false if the square is already visited
if(visited(board,square))
return false;
visitSquare(board,square,count);
Vector<position> nextSquareList; // <------------- HERE
calulateNextSquare(board,square,nextSquareList);
for(int i=0;i<nextSquareList.size();i++)
if(knightTour(board, nextSquareList[i], count+1))
return true;
unVisitSquare(board,square);
return false;
}
void printChess(chess &board)
{
for(int i=0;i<board.numRows();i++)
{
for(int j=0;j<board.numCols();j++)
cout<<setw(4)<<board[i][j];
cout<<endl;
}
}
int main()
{
chess board(N,N);
initializeBoard(board);
position start;
start.row = 0; start.col = 0;
if(knightTour(board,start,1))
printChess(board);
else
cout<<"Not Possible";
return 0;
}
但请注意,您仍然有exponential的复杂性,并优化你的代码不会改变它。
您正在传递董事会副本来计算下一个广场,但看起来你并不需要这种方法。
另外,你在这个方法中返回一个向量,但是你应该通过引用来传递它。
尝试通过董事会和向量参考..仍然需要很多时间... – Ganesh
@Ganesh递归回溯不是解决这个问题的最佳途径。它花费了很多时间而不使用某些学科 –
“几乎无限”? – spraff
冉半个小时仍然无法获得8X8输出..即使它没有无限但仍然是它的很多时间,这样的问题... – Ganesh