0

在我的分布式 Java 类中，我必须创建一个使用线程解决迷宫的算法。迷宫中的所有交叉点（多于一条剩余路径）将创建一个新线程，该线程将在旧线程中断的地方继续。最后我会查看所有路径，看看哪一个是有效的（从头开始，到最后）。

我想用Ford-Fulkerson 算法做同样的事情，但是这一次，我不必使用线程，我想避免这种情况，因为有一个线程会不断产生新线程，从而产生新线程（并且等等）似乎不必要的危险。

这是我的伪代码算法+一些信息：

该图是一个n矩阵n，其中int matrix [line][column]表示flow节点line index和节点之间column index（未连接的流为-1）

PathFinder:
    current
    start
    end
    path[] // actually an arraylist of integer

    run () { // thread part
        while not at end path {
            if possible paths == 0
               return
            if possible paths == 1
               continue that way
            if possible paths > 1
               create new thread for each path // each thread inherits path up to this point
        }
    }

在主程序中我只是调用pathFinder(start,end)then PathFinder.getAllPaths()，并过滤无效路径（死胡同、循环）。好吧，实际上我计划在该run()部分中处理循环，但我还忘了这样做。这很容易。

最后，我有一个包含所有路径的静态变量（arrayList）。我验证哪些路径是“有效的”，就是这样。

我应该使这个递归而不是使用线程吗？还有其他解决方案吗？我应该发布实际代码（尽管它不完整）。

4

2 回答 2

1

您可以使用队列而不是线程。每个交叉点只是将要调查的节点添加到队列中，并且主循环一直运行直到队列为空。

于 2013-12-12T16:52:07.980 回答
0

最后，使用队列的建议答案违背了目的。如果我要使用队列，我仍然必须实现某种回溯，这样做的重点是避免使用回溯，所以我将坚持使用线程。经过一番思考，他们不可能以消极的方式进行交互，从而消除了对并发问题的任何恐惧。

于 2013-12-12T17:20:12.710 回答