算法题（Knight巡回问题的Warnsdorff算法实现） _Warnsdorff

本文概述

C ++
Java

问题：一个骑士被放置在一个空棋盘的第一块上, 并且根据国际象棋的规则移动, 必须对每个广场精确地访问一次。
以下是Knight覆盖所有单元的示例路径。下面的网格表示一个8 x 8格的棋盘。单元格中的数字表示骑士的移动次数。

文章图片
我们已经讨论过回溯算法, 解决骑士之旅。在这篇文章中沃恩斯多夫的启发式讨论。
Warnsdorff的规则：

我们可以从骑士在板上的任何初始位置开始。
我们总是以最小的程度(最少的未访问相邻数)移动到相邻的未访问正方形。

该算法也可以更普遍地应用于任何图形。
一些定义：

如果P可以通过一个骑士的动作移动到Q, 并且尚未访问Q, 则可以从P位置访问Q。
位置P的可访问性是可从P访问的位置数。

算法：

将P设置为板上的随机初始位置
用移动号" 1"将板标记在P上
对于从2到板上的平方数的每个移动编号, 请执行以下操作：
- 令S为可从P访问的位置集合。
- 将P设置为S中具有最小辅助功能的位置
- 用当前移动编号将板标记在P上
返回标有标记的木板-每个方块都会标有其访问所在的移动编号。

下面是上述算法的实现。
C ++

//C++ program to for Kinight's tour problem usin //Warnsdorff's algorithm #include < bits/stdc++.h> #define N 8//Move pattern on basis of the change of //x coordinates and y coordinates respectively static int cx[N] = {1, 1, 2, 2, -1, -1, -2, -2}; static int cy[N] = {2, -2, 1, -1, 2, -2, 1, -1}; //function restricts the knight to remain within //the 8x8 chessboard bool limits( int x, int y) { return ((x> = 0 & & y> = 0) & & (x < N & & y < N)); }/* Checks whether a square is valid and empty or not */ bool isempty( int a[], int x, int y) { return (limits(x, y)) & & (a[y*N+x] < 0); }/* Returns the number of empty squares adjacent to (x, y) */ int getDegree( int a[], int x, int y) { int count = 0; for ( int i = 0; i < N; ++i) if (isempty(a, (x + cx[i]), (y + cy[i]))) count++; return count; }//Picks next point using Warnsdorff's heuristic. //Returns false if it is not possible to pick //next point. bool nextMove( int a[], int *x, int *y) { int min_deg_idx = -1, c, min_deg = (N+1), nx, ny; //Try all N adjacent of (*x, *y) starting //from a random adjacent. Find the adjacent //with minimum degree. int start = rand ()%N; for ( int count = 0; count < N; ++count) { int i = (start + count)%N; nx = *x + cx[i]; ny = *y + cy[i]; if ((isempty(a, nx, ny)) & & (c = getDegree(a, nx, ny)) < min_deg) { min_deg_idx = i; min_deg = c; } }//IF we could not find a next cell if (min_deg_idx == -1) return false ; //Store coordinates of next point nx = *x + cx[min_deg_idx]; ny = *y + cy[min_deg_idx]; //Mark next move a[ny*N + nx] = a[(*y)*N + (*x)]+1; //Update next point *x = nx; *y = ny; return true ; }/* displays the chessboard with all the legal knight's moves */ void print( int a[]) { for ( int i = 0; i < N; ++i) { for ( int j = 0; j < N; ++j) printf ( "%d\t" , a[j*N+i]); printf ( "\n" ); } }/* checks its neighbouring sqaures */ /* If the knight ends on a square that is one knight's move from the beginning square, then tour is closed */ bool neighbour( int x, int y, int xx, int yy) { for ( int i = 0; i < N; ++i) if (((x+cx[i]) == xx)& & ((y + cy[i]) == yy)) return true ; return false ; }/* Generates the legal moves using warnsdorff's heuristics. Returns false if not possible */ bool findClosedTour() { //Filling up the chessboard matrix with -1's int a[N*N]; for ( int i = 0; i< N*N; ++i) a[i] = -1; //Randome initial position int sx = rand ()%N; int sy = rand ()%N; //Current points are same as initial points int x = sx, y = sy; a[y*N+x] = 1; //Mark first move.//Keep picking next points using //Warnsdorff's heuristic for ( int i = 0; i < N*N-1; ++i) if (nextMove(a, & x, & y) == 0) return false ; //Check if tour is closed (Can end //at starting point) if (!neighbour(x, y, sx, sy)) return false ; print(a); return true ; }//Driver code int main() { //To make sure that different random //initial positions are picked. srand ( time (NULL)); //While we don't get a solution while (!findClosedTour()) { ; }return 0; }

