达到国际象棋目标的最少步数 - 使用 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

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

我认为你需要考虑如何减少搜索space。或者按巧妙的顺序搜索。

我会去 A*-search

Answer 2

你设置 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 3

您的问题最有效的解决方案是Dijkstra's algorithm。将正方形视为节点，并向骑士可以访问的另一个 squares/nodes 绘制边。然后运行这个图的算法。它以对数时间执行，因此它可以很好地解决大问题。

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

Dijkstra是一个重要的算法，实现它会帮助你解决很多类似的问题，比如你也可以用同样的逻辑解决this problem问题。

达到国际象棋目标的最少步数 - 使用 BFS 进行骑士遍历

Minimum number steps to reach goal in chess - knight traversal with BFS

java

algorithm

search

game-theory

graph-algorithm