如何使Java递归迷宫求解器更有效?

内容来源于 Stack Overflow,并遵循CC BY-SA 3.0许可协议进行翻译与使用

  • 回答 (1)
  • 关注 (0)
  • 查看 (80)

能够通过将线程大小增加到几千兆字节来使我的算法工作,并且能够在一两秒钟内解决1803x1803迷宫

---------------

我昨天开始用Java教自己递归。我创建了一个算法,拍摄迷宫照片并解决它。但是,当我做一个大于200x200像素的迷宫时,我得到一个堆栈溢出答案,因为我觉得这个算法的堆栈太长了。我怎样才能更好地使用这个算法,以便输入可能达到1000x1000的图像?

另外,你能告诉我我目前使用的是哪种算法吗?我相信这是DFS,但我不确定。

请解释为什么您的解决方案更有效率以及它使用的想法。

这是解决的主要课程

public class BlackWhiteSolver {

static int[][] solutionSet = new int[203][203];
static int width, height;
static String originalImage;
static int correctX, correctY;

public static void convert() {
try {
BufferedImage original = ImageIO.read(new File(originalImage));
int red;
int threshold = 2;
width = original.getWidth();
height = original.getHeight();

    for(int i=0; i<original.getWidth(); i++) {
        for(int j=0; j<original.getHeight(); j++) {
            red = new Color(original.getRGB(i, j)).getRed();
            // 1 = white, 0 = black, 9 = tried, 5 = solved
            if(red > threshold) { solutionSet[i][j] = 1; }
            else { solutionSet[i][j] = 0; }
        }
    }

} catch (IOException e) {e.printStackTrace();}
}

public BlackWhiteSolver(int solvedX, int solvedY, String pic) {
    correctX = solvedX;
    correctY = solvedY;
    originalImage = pic;
}

public boolean solve (int row, int column) {

        boolean completed = false;


        if (validPoint(row, column)) {
            solutionSet[row][column] = 9;

            if (row == correctX && column == correctY) {
                completed = true;
            } else {
                completed = solve (row+1, column);
                if (!completed) {
                    completed = solve (row, column+1);
                }
                if (!completed) {
                    completed = solve (row-1, column);
                }
                if (!completed) {
                    completed = solve (row, column-1);
                }
            }
            if (completed) {
                solutionSet[row][column] = 5;
            }
        }

        return completed;
    }

private boolean validPoint (int row, int column) {

        boolean isValid = false;
        if (row < height-1 && column < width-1 && row >= 1 && column >= 1 ) {
            if (solutionSet[row][column] == 1) {
            isValid = true;
            }
        }

        return isValid;
    }

public static void solvedFile() {
    BufferedImage binarized = new BufferedImage(width, height,BufferedImage.TYPE_3BYTE_BGR);
    int newPixel = 0;
    int rgb = new Color(255, 0, 0).getRGB();
    for(int i=0; i<width; i++){
        for(int j=0; j<height; j++)
    {
        if (solutionSet[i][j] == 0) {
            newPixel = 0;
            newPixel = colorToRGB(1, newPixel, newPixel, newPixel);
        } else if (solutionSet[i][j] == 1 || solutionSet[i][j] == 9) {
            newPixel = 255;
            newPixel = colorToRGB(1, newPixel, newPixel, newPixel);
        } else if (solutionSet[i][j] == 5) {
            newPixel = 16711680;
        }

        binarized.setRGB(i, j, newPixel);
    }
    }

    try { ImageIO.write(binarized, "gif",new File("maze-complete") );} catch (IOException e) {e.printStackTrace();}

}

    private static int colorToRGB(int alpha, int red, int green, int blue) {
        int newPixel = 0;
        newPixel += alpha;
        newPixel = newPixel << 8;
        newPixel += red; newPixel = newPixel << 8;
        newPixel += green; newPixel = newPixel << 8;
        newPixel += blue;
        return newPixel;
    }


}

这是运行迷宫的类

public class BlackWhiteInterface
{

    public static void main (String[] args) {

        BlackWhiteSolver puzzle = new BlackWhiteSolver(60, 202, "maze-4.gif");

        System.out.println();

        puzzle.convert();

        if (puzzle.solve(0,34)) {
            System.out.println("completed");
            puzzle.solvedFile();
        } else {
            System.out.println("not possible");
        }
    }
}

使用起点和终点生成正确的迷宫

public class MazeBuilder {

    static String start = "left";
    static String end = "down";

