如何让我的 BFS 算法 运行 更快？

Question

所以我有一个查看网格（二维数组）并找到从起点到终点的所有路径的函数。到目前为止，该算法按预期工作，我得到了我正在寻找的值。

问题是它需要永远。它可以 运行 在 100 x 100 网格上没问题，但是一旦我达到 10000 x 10000 网格，大约需要 10 分钟才能给出答案，而我正在寻找的可能是 1 分钟大多数。

这是现在的样子：

public void BFS(Point s, Point e){
        /**
         * North, South, East, West coordinates
         */
        int[] x = {0,0,1,-1};
        int[] y = {1,-1,0,0};

        LinkedList<Point> queue = new LinkedList<>();
        queue.add(s);

        /**
         * 2D int[][] grid that stores the distances of each point on the grid
         * from the start
         */
        int[][] dist = new int[numRow][numCol];
        for(int[] a : dist){
            Arrays.fill(a,-1);
        }
        /**
        * "obstacles" is an array of Points that contain the (x, y) coordinates of obstacles on the grid
        * designated as a -2, which the BFS algorithm will avoid.
        */
        for(Point ob : obstacles){
            dist[ob.x][ob.y] = -2;
        }
        // Start point
        dist[s.x][s.y] = 0;

        /**
         * Loops over dist[][] from starting point, changing each [x][y] coordinate to the int
         * value that is the distance from S.
         */
        while(!queue.isEmpty()){                                        
            Point p = queue.removeFirst();
            for(int i = 0; i < 4; i++){                             
                int a = p.x + x[i];
                int b = p.y + y[i];
                if(a >= 0 && b >= 0 && a < numRow && b < numCol && dist[a][b] == -1){
                    dist[a][b] = 1 + dist[p.x][p.y];
                    Point tempPoint = new Point(a, b);
                    if(!queue.contains(tempPoint)){
                        queue.add(tempPoint);
                    }
                }
            }
        }

        /**
         * Works backwards to find all shortest path points between S and E, and adds each
         * point to an array called "validPaths"
         */
        queue.add(e);
        while(!queue.isEmpty()){
            Point p = queue.removeFirst();

            // Checks grid space (above, below, left, and right) from Point p
            for(int i = 0; i < 4; i++){
                int curX = p.x + x[i];
                int curY = p.y + y[i];

                // Index Out of Bounds check
                if(curX >= 0 && curY >= 0 && !(curX == start.x && curY == start.y) && curX < numRow && curY < numCol){
                    if(dist[curX][curY] < dist[p.x][p.y] && dist[curX][curY] != -2){ // -2 is an obstacle
                        Point tempPoint = new Point(curX, curY);
                        if(!validPaths.contains(tempPoint)){
                            validPaths.add(tempPoint);
                        }
                        if(!queue.contains(tempPoint)){
                            queue.add(tempPoint);
                        }
                    }
                }
            }
        }

所以，虽然它有效，但它真的很慢。我正在尝试获得 O(n + m)，但我相信它可能会在 O(n^2).

中 运行ning

有没有人知道有什么好的想法可以使它更快？

Answer 1

观察到的效率低下的一个明显原因是比较 !validPaths.contains(tempPoint) 和 !queue.contains(tempPoint)，它们都是 O(n)。要进行这些比较，您应该努力进行 O(1) 比较，这可以通过使用特殊的数据结构来完成，例如 hash-set or simply a bitset.

就目前而言，由于这些比较，您的实现显然是 O(n^2)。