使用递归函数进行并行编程？
问题的背景：我正在尝试编写一个利用多核处理器和并行处理的拼图解算法。 但是，理想/最简单的解决方案是简单的递归function。
分解解决方案以利用并行处理和递归函数的最佳方法是什么？
下面的代码是一个简单的解谜算法的解决方案（它正常工作）。 这个例子中的谜题很简单 – 有14个插槽编号为1-14。 每个拼图都有一个唯一的ID，一个范围告诉你它可以在哪里开始和停止（例如6-8意味着它只适合6-8槽）和价格。 该算法试图找到最大化解决方案价格的解决方案。 只有1个可以占用一个插槽，空插槽是可以接受的。 解决方案会告诉您使用了哪些部件以及总成本。 （为了简单起见，还要假设插槽1必须填充）。
我尝试将并行性和递归结合起来的解决方案如下所示：为每个使用插槽1的部分创建一个Task，然后在Task中递归查看其余部分，将它们插入剩余空间，同时最大化成本。 这是最好的解决方案（可能不是，这就是为什么我在这里）。 怎么改进？ 使用并行/递归解决方案时还有其他好的建议吗？
虽然简单的递归在这里运行良好，但我想象一下这个有200个插槽和5000个拼图的拼图。
以下是此示例的解决方案：
ID=1 Price=10.0 Range=1-6 ID=12 Price=8.0 Range=9-14 ID=15 Price=3.0 Range=7-8 public class Puzzle { public PuzzleSet calculateResults(PuzzleSet input) throws Exception { System.out.println(System.currentTimeMillis()); PuzzleSet results = getPriceMultithread((PuzzleSet)SerializationUtils.clone(input)); System.out.println(System.currentTimeMillis()); return results; } private PuzzleSet getPriceMultithread(PuzzleSet input) throws Exception { PuzzleSet initial = input.startsAtPoint(1); ExecutorService exec = Executors.newFixedThreadPool(Runtime.getRuntime().availableProcessors()+1); Collection<Callable> tasks = new ArrayList<Callable>(); for (int i=0; i<initial.size(); i++) { final PuzzleData d = initial.get(i); final PuzzleSet start = input.higherThan(initial.get(i).rangeUpper); tasks.add(new Callable() { public PuzzleSet call() { PuzzleSet s = new PuzzleSet(); s.add(d); s.addAll(getPrice(start)); return s; } }); } List<Future> results = exec.invokeAll(tasks); PuzzleSet max = new PuzzleSet(); double maxD = 0.0; for (int i=0; i maxD) { maxD = sum; max = temp; } } return max; } private PuzzleSet getPrice(PuzzleSet input) { if (input == null || input.size() == 0) return new PuzzleSet(); double maxD = 0.0; PuzzleSet max = new PuzzleSet(); for (int i=0; i maxD) { maxD = pTemp; s.add(input.get(i)); max = s; } } return max; } public static void main(String arg[]) throws Exception { PuzzleSet s = new PuzzleSet(); PuzzleData v1 = new PuzzleData(); v1.rangeLower = 1; v1.rangeUpper = 6; v1.price = 10; v1.ID = 1; s.add(v1); PuzzleData v2 = new PuzzleData(); v2.rangeLower = 7; v2.rangeUpper = 11; v2.price = 0; v2.ID = 2; s.add(v2); PuzzleData v3 = new PuzzleData(); v3.rangeLower = 12; v3.rangeUpper = 14; v3.price = 7; v3.ID = 3; s.add(v3); PuzzleData v5 = new PuzzleData(); v5.rangeLower = 7; v5.rangeUpper = 9; v5.price = 0; v5.ID = 4; s.add(v5); PuzzleData v6 = new PuzzleData(); v6.rangeLower = 10; v6.rangeUpper = 14; v6.price = 5; v6.ID = 5; s.add(v6); PuzzleData v7 = new PuzzleData(); v7.rangeLower = 1; v7.rangeUpper = 3; v7.price = 5; v7.ID = 6; s.add(v7); PuzzleData v8 = new PuzzleData(); v8.rangeLower = 4; v8.rangeUpper = 9; v8.price = 0; v8.ID = 7; s.add(v8); PuzzleData v10 = new PuzzleData(); v10.rangeLower = 1; v10.rangeUpper = 5; v10.price = 3; v10.ID = 8; s.add(v10); PuzzleData v11 = new PuzzleData(); v11.rangeLower = 6; v11.rangeUpper = 11; v11.price = 2; v11.ID = 9; s.add(v11); PuzzleData v12 = new PuzzleData(); v12.rangeLower = 12; v12.rangeUpper = 14; v12.price = 7; v12.ID = 10; s.add(v12); PuzzleData v14 = new PuzzleData(); v14.rangeLower = 4; v14.rangeUpper = 8; v14.price = 1; v14.ID = 11; s.add(v14); PuzzleData v15 = new PuzzleData(); v15.rangeLower = 9; v15.rangeUpper = 14; v15.price = 8; v15.ID = 12; s.add(v15); PuzzleData v16 = new PuzzleData(); v16.rangeLower = 1; v16.rangeUpper = 5; v16.price = 3; v16.ID = 13; s.add(v16); PuzzleData v17 = new PuzzleData(); v17.rangeLower = 6; v17.rangeUpper = 8; v17.price = 1; v17.ID = 14; s.add(v17); PuzzleData v18 = new PuzzleData(); v18.rangeLower = 7; v18.rangeUpper = 8; v18.price = 3; v18.ID = 15; s.add(v18); PuzzleSet x = new Puzzle().calculateResults(s); for (int i=0; i<x.size(); i++) { System.out.println(x.get(i)); } } } public class PuzzleData implements Serializable { public int rangeLower; public int rangeUpper; public int ID; public double price; public String toString() { return "ID=" + ID + " Price=" + price + " Range=" + rangeLower + "-" + rangeUpper; } } public class PuzzleSet extends ArrayList implements Serializable { public PuzzleSet higherThan(int lowBound) { PuzzleSet s = new PuzzleSet(); for (int i=0; i lowBound) s.add(get(i)); } return s; } public PuzzleSet startsAtPoint(int point) { PuzzleSet s = new PuzzleSet(); for (int i=0; i<size(); i++) { if (get(i).rangeLower == point) s.add(get(i)); } return s; } public double sum() { double sum = 0.0; for (int i=0; i<size(); i++) sum += get(i).price; return sum; } public String toString() { StringBuffer b = new StringBuffer(); for (int i=0; i<size(); i++) { b.append(get(i).toString()); } return b.toString(); } } JSR-166Y旨在通过处理线程协调来简化Java 7中并行递归的实现。 您可能会发现他们的讨论，代码和论文（特别是Doug Lea的论文A Java Fork / Join Framework ）很有用。
问题的类型让我想起了遗传算法。 你已经有了健身function（成本），问题的布局似乎适合交叉和变异。 您可以使用其中一个可用的GA引擎并行运行多个池/代。 虽然找到绝对最佳的解决方案并不能得到保证，但GA往往会很快找到好的解决方案。 另一方面，我相信你描述的谜题无论如何都不一定有一个单一的最优解决方案。 GA解决方案通常用于安排（例如创建教师，教室和class级的名单）。 所发现的解决方案通常是“强大的”，因为通常可以通过最少量的更改找到满足约束变化的合理解决方案。
至于并行化给定的递归算法。 我最近尝试了这个（使用Terracotta）来解决n-Queens问题并且做了类似于你所描述的事情。 第一行后置放置在每个可能的列中以创建n个子问题。 有一个工作线程池。 作业计划程序检查池中是否有可用的空闲工作线程，并为其分配子问题。 工作线程通过子问题工作，输出所有找到的解决方案，并返回空闲状态。 因为工作线程通常比子问题少得多，所以如果子问题没有花费相同的时间来解决，这不是一个大问题。
我很想听听其他想法。
你可以使用蒙特卡洛并且平行地运行它们。 根据约束，在选择片段时添加一些随机性。