c++ - ナイトのツアーアルゴリズムを最適化するには?

Question

Backtrackingメソッドを使用して、C++ でKnight's tourアルゴリズムをコーディングします。しかし、n > 7 (7 x 7 のチェス盤よりも大きい) の場合、遅すぎるか無限ループに陥っているようです。

問題は次のとおりです: このアルゴリズムの時間計算量はどのくらいですか? また、どのように最適化すればよいでしょうか?!

---

Knight's Tour 問題は、次のように記述できます。

n × n マスのチェス盤が与えられたとき、騎士がすべてのマスを 1 回だけ訪れる道を見つけてください。

これが私のコードです：

#include <iostream>
#include <iomanip>

using namespace std;

int counter = 1;
class horse {
  public:
    horse(int);
    bool backtrack(int, int);
    void print();
  private:
    int size;
    int arr[8][8];
    void mark(int &);
    void unmark(int &);
    bool unvisited(int &);
};

horse::horse(int s) {
    int i, j;
    size = s;
    for (i = 0; i <= s - 1; i++)
        for (j = 0; j <= s - 1; j++)
            arr[i][j] = 0;
}

void horse::mark(int &val) {
    val = counter;
    counter++;
}

void horse::unmark(int &val) {
    val = 0;
    counter--;
}

void horse::print() {
    cout << "\n - - - - - - - - - - - - - - - - - -\n";
    for (int i = 0; i <= size - 1; i++) {
        cout << "| ";
        for (int j = 0; j <= size - 1; j++)
            cout << setw(2) << setfill ('0') << arr[i][j] << " | ";
        cout << "\n - - - - - - - - - - - - - - - - - -\n";
    }
}

bool horse::backtrack(int x, int y) {
    if (counter > (size * size))
        return true;

    if (unvisited(arr[x][y])) {
        if ((x - 2 >= 0) && (y + 1 <= (size - 1))) {
            mark(arr[x][y]);
            if (backtrack(x - 2, y + 1))
                return true;
            else
                unmark(arr[x][y]);
        }
        if ((x - 2 >= 0) && (y - 1 >= 0)) {
            mark(arr[x][y]);
            if (backtrack(x - 2, y - 1))
                return true;
            else
                unmark(arr[x][y]);
        }
        if ((x - 1 >= 0) && (y + 2 <= (size - 1))) {
            mark(arr[x][y]);
            if (backtrack(x - 1, y + 2))
                return true;
            else
                unmark(arr[x][y]);
        }
        if ((x - 1 >= 0) && (y - 2 >= 0)) {
            mark(arr[x][y]);
            if (backtrack(x - 1, y - 2))
                return true;
            else
                unmark(arr[x][y]);
        }
        if ((x + 2 <= (size - 1)) && (y + 1 <= (size - 1))) {
            mark(arr[x][y]);
            if (backtrack(x + 2, y + 1))
                return true;
            else
                unmark(arr[x][y]);
        }
        if ((x + 2 <= (size - 1)) && (y - 1 >= 0)) {
            mark(arr[x][y]);
            if (backtrack(x + 2, y - 1))
                return true;
            else
                unmark(arr[x][y]);
        }
        if ((x + 1 <= (size - 1)) && (y + 2 <= (size - 1))) {
            mark(arr[x][y]);
            if (backtrack(x + 1, y + 2))
                return true;
            else
                unmark(arr[x][y]);
        }
        if ((x + 1 <= (size - 1)) && (y - 2 >= 0)) {
            mark(arr[x][y]);
            if (backtrack(x + 1, y - 2))
                return true;
            else
                unmark(arr[x][y]);
        }
    }
    return false;
}

bool horse::unvisited(int &val) {
    if (val == 0)
        return 1;
    else
        return 0;
}

int main() {
    horse example(7);
    if (example.backtrack(0, 0)) {
        cout << " >>> Successful! <<< " << endl;
        example.print();
    } else
        cout << " >>> Not possible! <<< " << endl;
}

上記の例 (n = 7) の出力は次のようになります。

Answer 1

各ステップでチェックする可能性が 8 つあり、これを各セル (最後のセルを除く) に対して実行する必要があるため、このアルゴリズムの時間の複雑さは O(8^(n^2-1)) = O(8^( n^2)) ここで、n はチェックボードの端にある正方形の数です。正確に言うと、これは最悪の場合の時間の複雑さです (何も見つからない場合、または最後の可能性がある場合に、すべての可能性を調査するのにかかる時間)。

最適化に関しては、2 種類の改善があります。

実装の改善

x-2、x-1、x+1、x+2 を計算しており、y についても少なくとも 2 倍の時間を計算しています。次のように書き直すことをお勧めします。

int sm1 = size - 1;
int xm2 = x - 2;
int yp1 = y + 1;
if((xm2 >= 0) && (yp1 <= (sm1))){
    mark(arr[x][y]);
    if(backtrack(xm2, yp1))
        return true;
    else
        unmark(arr[x][y]);
}

