查找最短路径的递归方法

Question

    ########
    #C....G#
    ##.##C##
    #..C..S#
    #C.....#
    ########
S- starting Point
G-Goal
"#"- Blocked Path
"."- Free Paths
"C"- Checkpoints must be visited

可以访问任何点(S，G，C，"."(可以多次访问。 Finally应以 G 结尾。

我想找到 S 和 G 之间的最短路径。我正在使用BFS方法来查找它，但是它的问题会生成数千个线程。我的代码适用于 4x4 数组，但对于 50x50 大数组，它会崩溃：

java.lang.OutOfMemoryError： 无法创建新的本机线程

请帮助我改进解决此问题的方法。

public void distancecalculator(char[][] problem ,Point start ,int distancefound, ArrayList<Point> refernce) {
    Point p = new Point();
    LinkedList<Point> q = new LinkedList<>();
    q.add(start);
    int []x = {1,-1,0,0};
    int []y = {0,0,1,-1};
    int[][]dist = new int[m][n];
    for(int []a : dist){
        Arrays.fill(a,-1);
    }
    if(distanceend==true)
        enddistance = dist;
    dist[start.x][start.y] = distancefound;
    while(!q.isEmpty()){
    //  if(distanceend == true)
        p = q.removeFirst();
    //  else
    //      p = q.getFirst();
    //      ExecutorService execute = Executors.newFixedThreadPool(200);
        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 < m && b < n && dist[a][b] == -1 && problem[a][b] != '#' ) {
                dist[a][b] = 1 + dist[p.x][p.y];
                if (distanceend==true)
                {
                    enddistance[a][b] = dist[a][b];
                    q.add(new Point(a,b));
                }
                if (distanceend==false)
                {
                    //  virtual++;
                    Point  neworigin =  new Point();
                    neworigin.x = a;
                    neworigin.y = b;
                    refernce.add(neworigin);
                    char[][] newproblem =  new char[m][n];
                    //newproblem = problem;
                    int k=0;
                    for(int s=0 ;s<m;s++)
                    {
                        for(int j=0;j<n;j++)
                        {
                            newproblem[s][j] = problem[s][j];
                            if(problem[a][b]=='@')
                                newproblem[a][b]= '.';
                            if(newproblem[s][j]=='@')
                                k=k+1;
                        }
                    }
                    //  System.out.println(k)
                    // System.out.println("1");
                    System.out.println(neworigin);
                    if(k>0)
                    {
                        ArrayList<Point> sompathak =  (ArrayList<Point>)refernce.clone();
                        solver s = new solver(newproblem , neworigin,dist[a][b] , refernce );
                        som =  new Thread(s);
                        som.start();
                        // execute.submit(s);
                    }
                    if(k==0)
                    {    // System.out.println("why god");
                        if(enddistance[a][b]!=-1)
                        {  
                            dist[a][b] = dist[a][b] + enddistance[a][b];
                            temp2 = dist[a][b];
                            System.out.println("Answer is "+ temp2);
                            System.exit(1);
                        }
                    }
                }
            }
        }
    }

如果我正在计算从末端到每个点的距离(如果不可能，则为 -1(或我正在解决问题(找到最短距离(，则使用距离结束布尔表达式

Answer 1

正如Kyllopardium已经说过的那样，BFS消耗了大量内存，但是您的问题是您尝试启动一个新线程，而该线程在您的情况下不会进行。这可能是由 RAM、操作系统的线程限制等引起的。

更简单的解决方案是使用线程池。阅读甲骨文的这篇文章。您需要的线程池具有一些称为"工作线程"的线程来处理您的操作。如果当前没有可用的工作线程，并且无法启动任何工作线程(出于某种原因(，则作业将放在队列中，直到当前没有作业的工作线程可以执行该作业。这将确保不会引发此类异常。