图的深度优先搜索(DFS)的应用--马踏棋盘问题(骑士周游问题)

gong

发布日期: 2020-08-24 15:51:20 浏览量: 81
评分:
star star star star star star star star star star_border
*转载请注明来自write-bug.com

将马随机放在国际象棋的 8X8 棋盘Board[0~7] [0~7]的某个方格中,马按走棋规则(马走日字)进行移动。要求每个方格只进入一次,走遍棋盘上全部64个方格。

马踏棋盘游戏代码实现

马踏棋盘问题(骑士周游问题)实际上是图的深度优先搜索(DFS)的应用。

如果使用回溯(就是深度优先搜索)来解决,假如马儿踏了53个点,走到了第53个,坐标(1,0) ,发现已经走到尽头,没办法,那就只能回退了,查看其他的路径,就在棋盘上不停的回退…

分析第一种方式的问题,并使用贪心算法(greedyalgorithm)进行优化。解决马踏棋盘问题。

使用前面的游戏来验证算法是否正确。

解决步骤和思路https://blog.csdn.net/zhang0558/article/details/50497298

  • 创建棋盘chessBoard,是一个二维数组

  • 将当前位置设置为已经访问,然后根据当前位置,计算马儿还能走哪些位置,并放入到一个集合中(ArrayList),最多有8个位置,每走-步,就使用step+1

  • 遍历ArrayList中存放的所有位置,看看哪个可以走通,如果走通,就继续,走;不通,就回溯

  • 判断马儿是否完成了任务,使用step 和应该走的步数比较,如果没有达到数量,则表示没有完成任务,将整个棋盘置0

注意:马儿不同的走法(策略),会得到不同的结果,效率也会有影响(优化)

  1. public class HorsechessBoard {
  2. private static int X; // 表示列
  3. private static int Y; // 表示行
  4. private static boolean visited[]; // 是否被访问
  5. private static boolean finished; // 是否全部完成
  6. // 进行行走
  7. public static void traversal(int[][] arr, int row, int col, int step) {
  8. arr[row][col] = step;
  9. visited[row * X + col] = true;// 初始位置标记为已访问
  10. // 获取下一步集合
  11. ArrayList<Point> ps = next(new Point(col, row));
  12. sort(ps); //然后在traversal方法当中的ps进行排序:
  13. // 遍历集合
  14. while (!ps.isEmpty()) {
  15. Point p = ps.remove(0);
  16. // 判断该点是否访问过
  17. if (!visited[p.y * X + p.x]) { // 没有访问过
  18. traversal(arr, p.y, p.x, step+1);
  19. }
  20. }
  21. if (step < X * Y && !finished) {
  22. arr[row][col] = 0;
  23. visited[row * X + col] = false;
  24. } else {
  25. finished = true;
  26. }
  27. }
  28. public static void sort(ArrayList<Point> ps) {
  29. ps.sort(new Comparator<Point>() {
  30. @Override
  31. public int compare(Point o1, Point o2) {
  32. int count1 = next(o1).size();
  33. int count2 = next(o2).size();
  34. if (count1 < count2) {
  35. return -1;
  36. } else if (count1 == count2) {
  37. return 0;
  38. } else {
  39. return 1;
  40. }
  41. }
  42. });
  43. }
  44. // 根据当前位置计算还有哪些位置可以走
  45. static int weizhi[][] = {{-2,1},{-2,-1},{-1,2},{-1,-2},{1,2},{1,-2},{2,1},{2,-1}};
  46. public static ArrayList<Point> next(Point cutPoint) {
  47. ArrayList<Point> ps = new ArrayList<Point>();
  48. Point p1 = new Point();
  49. // 判断是否可以走下一个位置
  50. if ((p1.x = cutPoint.x - 2) >= 0 && (p1.y = cutPoint.y - 1) >= 0) {
  51. ps.add(new Point(p1));
  52. }
  53. if ((p1.x = cutPoint.x - 1) >= 0 && (p1.y = cutPoint.y - 2) >= 0) {
  54. ps.add(new Point(p1));
  55. }
  56. if ((p1.x = cutPoint.x + 1) < X && (p1.y = cutPoint.y - 2) >= 0) {
  57. ps.add(new Point(p1));
  58. }
  59. if ((p1.x = cutPoint.x + 2) < X && (p1.y = cutPoint.y - 1) >= 0) {
  60. ps.add(new Point(p1));
  61. }
  62. if ((p1.x = cutPoint.x + 2) < X && (p1.y = cutPoint.y + 1) < Y) {
  63. ps.add(new Point(p1));
  64. }
  65. if ((p1.x = cutPoint.x + 1) < X && (p1.y = cutPoint.y + 2) < Y) {
  66. ps.add(new Point(p1));
  67. }
  68. if ((p1.x = cutPoint.x - 1) >= 0 && (p1.y = cutPoint.y + 2) < Y) {
  69. ps.add(new Point(p1));
  70. }
  71. if ((p1.x = cutPoint.x - 2) >= 0 && (p1.y = cutPoint.y + 1) < Y) {
  72. ps.add(new Point(p1));
  73. }
  74. return ps;
  75. }
  76. public static void main(String[] args) {
  77. X = 9;//chg to 6
  78. Y = 9;
  79. int row = 5;
  80. int col = 5;
  81. int[][] arr = new int[X][Y];
  82. visited = new boolean[X * Y];
  83. System.out.println("开始");
  84. long start = System.currentTimeMillis();
  85. traversal(arr, row-1, col-1,1);
  86. long end = System.currentTimeMillis();
  87. System.out.println("耗时 = "+ (end-start)+" 毫秒");
  88. for(int[] rows:arr) {
  89. for(int step :rows) {
  90. System.out.print(step+"\t");
  91. }
  92. System.out.println();
  93. }
  94. System.out.println("结束");
  95. }
  96. }
上传的附件 cloud_download HorsechessBoard.java ( 3.98kb, 1次下载 )
eject