int ym1 = y-1;
if((xm2 >= 0) && (ym1 >= 0)){
    mark(arr[x][y]);
    if(backtrack(xm2, ym1))
        return true;
    else
        unmark(arr[x][y]);
}

後続のブロックでも事前計算された値が再利用されていることに注意してください。これは、私が観察していたものよりも効果的であることがわかりました。つまり、変数の割り当てとリコールは、操作を再度実行するよりも高速です。また、毎回計算するのではなく、コンストラクターにsm1 = s - 1;andを保存することも検討してください。area = s * s;

ただし、これ (実装の改善であり、アルゴリズムの改善ではありません) は、時間の複雑さの順序を変更せず、時間を特定の係数で分割するだけです。私は時間の複雑さ O(8^(n^2)) = k*8^(n^2) を意味し、違いはより低い k ファクターになります。

アルゴリズムの改善

私はこれを考えることができます：

• 対角線のセルで開始するツアーごとに (例のように (0,0) で開始するなど)、最初の移動のみが対角線によって作成された 2 つのハーフ チェックボードの 1 つにあると見なすことができます。
  • これは対称性のためか、2 つの対称解が存在するか、またはまったく存在しません。
  • これにより、その場合は O(4*8^(n^2-2)) が得られますが、対称でない場合も同じです。
  • 再び注意してください O(4*8^(n^2-2)) = O(8^(n^2))
• なんらかのグローバルな状況により、現在のマーキングを考えると解決策が不可能であることが示唆される場合は、ラッシュを早期に中断してみてください。
  • たとえば、馬は 2 つのバルク列または行をジャンプすることはできないため、2 つのバルク マークされた列 (または行) とマークされていないセルが両側にある場合、解決策はありません。更新された列/行ごとにマークされたセルの数を維持する場合、これは O(n) でチェックできると考えてください。次に、各マーキングの後にこれをチェックすると、n < = 8 の場合に O(n*8^(n^2)) 時間が追加されます。counter % 8 == 4例以上のチェックcounter > 2*n && counter % 8 == 4
• 検索を早期に巧みに中断する他のアイデアを見つけますが、8 つのオプションを持つバックトラック アルゴリズムは常に O(8^(2^n)) の性質を持つことを覚えておいてください。

さよなら

Answer 2

これが私の2セントです。基本的なバックトラッキング アルゴリズムから始めました。あなたが言及したように、n> 7を無期限に待っていました。warnsdorff ルールを実装したところ、魔法のように機能し、n = 31 までのサイズのボードで 1 秒未満で結果が得られました。n > 31 の場合、再帰の深さが制限を超えたため、stackoverflow エラーが発生していました。warnsdorff ルールの問題とさらなる最適化の可能性について話しているこちらのより良い議論を見つけることができました。

参考までに、warnsdorff最適化を使用したKnight's Tour問題のPython実装を提供しています

    def isValidMove(grid, x, y):
            maxL = len(grid)-1
            if x  maxL or y  maxL or grid[x][y] > -1 :
                    return False
            return True

    def getValidMoves(grid, x, y, validMoves):
            return [ (i,j) for i,j in validMoves if isValidMove(grid, x+i, y+j) ]

    def movesSortedbyNumNextValidMoves(grid, x, y, legalMoves):
            nextValidMoves = [ (i,j) for i,j in getValidMoves(grid,x,y,legalMoves) ]
            # find the number of valid moves for each of the possible valid mode from x,y
            withNumNextValidMoves = [ (len(getValidMoves(grid,x+i,y+j,legalMoves)),i,j) for i,j in nextValidMoves]
            # sort based on the number so that the one with smallest number of valid moves comes on the top
            return [ (t[1],t[2]) for t in sorted(withNumNextValidMoves) ]


    def _solveKnightsTour(grid, x, y, num, legalMoves):
            if num == pow(len(grid),2):
                    return True
            for i,j in movesSortedbyNumNextValidMoves(grid,x,y,legalMoves):
            #For testing the advantage of warnsdorff heuristics, comment the above line and uncomment the below line
            #for i,j in getValidMoves(grid,x,y,legalMoves):
                    xN,yN = x+i,y+j
                    if isValidMove(grid,xN,yN):
                            grid[xN][yN] = num
                            if _solveKnightsTour(grid, xN, yN, num+1, legalMoves):
                                    return True
                            grid[xN][yN] = -2
            return False

    def solveKnightsTour(gridSize, startX=0, startY=0):
            legalMoves = [(2,1),(2,-1),(-2,1),(-2,-1),(1,2),(1,-2),(-1,2),(-1,-2)]
            #Initializing the grid
            grid = [ x[:] for x in [[-1]*gridSize]*gridSize ]
            grid[startX][startY] = 0
            if _solveKnightsTour(grid,startX,startY,1,legalMoves):
                    for row in grid:
                            print '  '.join(str(e) for e in row)
            else:
                    print 'Could not solve the problem..'

