java使用BFS实现国际象棋骑士穿越目标的最小步数

Question

下面给出的代码适用于小于13码的国际象棋，但在这之后，它会花费太多时间，并且永远运行。 我想缩短到达终点节点的时间。 这段代码还可以找到从starti，startj到endi，endj的最小路径，其中starti和startj的值从1到n-1

以下是我试图解决的问题：
https://www.hackerrank.com/challenges/knightl-on-chessboard/problem

节目：

import java.util.LinkedList;<br>
import java.util.Scanner;

class Node {

    int x,y,dist;

    Node(int x, int y, int dist) {
        this.x = x;
        this.y = y;
        this.dist = dist;
    }

    public String toString() {
        return "x: "+ x +" y: "+y +" dist: "+dist;
    }
}

class Solution {

    public static boolean checkBound(int x, int y, int n) {

        if(x >0 && y>0 && x<=n && y<=n)
            return true;
        return false;
    }

    public static void printAnswer(int answer[][], int n) {
        for(int i=0; i<n-1; i++) {
            for(int j=0; j<n-1; j++) {
                System.out.print(answer[i][j]+" ");
            }
            System.out.println();
        }

    }

    public static int findMinimumStep(int n, int[] start, int[] end, int a, int b) {

        LinkedList<Node> queue = new LinkedList();
        boolean visited[][] = new boolean[n+1][n+1];
        queue.add(new Node(start[0],start[1],0));       
        int x,y;

        int[] dx = new int[] {a, -a, a, -a, b, -b, b, -b};
        int[] dy = new int[] {b, b, -b, -b, a, a, -a, -a};


        while(!queue.isEmpty()) {
            Node z = queue.removeFirst();
            visited[z.x][z.y] = true;

            if(z.x == end[0] && z.y == end[1])
                return z.dist;

            for(int i=0; i<8; i++)
            {
                x = z.x + dx[i];
                y = z.y + dy[i];            
                if(checkBound(x,y,n) && !visited[x][y])
                    queue.add(new Node(x,y,z.dist+1));
            }
        }
        return -1;
    }

    public static void main(String args[]) {

        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        int start[] = new int[] {1,1};
        int goal[] = new int[] {n,n};
        int answer[][] = new int[n-1][n-1];

        for(int i=1; i<n; i++) {
            for(int j=i; j<n; j++) {
                int result = findMinimumStep(n, start, goal, i, j);
                answer[i-1][j-1] = result;
                answer[j-1][i-1] = result;
            }
        }
        printAnswer(answer,n);

    }
}

Answer 1

设置visited太晚，同一个单元格被多次添加到队列中，然后在不检查其已访问状态的情况下将其从队列中弹出，这会使情况变得更糟。这导致了队列的快速增长

将Node添加到队列后，需要立即设置visited：

if(checkBound(x,y,n) && !visited[x][y]) {
    queue.add(new Node(x,y,z.dist+1)); 
    visited[x][y] = true;   
}

Answer 2

即使优化了代码，也不会降低算法的复杂性

我认为你需要考虑如何减少搜索空间。或者以巧妙的顺序搜索它

我会去A*-search

Answer 3

你的问题最有效的解决方法是Dijkstra's algorithm。将方块视为节点，并向骑士可以访问的其他方块/节点绘制边。然后运行这个图的算法。它在对数时间内执行，因此对于大问题，它的伸缩性非常好

史密斯先生提出的搜索建议是一种启发式方法，所以我不建议用它来解决这类问题

Dijkstra是一个重要的算法，实现它将帮助您在未来解决许多类似的问题，例如，您也可以用相同的逻辑解决this problem问题