递归的方法寻找最短路径 [英] Recursive approach to find shortest path
问题描述
########
#C....G#
##.##C##
#..C..S#
#C.....#
########
S- starting Point
G-Goal
"#"- Blocked Path
"."- Free Paths
"C"- Checkpoints must be visited
任意点可参观（S，G，C，。）可以访问超过一次。 最后应结束于G1
Any Points can be visited(S,G,C,".") can be visited more than once. Finally should end at G.
我想找到S和G之间的最短路径，我使用BFS的方法来找到它，但它存在的问题也产生数千个线程的。我的code正常工作的4×4阵列，但有一个大的50×50阵列崩溃：
I want to find the shortest path between S and G. I am using BFS approach to find it but the problem with it it generates thousands of threads. My code works fine for 4x4 array but with a big array 50x50 it crashes:
java.lang.OutOfMemoryError：无法创建新的本地线程
java.lang.OutOfMemoryError: unable to create new native thread
请帮我提高我的方法来解决这个问题。
Please help me to improve my approach to solve this problem.
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布尔EX pression使用，如果我的计算从最终的距离，以每个点（-1，如果不可能的），或者我解决（发现的最短距离）问题
distanceend boolean expression is used if I am calculation the distance from end to each point (-1 if not possible) or I am solving the problem (finding the shortest distance)
推荐答案
作为的 Kyllopardium 的已经说了，BFS吃大量的内存，但你的问题是，你试图启动一个新的线程是不想你的情况。这可以通过在RAM引起的，由你的操作系统的线程限制，等等。
As Kyllopardium already said, BFS eats a lot of memory, but your problem is that you try to start a new Thread which is not going in your case. This can be caused by the RAM, by the Thread Limit of your OS, and so on.
这是简单的解决方案是使用线程池。阅读从甲骨文这个的文章吧。因为你需要一个线程池有一定的主题叫做工作线程可以处理你的行动。如果目前没有工作线程可用，也没有人可以启动（什么原因话），你的工作被放置在队列中，直到它可以由一个工作线程，目前没有工作被执行。这将确保这样的异常不会被抛出。
An easier solution would be to use Thread Pools. Read this article from Oracle about it. A Thread Pool as you need it has some Threads called "Worker Threads" that handle your actions. If there is currently no worker thread available, and no one could be started (for what reasons ever), your job is placed in a queue until it can be executed by a worker thread that currently has no job. This will make sure that Exceptions like this won't be thrown.
这篇关于递归的方法寻找最短路径的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
