在国际象棋中达到目标的最小数量步数 - 使用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太晚了，并且将相同的单元格多次添加到队列中，然后从队列中弹出它们而不检查它们的访问状态会使事情变得更糟。这导致队列的快速增长。

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

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。将方块视为节点并将边缘绘制为骑士可以访问的其他方块/节点。然后运行此图的算法。它在对数时间内执行，因此它可以很好地解决大问题。

MrSmith建议的A *搜索是一种启发式方法，因此我不建议将其用于此类问题。

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