최단 경로를 찾는 재귀 적 접근

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

이 문제를 해결하기위한 접근 방식을 개선하는 데 도움을주십시오. I는 각 지점에서 끝까지의 거리 (-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 부울 표현식 사용 또는 I는 Kyllopardium같이

Answer 1

(최단 거리를 찾는) 문제를 해결하고 이미 말했듯이, BFS는 많은 기억을 가지고 있지만, 문제는 당신이 당신의 경우에 들어 가지 않는 새로운 실을 시작하려고한다는 것입니다. RAM, OS의 스레드 제한 등으로 인해 발생할 수 있습니다.

더 쉬운 해결책은 스레드 풀을 사용하는 것입니다. 오라클의 this 기사를 읽어보십시오. 스레드 풀에는 필요한 경우 작업을 처리하는 "작업자 스레드"라는 스레드가 있습니다. 현재 사용할 수있는 작업자 스레드가없고 아무도 시작할 수없는 경우 (어떤 이유로 든) 작업이 현재 작업이없는 작업자 스레드에 의해 실행될 때까지 대기열에 배치됩니다. 이렇게하면 예외가 throw되지 않습니다.