    public static void main(String[] args)
    {
        try
        {
            BufferedImage original = ImageIO.read(new File("mazeInput1.gif"));
            BufferedImage binarized = new BufferedImage(original.getWidth(), original.getHeight(),BufferedImage.TYPE_BYTE_BINARY);
            int red;
            int redRightPixel;
            int redUpPixel;
            int newPixel;
            int threshold = 2;

            for(int i=0; i<original.getWidth(); i++)
            {
                for(int j=0; j<original.getHeight(); j++)
                {

                    red = new Color(original.getRGB(i, j)).getRed();
                    int alpha = new Color(original.getRGB(i, j)).getAlpha();
                    if(red > threshold) { newPixel = 255; }
                    else { newPixel = 0; }

                    if (i == 0 || j == 0 || i == original.getWidth()-1 || j == original.getHeight() - 1){
                        newPixel = 0;

                        if (end == "left") {

                        } else if (end == "right") {

                        } else if (end == "up") {

                        } else if (end == "down") {

                        }


    /*if (i == 1 || j == 1 || i == original.getWidth()-2 || j == original.getHeight() - 2 && red > 2) {
        System.out.println("Start Point: (" + i + ", " + j + ")");
    }
    if (i == 0 && j > 0 && j < original.getHeight()-1) {


        redRightPixel = new Color(original.getRGB(i+1, j)).getRed();

        if (i == 0 && redRightPixel > 2) {
            System.out.println("Start Point: (" + i + ", " + j + ")");
            newPixel = 255;
        }
    }*/

    /*if (j == original.getHeight()-1 && i > 0 && i < original.getWidth()-1) {

        redUpPixel = new Color(original.getRGB(i, j-1)).getRed();

        if (redUpPixel > 2) {
            System.out.println("End Point: (" + i + ", " + j + ")");
            newPixel = 255;
        }
    }*/

                    }

                    if (start == "left") {
                        if (i == 1 && j != 0 && j != original.getHeight()-1 && red > 2) {
                            System.out.println("Start Point: (" + i + ", " + j + ")");
                        }
                    } else if (start == "right") {
                        if (i == original.getHeight()-2 && j != 0 && j != original.getHeight()-1 && red > threshold) {
                            System.out.println("Start Point: (" + i + ", " + j + ")");
                        }
                    } else if (start == "up") {
                        if (j == 1 && i != 0 && i != original.getWidth()-1 && red > threshold) {
                            System.out.println("Start Point: (" + i + ", " + j + ")");
                        }
                    } else if (start == "down") {
                        if (j == original.getHeight()-2 && i != 0 && i != original.getWidth()-1 && red > threshold) {
                            System.out.println("Start Point: (" + i + ", " + j + ")");
                        }
                    }

                    if (end == "left") {
                        if (i == 1 && j != 0 && j != original.getHeight()-1 && red > 2) {
                            System.out.println("End Point: (" + i + ", " + j + ")");
                        }
                    } else if (end == "right") {
                        if (i == original.getHeight()-2 && j != 0 && j != original.getHeight()-1 && red > threshold) {
                            System.out.println("End Point: (" + i + ", " + j + ")");
                        }
                    } else if (end == "up") {
                        if (j == 1 && i != 0 && i != original.getWidth()-1 && red > threshold) {
                            System.out.println("End Point: (" + i + ", " + j + ")");
                        }
                    } else if (end == "down") {
                        if (j == original.getHeight()-2 && i != 0 && i != original.getWidth()-1 && red > threshold) {
                            System.out.println("End Point: (" + i + ", " + j + ")");
                        }
                    }


                    newPixel = colorToRGB(alpha, newPixel, newPixel, newPixel);
                    binarized.setRGB(i, j, newPixel);
                }
            }
            ImageIO.write(binarized, "gif",new File("maze-4") );
        }
        catch (IOException e)
        {
            e.printStackTrace();
        }
    }
    private static int colorToRGB(int alpha, int red, int green, int blue) {
        int newPixel = 0;
        newPixel += alpha;
        newPixel = newPixel << 8;
        newPixel += red; newPixel = newPixel << 8;
        newPixel += green; newPixel = newPixel << 8;
        newPixel += blue;
        return newPixel;
    }

203 x 203迷宫的示例输出

提问于
用户回答回答于

一种只是略微提高效率的简单方法是不使用递归存储到目前为止在堆栈中所遵循的路径。而是将您目前所遵循的路径存储在a java.util.BitSet(将元素y*width + x中的每个路径像素存储在其中BitSet),或者您可以简单地使用已着色的图片的红色区域来存储路径。

这可以避免堆栈溢出。

基本算法是从起点开始,然后进入四个基本方向中的一个,除非你已经去过那个方向(要么尝试它,要么找到一个死胡同或者从那个方向来到这里)。当你向某个方向前进时,你会在那里做同样的事情。这是一个简单的非递归循环。

当你走到死胡同时,你可以通过检查所有四个方向来确定你是如何到达那里的,从那里你可以看到路径的来源。你从你所站立的地方移走红色,然后沿着你来自的方向返回。如果在任何方向都没有红色路径,那么你再次处于起点并且你已经尝试了所有方法,因此迷宫没有解决方案。

当你回溯时,你会尝试在路径上的旧方块上没有尝试过的下一个方向,直到所有方向都是死路

扫码关注云+社区

领取腾讯云代金券