尋找最短路徑的遞歸方法

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: unable to create new native thread

請幫我改進我的方法來解決這個問題。如果我計算從一端至各點（如果不可能-1）的距離

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); 

         } 
        } 
       } 
      } 
     } 
    } 

distanceend布爾表達式是用來或我解決問題（發現的最短距離）

Answer 1

作爲Kyllopardium已經說過，BFS吃了很多內存，但是你的問題是你試圖開始一個不適合你的情況的新線程。這可能是由R​​AM，OS的線程限制等引起的。

更簡單的解決方案是使用線程池。閱讀來自Oracle的文章this。一個線程池，你需要它有一些稱爲「工作線程」的線程來處理你的行爲。如果當前沒有工作線程可用，並且沒有人可以啓動（出於何種原因），那麼您的工作將被放入隊列中，直到它可以由當前沒有工作的工作線程執行。這將確保像這樣的異常不會被拋出。