Java

//Java program to for Kinight's tour problem using //Warnsdorff's algorithm import java.util.concurrent.ThreadLocalRandom; class GFG { public static final int N = 8 ; //Move pattern on basis of the change of //x coordinates and y coordinates respectively public static final int cx[] = { 1 , 1 , 2 , 2 , - 1 , - 1 , - 2 , - 2 }; public static final int cy[] = { 2 , - 2 , 1 , - 1 , 2 , - 2 , 1 , - 1 }; //function restricts the knight to remain within //the 8x8 chessboard boolean limits( int x, int y) { return ((x> = 0 & & y> = 0 ) & & (x < N & & y < N)); }/* Checks whether a square is valid and empty or not */ boolean isempty( int a[], int x, int y) { return (limits(x, y)) & & (a[y * N + x] < 0 ); }/* Returns the number of empty squares adjacent to (x, y) */ int getDegree( int a[], int x, int y) { int count = 0 ; for ( int i = 0 ; i < N; ++i) if (isempty(a, (x + cx[i]), (y + cy[i]))) count++; return count; }//Picks next point using Warnsdorff's heuristic. //Returns false if it is not possible to pick //next point. Cell nextMove( int a[], Cell cell) { int min_deg_idx = - 1 , c, min_deg = (N + 1 ), nx, ny; //Try all N adjacent of (*x, *y) starting //from a random adjacent. Find the adjacent //with minimum degree. int start = ThreadLocalRandom.current().nextInt( 1000 ) % N; for ( int count = 0 ; count < N; ++count) { int i = (start + count) % N; nx = cell.x + cx[i]; ny = cell.y + cy[i]; if ((isempty(a, nx, ny)) & & (c = getDegree(a, nx, ny)) < min_deg) { min_deg_idx = i; min_deg = c; } }//IF we could not find a next cell if (min_deg_idx == - 1 ) return null ; //Store coordinates of next point nx = cell.x + cx[min_deg_idx]; ny = cell.y + cy[min_deg_idx]; //Mark next move a[ny * N + nx] = a[(cell.y) * N + (cell.x)] + 1 ; //Update next point cell.x = nx; cell.y = ny; return cell; }/* displays the chessboard with all the legal knight's moves */ void print( int a[]) { for ( int i = 0 ; i < N; ++i) { for ( int j = 0 ; j < N; ++j) System.out.printf( "%d\t" , a[j * N + i]); System.out.printf( "\n" ); } }/* checks its neighbouring sqaures */ /* If the knight ends on a square that is one knight's move from the beginning square, then tour is closed */ boolean neighbour( int x, int y, int xx, int yy) { for ( int i = 0 ; i < N; ++i) if (((x + cx[i]) == xx) & & ((y + cy[i]) == yy)) return true ; return false ; }/* Generates the legal moves using warnsdorff's heuristics. Returns false if not possible */ boolean findClosedTour() { //Filling up the chessboard matrix with -1's int a[] = new int [N * N]; for ( int i = 0 ; i < N * N; ++i) a[i] = - 1 ; //initial position int sx = 3 ; int sy = 2 ; //Current points are same as initial points Cell cell = new Cell(sx, sy); a[cell.y * N + cell.x] = 1 ; //Mark first move.//Keep picking next points using //Warnsdorff's heuristic Cell ret = null ; for ( int i = 0 ; i < N * N - 1 ; ++i) { ret = nextMove(a, cell); if (ret == null ) return false ; }//Check if tour is closed (Can end //at starting point) if (!neighbour(ret.x, ret.y, sx, sy)) return false ; print(a); return true ; }//Driver Code public static void main(String[] args) { //While we don't get a solution while (! new GFG().findClosedTour()) { ; } } }class Cell { int x; int y; public Cell( int x, int y) { this .x = x; this .y = y; } }//This code is contributed by SaeedZarinfam

输出如下：

59146332116193462316015563321713585564491835203061425754514034312535041482136262944475239471146272496372228251045382385

【算法题（Knight巡回问题的Warnsdorff算法实现）】哈密顿路径问题通常是NP难的。在实践中, 沃恩斯多夫的启发式方法成功地找到了线性时间的解决方案。
你知道吗？
"在8×8的板上, 恰好有26, 534, 728, 821, 064个定向封闭巡回路线(即, 沿着同一路径沿相反方向行驶的两个巡回路线分别计算在内, 旋转和反射也是如此)。无方向的封闭式游览的数量是该数字的一半, 因为每个游览都可以反向追踪！"
如果发现任何不正确的地方, 或者想分享有关上述主题的更多信息, 请写评论。