Рекурсивный подход, чтобы найти кратчайший путь

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, чтобы найти его, но проблема с ним порождает тысячи нитей. Мой код работает отлично для массива 4х4, но с большим 50x50 массива он выходит из строя:

java.lang.OutOfMemoryError: unable to create new native thread

Пожалуйста, помогите мне улучшить мой подход к решению этой проблемы. логическое выражение

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 используется, если я вычисление расстояния от конца до каждой точки (-1, если не возможно), или я решение задачи (нахождение кратчайшего расстояния)

Answer 1

В Kyllopardium уже сказано, BFS ест много памяти, но ваша проблема в том, что вы пытаетесь запустить новый Thread, который не будет в вашем случае. Это может быть вызвано оперативной памятью, лимитом потока вашей ОС и т. Д.

Более простым решением было бы использовать пулы потоков. Прочитайте статью this об Oracle. Пул потоков, в котором он нужен, имеет несколько потоков, называемых «Рабочие потоки», которые обрабатывают ваши действия. Если в настоящий момент нет ни одного рабочего потока, и никто не может быть запущен (по каким причинам когда-либо), ваша задача помещается в очередь, пока она не будет выполнена рабочим потоком, который в настоящее время не имеет работы. Это позволит убедиться, что Исключения, подобные этому, не будут выбрасываться.