0

再帰バックトラッキングを使用してナイト ツアー問題を解決しようとしています。誰かが私のコードを最適化するのを手伝ってくれますか? 私のコードは 6X6 ボードまで動作します。. N=7 を超えると、 を解くのにほぼ無限の時間がかかります。これが私のコードです:

#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 必要なライブラリ ファイルを含む空のプロジェクト

4

3 に答える 3

1

まず、これを取り除きます：

Vector<position> nextSquareList = calulateNextSquare(board,square);

各ステップでベクターを作成するには、多くの時間がかかります。配列を使用するか (8 つの可能な移動があることがわかっているため、固定サイズ)、ループを完全に展開することができます。あなたのものに似たこのバージョンと比較してください。

于 2011-10-06T15:48:52.410 に答える
0

ボードのコピーをcalculateNextSquareに渡しますが、このメソッドでは必要ないようです。

また、このメソッドでベクトルを返しますが、参照によって渡す必要があります。

于 2011-10-06T15:55:49.737 に答える
0

私が提案したいいくつかの変更：

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

ただし、指数関数的な複雑さは依然として残っており、コードを最適化してもそれは変わらないことに注意してください。

于 2011-10-06T15:49:15.990 に答える