Answer 3

アルゴリズムを調べます。再帰の各深さで、ボード上にある 8 つの可能な手のそれぞれを調べてから、その位置を再帰的に処理します。この展開を最もよく表す数式は?

ボードのサイズが int[8][8] に固定されている場合は、動的にする必要があるかもしれません。

class horse
{
    ...
    int** board; //[s][s];
    ...
};

horse::horse(int s)
{
    int i, j;
    size = s;
    board = (int**)malloc(sizeof(int*)*size);
    for(i = 0; i < size; i++)
    {
        board[i] = (int*)malloc(sizeof(int)*size);
        for(j = 0; j < size; j++)
        {
            board[i][j] = 0;
        }
    }
}

ボードの移動が合法であることを確認する関数を追加して、テストを少し変更します。

bool canmove(int mx, int my)
{
    if( (mx>=0) && (mx<size) && (my>=0) && (my<size) ) return true;
    return false;
}

mark() と unmark() は非常に反復的であることに注意してください。実際には、ボードを mark() し、すべての正当な動きをチェックし、backtrack() が true を返さない場合は位置を unmark() するだけで済みます。

関数を書き直すと、すべてが少し明確になります。

bool horse::backtrack(int x, int y)
{

    if(counter > (size * size))
        return true;

    if(unvisited(board[x][y]))
    {
        mark(board[x][y]);
        if( canmove(x-2,y+1) )
        {
            if(backtrack(x-2, y+1)) return true;
        }
        if( canmove(x-2,y-1) )
        {
            if(backtrack(x-2, y-1)) return true;
        }
        if( canmove(x-1,y+2) )
        {
            if(backtrack(x-1, y+2)) return true;
        }
        if( canmove(x-1,y-2) )
        {
            if(backtrack(x-1, y-2)) return true;
        }
        if( canmove(x+2,y+1) )
        {
            if(backtrack(x+2, y+1)) return true;
        }
        if( canmove(x+2,y-1) )
        {
            if(backtrack(x+2, y-1)) return true;
        }
        if( canmove(x+1,y+2) )
        {
            if(backtrack(x+1, y+2)) return true;
        }
        if( canmove(x+1,y-2) )
        {
            if(backtrack(x+1, y-2)) return true;
        }
        unmark(board[x][y]);
    }
    return false;
}

ここで、すべての [x][y] を訪問するには、再帰がどれだけ深くなければならないか考えてみてください。かなり深いですよね？そのため、より効率的な戦略について考えたいと思うかもしれません。これらの 2 つのプリントアウトをボード ディスプレイに追加すると、バックトラック ステップがいくつ発生したかがわかります。

int counter = 1; int stepcount=0;
...
void horse::print()
{
    cout<< "counter: "<<counter<<endl;
    cout<< "stepcount: "<<stepcount<<endl;
    ...
bool horse::backtrack(int x, int y)
{
    stepcount++;
    ...

5x5、6x6、7x6、

./knightstour 5
 >>> Successful! <<< 
counter: 26
stepcount: 253283

./knightstour 6
 >>> Successful! <<< 
counter: 37
stepcount: 126229019

./knightstour 7
 >>> Successful! <<< 
counter: 50
stepcount: 56342

なぜ 5 よりも 7 の方がステップ数が少ないのですか? バックトラックでの動きの順序について考えてみてください。順序を変更すると、ステップが変わりますか? 可能な手 [ {1,2},{-1,2},{1,-2},{-1,-2},{2,1},{2,1} ,{2,1},{2,1} ]、そしてそれらを別の順序で処理しましたか? 動きの並べ替えを簡単にすることができます。

int moves[ ] =
{ -2,+1, -2,-1, -1,+2, -1,-2, +2,+1, +2,-1, +1,+2, +1,-2 };
...
        for(int mdx=0;mdx<8*2;mdx+=2)
        {
        if( canmove(x+moves[mdx],y+moves[mdx+1]) )
        {
            if(backtrack(x+moves[mdx], y+moves[mdx+1])) return true;
        }
        }

元のムーブ シーケンスをこれに変更し、7x7 で実行すると異なる結果が得られます。

{ +2,+1, +2,-1, +1,+2, +1,-2, -2,+1, -2,-1, -1,+2, -1,-2 };


./knightstour 7
 >>> Successful! <<< 
counter: 50
stepcount: -556153603 //sheesh, overflow!

しかし、あなたの最初の質問は、

問題は次のとおりです:このアルゴリズムの時間計算量はどのくらいですか? また、どのように最適化すればよいでしょうか?!

バックトラッキング アルゴリズムは約 8^(n^2) ですが、わずか n^2 回の移動で答えが見つかる場合があります。それを O() の複雑さのメトリックに変換します。

これは、答えを教えなくても、答えに導くと思います。