0

为什么我们需要回溯骑士的旅行问题？我们可以只使用递归吗？我试过这样做，但它给出了错误的答案，我无法弄清楚代码或逻辑哪里出错了。

import java.util.*;
public class Solution {

    public static void main(String[] args) {
        Scanner s=new Scanner(System.in);
        int[][] ans=new int[8][8];
        for(int d=0;d<8;d++){
            for(int e=0;e<8;e++){
                ans[d][e]=-1;
            }
        }
        int[] x={2,1,-2,1,-1,-2,-1,2};
        int[] y={1,2,1,-2,-2,-1,2,-1};
        func(x,y,ans,7,7,1);
    }

    public static void func(int[] x,int[] y,int[][] ans,int i,int j,int count){
        if(count==64){
            for(int d=0;d<8;d++){
                for(int e=0;e<8;e++){
                    System.out.print(ans[d][e]+" ");
                }
                System.out.println();
            }
        }
        if(ans[i][j]!=-1){
            return;
        }
        else{
            ans[i][j]=count;
            for(int u=0;u<8;u++){
                if(i+x[u]>=0 && i+x[u]< 8 && j+y[u]>=0 && j+y[u]<8){
                    func(x,y,ans,i+x[u],j+y[u],count+1);
                }
            }
        }
        return;
    }
}
4

2 回答 2

4

在骑士巡回赛问题中需要回溯是至关重要的。您没有在代码中实现回溯的事实是它不起作用的主要原因。

要修复它，您至少必须在方法结束时清除位置。即，当你这样做时，ans[i][j] = count你必须平衡它ans[i][j] = -1以清除那个正方形 - 你没有这样做。

这不是您的代码的唯一问题，但它是主要问题。

存在回溯的替代方案。您可以在任何递归级别创建一个新板，它是当前板的副本，但通常被认为是浪费内存。

这是我最终得到的代码：

// The board size.
private static final int SIZE = 8;
// Contents of board squares when empty.
private static final int EMPTY = -1;
// The 8 possible x,y moves for the knight.
private static final int[] x = {2, 1, -2, 1, -1, -2, -1, 2};
private static final int[] y = {1, 2, 1, -2, -2, -1, 2, -1};

public static void printBoard(int[][] board) {
    // Print out the board.
    for (int d = 0; d < SIZE; d++) {
        for (int e = 0; e < SIZE; e++) {
            System.out.print(board[d][e] + " ");
        }
        System.out.println();
    }

}

public static boolean knightsMove(int[][] board, int i, int j, int count) {
    boolean finished = false;
    // Only step onto empty squares that are on the board.
    if (i >= 0 && i < SIZE && j >= 0 && j < SIZE && board[i][j] == EMPTY) {
        // Mark my route.
        board[i][j] = count;
        // Count up.
        count += 1;
        // Are we done?
        if (count > SIZE * SIZE) {
            System.out.println("=== Solution ===");
            // Print the solution.
            printBoard(board);
            // Finished now.
            return true;
        }
        if (count == SIZE * SIZE) {
            // Nearly there - print something to show progress.
            System.out.println("=== Try === (" + i + "," + j + ")=" + count);
            // Print the current state.
            printBoard(board);
        }
        // Look around to try all moves from here.
        for (int u = 0; u < x.length && !finished; u++) {
            // Try the next place.
            finished = knightsMove(board, i + x[u], j + y[u], count);
        }
        // Clear my trail - you missed this.
        board[i][j] = EMPTY;
    } else {
        // Cannot go there.
        return false;
    }
    return finished;
}

public static void knightsMove() {
    int[][] board = new int[SIZE][SIZE];
    // Clear to EMPTY.
    for (int d = 0; d < board.length; d++) {
        for (int e = 0; e < board[d].length; e++) {
            board[d][e] = EMPTY;
        }
    }
    // Start at (7,7) with count 1.
    knightsMove(board, 7, 7, 1);
}

请耐心等待 - 这需要很长时间才能完成 - 正如您所期望的那样。在我的电脑上，大约需要 20 分钟才能到达：

=== Solution ===
29 42 51 60 27 22 17 24 
50 59 28 41 52 25 20 15 
43 30 61 26 21 16 23 18 
62 49 58 53 40 19 14 7 
57 44 31 48 33 8 3 10 
36 63 34 39 54 11 6 13 
45 56 37 32 47 2 9 4 
64 35 46 55 38 5 12 1

我做了以下更改：

  1. 添加评论 - 您应该始终评论您的代码。
  2. 制作你的x和y数组static- 它们不需要是参数。
  3. 在一个地方完成所有支票（在船上和空的）。
  4. 在未遂事件上打印板，只是为了让您开心。
  5. 用 astatic final EMPTY表示空。
  6. 完成后返回boolean结果以停止搜索。
  7. 添加了回溯。
  8. 使用更好的名称，例如board和knightsMove。
  9. 用于电路板尺寸的常数SIZE。
  10. 可能是一些小的调整。

请不要将此代码用于您的作业 - 通过自己执行此操作并了解每个部分的工作原理，您将学到更多。

于 2015-06-18T08:51:24.113 回答
2

递归是函数/方法调用自身的时候。您的func方法调用自身，因此您的程序使用递归。（顺便说一句：标识符应该提供信息。调用函数function什么也没说；tour会更好）。

回溯是指您通过一个接一个地尝试分支来探索分支问题，并且仅在完成当前分支后才检查下一个分支。您的程序会这样做，因此它使用回溯。

回溯也可以通过堆栈和循环来实现，如下所示：

 State initialState = new State(); // empty board, no moves
 Stack<State> stack = new Stack<State>();
 stack.add(initialState);
 while ( ! stack.isEmpty()) {
      State current = stack.pop();
      for (State next : current.getSuccesorStates()) {
           if (next.isLegal()) {
                 stack.add(next);
           }
      }
 }

这不使用递归。但是，通过递归（使用程序堆栈）更频繁地执行此操作，就像在您的代码中一样。

所以：你的问题需要回溯来解决。尽管您正在使用它，但它不需要递归。

额外的功劳：您的代码失败，因为您应该在完成访问它们时取消标记单元格。这样，当您尝试下一个分支（不会跳转到那里）时，单元格可以自由跳转。见//MISSING注解。

    if(ans[i][j]!=-1){
        return;
    }
    else{
        ans[i][j]=count;
        for(int u=0;u<8;u++){
            if(i+x[u]>=0 && i+x[u]< 8 && j+y[u]>=0 && j+y[u]<8){
                func(x,y,ans,i+x[u],j+y[u],count+1);
            }
        }
    }
    // MISSING: un-mark last marking, so that other branches can be explored
    ans[i][j]=-1
    return;
于 2015-06-18T08:56:13.610 回答